Editing Quadratic sieve (section)

==Example of basic sieve==

This example will demonstrate standard quadratic sieve without logarithm optimizations or prime powers. Let the number to be factored <math>N = 15347</math>, therefore the ceiling of the square root of <math>N</math> is 124. Since <math>N</math> is small, the basic polynomial <math>Y(X) = (X + 124)^2 - 15347</math> is enough.

===Data collection===

Since <math>N</math> is small, only four primes are necessary.  The first four primes <math>p</math> for which 15347 has a square root mod <math>p</math> are 2, 17, 23, and 29 (in other words, 15347 is a [[quadratic residue]] modulo each of these primes). These primes will be the basis for sieving.

Now we construct our sieve <math>V_X</math> of <math>Y(X) = (X + \lceil\sqrt{N}\rceil)^2 - N = (X + 124)^2 - 15347</math> and begin the sieving process for each prime in the basis, choosing to sieve the first <math>0 \le X < 100</math> of <math>Y(X)</math>:

:<math>
\begin{align}V &= \begin{bmatrix} Y(0) & Y(1) & Y(2) & Y(3) & Y(4) & Y(5) & \cdots & Y(99) \end{bmatrix} \\
 & =\begin{bmatrix} 29 & 278 & 529 & 782 & 1037 & 1294 & \cdots & 34382 \end{bmatrix}\end{align}</math>

The next step is to perform the sieve. For each <math>p</math> in our factor base <math>\lbrace 2, 17, 23, 29\rbrace</math> solve the equation

:<math>Y(X) \equiv (X + \lceil\sqrt{N}\rceil)^2 - N \equiv 0 \pmod{p} </math>

to find the entries in the array <math>V</math> which are divisible by <math>p</math>.

For <math>p=2</math> solve <math>(X + 124)^2 - 15347 \equiv 0 \pmod{2}</math> to get the solution <math>X \equiv \sqrt{15347} - 124 \equiv 1 \pmod{2}</math>.

Thus, starting at <math>X = 1</math> and incrementing by 2, each entry will be divisible by 2.  Dividing each of those entries by 2 yields
: <math>V = \begin{bmatrix} 29 & 139 & 529 & 391 & 1037 & 647 & \cdots & 17191 \end{bmatrix}</math>

Similarly for the remaining primes <math>p</math> in <math>\lbrace 17, 23, 29\rbrace</math> the equation<math>X \equiv \sqrt{15347} - 124 \pmod{p}</math> is solved.  Note that for every <math>p > 2</math>, there will be 2 resulting linear equations due to there being 2 modular square roots.

: <math>\begin{alignat}{3}
  X \equiv \pm\sqrt{15347} - 124 \equiv &&   8  - 124 & \equiv 3 & \pmod{17} \\
                                 \equiv &&  -8  - 124 & \equiv 4 & \pmod{17} \\
  X \equiv \pm\sqrt{15347} - 124 \equiv &&   11 - 124 & \equiv 2 & \pmod{23} \\
                                 \equiv &&\,-11 - 124 & \equiv 3 & \pmod{23} \\
  X \equiv \pm\sqrt{15347} - 124 \equiv &&   8  - 124 & \equiv 0 & \pmod{29} \\
                                 \equiv &&  -8  - 124 & \equiv 13& \pmod{29} \\
\end{alignat}
</math>

Each equation <math>X \equiv a \pmod{p}</math> results in <math>V_x</math> being divisible by <math>p</math> at <math>x = a</math> and each ''p''th value beyond that.  Dividing <math>V</math> by <math>p</math> at <math>a</math>, <math>a + p</math>, <math>a + 2p</math>, <math>a + 3p</math>, etc., for each prime in the basis finds the smooth numbers which are products of unique primes (first powers).

: <math>V = \begin{bmatrix} 1 & 139 & 23 & 1 & 61 & 647 & \cdots & 17191 \end{bmatrix}</math>

Any entry of <math>V</math> that equals 1 corresponds to a smooth number. Since <math>V_0</math>, <math>V_3</math>, and <math>V_{71}</math> equal one, this corresponds to:

{| class="wikitable"
|-----
! ''X'' + 124 || ''Y'' || factors
|-----
| 124
| 29
| 2<sup>0</sup> • 17<sup>0</sup> • 23<sup>0</sup> • 29<sup>1</sup>
|-----
| 127
| 782
| 2<sup>1</sup> • 17<sup>1</sup> • 23<sup>1</sup> • 29<sup>0</sup>
|-----
| 195
| 22678
| 2<sup>1</sup> • 17<sup>1</sup> • 23<sup>1</sup> • 29<sup>1</sup>
|}

===Matrix processing===

Since smooth numbers <math>Y</math> have been found with the property <math>Y \equiv Z^2 \pmod{N}</math>, the remainder of the algorithm follows equivalently to any other variation of [[Dixon's factorization method]].

Writing the exponents of the product of a subset of the equations 
: <math>\begin{align}
29 &= 2^0 \cdot 17^0 \cdot 23^0 \cdot 29^1 \\
782 &= 2^1 \cdot 17^1 \cdot 23^1 \cdot 29^0 \\ 
22678 &= 2^1 \cdot 17^1 \cdot 23^1 \cdot 29^1 \\
\end{align}
</math>

as a matrix<math>\pmod{2}</math> yields:
: <math>
S \cdot \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix} \equiv \begin{bmatrix} 0 & 0 & 0 & 0 \end{bmatrix} \pmod{2}</math>

A solution to the equation is given by the [[Left null space#Left null space|left null space]], simply 
: <math> S = \begin{bmatrix}1 & 1 & 1 \end{bmatrix} </math>

Thus the product of all three equations yields a square modulo <math>N</math>.

: <math>29 \cdot 782 \cdot 22678 = 22678^2</math>
and
: <math>124^2 \cdot 127^2 \cdot 195^2 = 3070860^2 </math>

So the algorithm found 
: <math>22678^2 \equiv 3070860^2 \pmod{15347} </math>

Testing the result yields <math>\gcd(3070860 - 22678, 15347) = 103</math>, a nontrivial factor of 15347, the other being 149.

This demonstration should also serve to show that the quadratic sieve is only appropriate when <math>N</math> is large. For a number as small as 15347, this algorithm is overkill. [[Trial division]] or [[Pollard rho]] could have found a factor with much less computation.