Quadratic Sieve

Question

Can anyone explain how Quadratic Sieve (factorization algorithm) works?

I tried reading relevant articles but they didn't include clear explanation / implementation of it.

Answer 1

This is an outline, an actual implementation is more complicated.

You want to factor $m$ where $m = pq$ , $p$ and $q$ are primes.

if $x^2 - y^2 = m$ then $(x-y)(x+y) = m$ so $(x-y)$ and $(x+y)$ are factors of $m$.

if $x^2 - y^2 = km$ then $(x-y)(x+y) = km$ so $(x-y)$ and $(x+y)$ could contain a single factor of $m$ each. One of them could contain all of $m$ which is useless.There are many more ways to find a solution to this problem.

The quadratic sieve tries to construct $x$ and $y$ so that $x^2 - y^2 = km$ then check if $(x-y)$ or $(x+y)$ has one common factor with $m$.

It generates many $x_n$ by $x_n = \lfloor \sqrt{m} \rfloor + n$ , $n = 1\dots$

$x_n^2 - km = (\lfloor \sqrt{m} \rfloor + n)^2 -km = p_1p_2\dots p_a \tag 1$

The right side is factored into primes.

By selecting some of the equations to match the primes so that there is an even power of each of them and multiplying the equations together it gets:

$$(x_1x_2\dots x_b)^2 - p_1^{2k_1}p_2^{2k_2}\dots p_a^{2k_a} = Km$$

$(x_1x_2\dots x_b)^2 - (p_1^{k_1}p_2^{k_2}\dots p_a^{k_a})^2 = Km \tag 2$

Then it tests if $(x_1x_2\dots x_b - p_1^{k_1}p_2^{k_2}\dots p_a^{k_a})$ or $(x_1x_2\dots x_b + p_1^{k_1}p_2^{k_2}\dots p_a^{k_a})$ has one common factor with $m$. The greatest common divisor (gcd) algorithm is used.

In practice a factor base is used. This limits the set of primes $p_1\dots p_{max}$ that are used.If the right side of $(1)$ contains factors not in the factor base then that equation is rejected. Sieving methods ensure that only small primes are needed in the factor base i.e. smoothness.

---

Example: Let $m = 253 =11*23$, $\lfloor \sqrt{m} \rfloor = 15$

\begin{array}{|c|c|c|c|c|c|} \hline n & x_n & x_n^2-km & factors & odd\ power & comment\\ \hline 1 & 16 & 3 & 3 & 3 & \\ \hline 2 & 17 & 36 & 2,2,3,3 & & is\ square\\ \hline 3 & 18 & 71 & 71 & 71 & too\ large\\ \hline 4 & 19 & 108 & 2,2,3,3,3 & 3 & \\ \hline 5 & 20 & 147 & 3,7,7 & 3 & \\ \hline \end{array}

Row 2 is square but for the sake of the demonstration lets ignore it.

The odd power column contains primes that have an odd power.

Multiplying rows 1 and 4 will give $3^2$ evening up the powers.

$x = x_1x_4 = 16.19 = 304$ , $y = \sqrt{3.108} = 2.3^2 = 18$

$gcd(x-y,m) = gcd(304-18,253) = 11$

$gcd(x+y,m) = gcd(304+18,253) = 23$