Editing Quadratic sieve (section)

===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.