# quadratic sieve

## Algorithm

To factor a number $n$ using the quadratic sieve^{}, one seeks
two numbers $x$ and $y$ which are not congruent modulo $n$
with $x$ not congruent^{} to $-y$ modulo $n$ but
have ${x}^{2}\equiv {y}^{2}\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$. If two such numbers are found,
one can then say that $(x+y)(x-y)\equiv 0\phantom{\rule{veryverythickmathspace}{0ex}}(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 able
to create a set of numbers whose factorization can be expressed
as a product^{} of pre-chosen primes. These factorizations are
recorded as vectors of the exponents. Once enough vectors are
collected to form a set which contains a linear dependence,
this linear dependence is exploited to find two squares which
are equivalent^{} modulo $n$.

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

Once $k+1$ of these vectors have been collected, there must be
a linear dependence among them. The $k+1$ vectors are taken
modulo $2$ to form vectors in ${\mathbb{Z}}_{2}^{k}$. The linear dependence
among them is used to find a combination^{} of the vectors which
sum up to the zero vector^{} in ${\mathbb{Z}}_{2}^{k}$. Summing these vectors
is 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 $\mathbf{B}=\{{p}_{1},{p}_{2},\mathrm{\dots},{p}_{k}\}$ such that $2\in \mathbf{B}$ and for each odd
prime ${p}_{j}$ in $\mathbf{B}$, $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}\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$. If ${y}_{i}$ can be
completely factored by numbers in $\mathbf{B}$, then it is called
$\mathbf{B}$-smooth. If it is not $\mathbf{B}$-smooth, then discard ${x}_{i}$ and
${y}_{i}$ and move on to a new choice of ${x}_{i}$. If it is $\mathbf{B}$-smooth,
then store ${x}_{i}$, ${y}_{i}$, and the vector of its exponents for
the primes in $\mathbf{B}$. Also, record a copy of the exponent vector
with each component taken modulo $2$.

Once $k+1$ vectors have been recorded, there must be a linear dependence among them. Using the copies of the exponent vectors that were taken modulo $2$, determine which ones can be added together 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 chosen vectors to form a new vector $\overrightarrow{v}$. Every component of this 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}\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$, ${x}^{2}\equiv {y}^{2}\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$. If $x\equiv y\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$, then find some more $\mathbf{B}$-smooth numbers 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 its square root is $4104$. Given the factor base

$$\mathbf{B}=\{2,3,5,7,13\}$$ |

, the first few $\mathbf{B}$-smooth values of ${y}_{i}=f({x}_{i})={x}_{i}^{2}-n$ are:

${x}_{i}$ | ${y}_{i}=f({x}_{i})$ | 2 | 3 | 5 | 7 | 13 |
---|---|---|---|---|---|---|

4122 | 147875 | 0 | 0 | 3 | 1 | 2 |

4159 | 454272 | 7 | 1 | 0 | 1 | 2 |

4187 | 687960 | 3 | 3 | 1 | 2 | 1 |

4241 | 1143072 | 5 | 6 | 0 | 2 | 0 |

4497 | 3380000 | 5 | 0 | 4 | 0 | 2 |

4993 | 8087040 | 9 | 5 | 1 | 0 | 1 |

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:

$$\mathrm{gcd}(x-y,n)=257$$ |

$$\mathrm{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 the factor base $\mathbf{B}$. One might intuitively think that we actually want the ${p}_{i}$ to be quadratic residues of $n$ instead. But, that is not 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 reason that the ${p}_{i}$ would need to be quadratic residues of $n$.

So, why do we require that $n$ be a quadratic residue of each ${p}_{i}$? We can rewrite the ${x}^{2}-{y}^{2}=n$ as:

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

If we take that expression modulo ${p}_{i}$ for any ${p}_{i}$ for which the corresponding ${v}_{i}$ is non-zero, we are left with:

$${x}^{2}\equiv n\phantom{\rule{veryverythickmathspace}{0ex}}(mod{p}_{i})$$ |

Thus, in order for ${p}_{i}$ to show up in a useful
solution, $n$ must be a quadratic residue of ${p}_{i}$.
We would be wasting time and space to employ other
primes in our factoring and linear combinations^{}.

Title | quadratic sieve |
---|---|

Canonical name | QuadraticSieve |

Date of creation | 2013-03-22 12:48:14 |

Last modified on | 2013-03-22 12:48:14 |

Owner | patrickwonders (217) |

Last modified by | patrickwonders (217) |

Numerical id | 9 |

Author | patrickwonders (217) |

Entry type | Algorithm^{} |

Classification | msc 11Y05 |

Classification | msc 11A51 |