Editing Quadratic sieve (section)

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