quadratic sieve

Algorithm

To factor a number $n$ using the quadratic sieve, one seekstwo numbers $x$ and $y$ which are not congruent modulo $n$with $x$ not congruent to $-y$ modulo $n$ buthave $x^2\equiv y^2(modn)$. If two such numbers are found,one can then say that $(x+y)(x-y)\equiv 0(modn)$. Then,$x+y$ and $x-y$ must have non-trivial factors in common with $n$.

The quadratic sieve method of factoring depends upon being ableto create a set of numbers whose factorization can be expressedas a product of pre-chosen primes. These factorizations arerecorded as vectors of the exponents. Once enough vectors arecollected to form a set which contains a linear dependence,this linear dependence is exploited to find two squares whichare equivalent modulo $n$.

To accomplish this, the quadratic sieve method uses a set ofprime numbers called a factor base. Then, it searches fornumbers which can be factored entirely within that factor base.If there are $k$ prime numbers in the factor base, then eachnumber which can be factored within the factor base is storedas a $k$-dimensional vector where the $i$-th component of thevector for $y$ gives the exponent of the $i$-th prime from thefactor base in the factorization of $y$. For example, if thefactor base were $\{2,3,5,7,11,13\}$, thenthe number $y=2^3\cdot 3^2\cdot {11}^5$ would be stored as thevector .

Once $k+1$ of these vectors have been collected, there must bea linear dependence among them. The $k+1$ vectors are takenmodulo $2$ to form vectors in ${\mathbb{Z}}_2^k$. The linear dependenceamong them is used to find a combination of the vectors whichsum up to the zero vector in ${\mathbb{Z}}_2^k$. Summing these vectorsis equivalent to multiplying the $y$’s to which they correspond.And, the zero vector in ${\mathbb{Z}}_2^k$ signals a perfect square.

To factor $n$, chose a factor base $𝐁=\{p_1,p_2,\mathrm{\dots },p_k\}$ such that $2\in 𝐁$ and for each oddprime $p_j$ in $𝐁$, $n$ is a quadratic residue of $p_j$. Now,start picking $x_i$ near $\sqrt{n}$ and calculate $y_i=x_i^2-n$. Clearly $y_i\equiv x_i^2(modn)$. If $y_i$ can becompletely factored by numbers in $𝐁$, then it is called$𝐁$-smooth. If it is not $𝐁$-smooth, then discard $x_i$ and$y_i$ and move on to a new choice of $x_i$. If it is $𝐁$-smooth,then store $x_i$, $y_i$, and the vector of its exponents forthe primes in $𝐁$. Also, record a copy of the exponent vectorwith each component taken modulo $2$.

Once $k+1$ vectors have been recorded, there must be a lineardependence among them. Using the copies of the exponent vectorsthat were taken modulo $2$, determine which ones can be addedtogether to form the zero vector. Multiply together the $x_i$that correspond to those chosen vectors—call this $x$. Also,add together the original vectors that correspond to the chosenvectors to form a new vector $\overrightarrow{v}$. Every component ofthis vector will be even. Divide each element of $\overrightarrow{v}$ by$2$. Form $y={\prod }_{i=1}^k{p}_i^{v_i}$.

Because each $y_i\equiv x_i^2(modn)$, $x^2\equiv y^2(modn)$. If $x\equiv y(modn)$, then find some more $𝐁$-smoothnumbers and try again. If $x$ is not congruent to $y$ modulo$n$, then $(x+y)$ and $(x-y)$ are factors of $n$.

Example

Consider the number $n=16843009$ The integer nearest itssquare root is $4104$. Given the factor base

$$𝐁=\{2,3,5,7,13\}$$

, the first few $𝐁$-smooth valuesof $y_i=f(x_i)=x_i^2-n$ are:

Using $x_0=4241$ and $x_1=4497$, one obtains:

$$y_0=1143072=2^5\cdot 3^6\cdot 5^0\cdot 7^2\cdot {13}^0$$

$$y_1=3380000=2^5\cdot 3^0\cdot 5^4\cdot 7^0\cdot {13}^2$$

Which results in:

$$x=4241\cdot 4497=19071777$$

$$y=2^5\cdot 3^3\cdot 5^2\cdot 7^1\cdot {13}^1=1965600$$

From there:

$$\gcd (x-y,n)=257$$

$$\gcd (x+y,n)=65537$$

It may not be completely obvious why we required that$n$ be a quadratic residue of each $p_i$ in thefactor base $𝐁$. One mightintuitively think that we actually want the $p_i$ tobe quadratic residues of $n$ instead. But, that isnot the case.

We are trying to express $n$ as:

$$(x+y)(x-y)=x^2-y^2=n$$

where

$$y=\prod _{i=1}^k{p}_i^{v_i}$$

Because we end up squaring $y$, there is no reasonthat the $p_i$ would need to be quadratic residuesof $n$.

So, why do we require that $n$ be a quadratic residueof each $p_i$? We can rewrite the $x^2-y^2=n$ as:

$$x^2-\prod _{i=1}^k{p}_i^{2v_i}=n$$

If we take that expression modulo $p_i$ for any $p_i$for which the corresponding $v_i$ is non-zero, we areleft with:

$$x^2\equiv n(mod{p}_i)$$

Thus, in order for $p_i$ to show up in a usefulsolution, $n$ must be a quadratic residue of $p_i$.We would be wasting time and space to employ otherprimes in our factoring and linear combinations.