The General Number Field Sieve factors composite $n$ basically this way.

Select homogeneous polynomials with integer coefficients $f(x,y),g(x,y)$ s.t. $f(x,1),g(x,1)$ have common root modulo $n$ but not over the complex numbers.

In the number fields with defining polynomials $f(x,1),g(x,1)$ find two related squares with linear algebra and then express $n$ as difference of two squares. This is done by finding $x_i,y_i$, s.t. $f(x_i,y_i),g(x_i,y_i)$ are smooth.

Here is an algorithm, which if correct will greatly speed the GNFS.

Choose integer $m$ s.t. $m^2 \equiv d \pmod{n}$ and $d$ is not square.

Set $f(x,y)=x^2-d y^2,g(x,y)=x-my$. The common root is $m$.

Choose bound $B$ for the smoothness.

Call $f$ the algebraic side and $g$ the rational side.

The main idea is to make the algebraic side always square.

Sieving step: To make $f(x,y)$ always square in the NF $f(x,1)$, set $X=u^2+dv^2,Y=2uv$, then $f(X,Y)$ is always square in the NF.

$g(X,Y)=v^{2} d - 2 u v m + u^{2}$.

Using sieving state of the art, choose small number $M$, say, $M=100$ and find $u,v$ for which $g(X,Y)$ is $B$-smooth, store them and the corresponding $f(X,Y)$.

So far the algebraic side is square and the rational relations are $B$ smooth.

To speed up sieving and essentially eliminate linear algebra, we let $y=0$ and $X'$ runs over the primes less than $B$.

On the algebraic side $f(X',0)=X'^2$ which is square.

On the rational side $g(X',0)=X'$ which $B$ smooth and is prime.

Store both of the above.

After this step finishes, all of the algebraic side is square in the NF and all of the rational side is $B$-smooth.

In addition we have basis for the linear algebra in the rational side.

So we are close to the GNFS, having basis for the overdetermined rational side and the algebraic side is square.

Then make the rational side square, keeping track of the algebraic side sending $\sqrt{d} \mapsto m$.

Q1 Does GNFS allows relations of the form $f(x,0),g(x,0)$?

Q2 Would this algorithm factor $n$ for small values of $M$?

Q3 In case of positive answer to Q1, would the factorization always be trivial for small values of $M$?


After some experiments, found out this won't work.

The main reason is that square norm (even restricting to being divisible by primes of certain form) doesn't mean square algebraic integer.

Take the number field with defining polynomial $i^2+1=0$. The norm of $x+iy$ is $x^2+y^2$. The norm of $5+ i\cdot0$ is $5^2$, but $5$ is not square. Same for $5\cdot (3+i)^2$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.