Let $N = x^2 + 3y^2$ be a composite integer with a known representation of this form. Consider the cubic polynomial
$$ f(t) = 4t^3 - 3Nt - Nx, $$
and let $K = \mathbb{Q}(\alpha)$ be the cubic number field defined by a root $\alpha$ of $f$, assuming $f$ is irreducible. Then $K$ is cyclic, and $N \vert \Delta_K$.
A heuristic factorization method proceeds as follows:
- Compute fundamental units $u_1, u_2 \in \mathcal{O}_K^\times$.
- Use Hilbert's Theorem 90 to construct $c \in K^\times$ such that $$ u_i = \frac{c}{\sigma(c)}, $$ for a generator $\sigma \in \mathrm{Gal}(K/\mathbb{Q})$.
- We expect that the norm $N_{K/\mathbb{Q}}(c)$ is nontrivially related to the factorization of $N$, so that a factor can be recovered via a gcd computation.
In practice, we do not explicitly work in $\mathcal{O}_K$, but instead reduce modulo $N$. Let
$$ R = (\mathbb{Z}/N\mathbb{Z})[t]/(f), $$
and consider the natural map
$$ \psi : \mathcal{O}_K \to R. $$
If $\overline{N}_{R/\mathbb{Z}/N\mathbb{Z}}$ denotes the induced norm, then for units we have
$$ \overline{N}(\psi(u_i)) \equiv \pm 1 \pmod{N}. $$
This avoids the expansion of the units as algebraic integers, which would be completely impractical for large $\Delta_K$, and works well if the units are given as a power product of algebraic numbers, which is how e.g. PARI/GP presents units in fields of large discriminant. If $u$ is a unit of norm $1$ in $\mathcal{O}_K^\times$ and $\overline{u} = \psi(u)$, we construct
$$ \overline{c} = \overline{u} + \overline{u}\sigma(\overline{u}) + \overline{u}\sigma(\overline{u})\sigma^2(\overline{u}) $$
and then take
$$ \gcd\bigl(N^3, \operatorname{Res}(\overline{c},f)\bigr), $$
The method is successful if the valuations of the prime factors of this gcd are different. It often succeeds in practice. However, there are cases where the final valuations are identical and the gcd is uninteresting.
Unlike the number field sieve, where there are many chances for success if the final congruence is trivial and we do not expect inordinately long strings of bad luck in taking different kernel vectors from the linear algebra, here we appear to have very limited flexibility:
- only two fundamental units $u_1, u_2$,
- possibly their products,
- and adjustments to ensure positive norm (e.g., squaring).
In some cases, no combination seems to yield a nontrivial gcd.
Is there a principled fallback strategy for this method when the final gcd fails to produce a factor of $N$?
If robust, this approach would reduce factoring integers of the form $x^2 + 3y^2$ to computing units in a cubic field. For example, one such interesting number (as of March 2026) is the Cunningham number
$$ 3^{709} + 1 $$
which has a composite 327 digit factor of this form of unknown factorization. However, computing units in the associated field is currently out of reach, e.g. with Buchmann's algorithm. The potential for a breakthrough in computing units would be a separate question.
A PARI/GP implementation suggests that the method succeeds frequently on moderate examples, but exhibits occasional complete failure with trivial gcd output. Here is some proof of concept code:
default(parisizemax,4*1024^3);
default(threadsizemax,4*1024^3);
sos(n, d) = my(s=qfbsolve(Qfb(1, 0, d), n)); if(s, s, []);
B=10^8;while(1,[p,q]=[randomprime(B),randomprime(B)];r=sos(p*q,3);if(#r>0,break;););n=p*q
[A,B]=abs(sos(n,3))
f=4*x^3-3*n*x-n*A;
f=polredbest(f)
k = bnfinit(f,1);
uu = bnfunits(k);
u1=liftall(Mod(prod(i=1,#uu[1][1][,1],[a,e]=uu[1][1][i,];Mod(nfbasistoalg(k,a),n)^e),f))
u2=liftall(Mod(prod(i=1,#uu[1][2][,1],[a,e]=uu[1][2][i,];Mod(nfbasistoalg(k,a),n)^e),f))
polresultant(u1,f) % n
polresultant(u2,f) % n
xc=nfgaloisconj(k)
if (polresultant(u1,f)%n==1,u2=u1;);
if (polresultant(u2,f)%n==n-1,u2=u2^2;);
c=u2+u2*subst(u2,x,xc[2])+u2*subst(u2,x,xc[2])*subst(u2,x,xc[3]);
n
factor(n)
gcd(n^3,polresultant(c,f))
factor(%)
I know you could just say 'computing the fundamental unit in a real quadratic field can also give you factorization, and of general $N$', but actually in that case too it sometimes fails, so the general question remains interesting.
