Editing Dixon's factorization method (section)

==Pseudocode==
This section is taken directly from Dixon (1981).

'''Dixon's algorithm'''

''Initialization.'' Let ''L'' be a list of integers in the range [1, ''n''], and let ''P'' = {''p''<sub>1</sub>, ..., ''p''<sub>h</sub>} be the list of the ''h'' primes ≤ ''v''. Let ''B'' and ''Z'' be initially empty lists (''Z'' will be indexed by ''B'').

'''Step 1.''' If ''L'' is empty, exit (algorithm unsuccessful). Otherwise, take the first term ''z'' from ''L'', remove it from ''L'', and proceed to Step 2.

'''Step 2.''' Compute ''w'' as the least positive remainder of ''z<sup>2</sup> mod n''. Factor ''w'' as:

<math>w = w' \prod_i p_i^{a_i}</math>

where ''{{prime|w}}'' has no factor in ''P''. If ''{{prime|w}}'' = 1, proceed to Step 3; otherwise, return to Step 1.

'''Step 3.''' Let ''a'' ← (''a''<sub>1</sub>, ..., ''a''<sub>h</sub>). Add ''a'' to ''B'' and ''z'' to ''Z''. If ''B'' has at most ''h'' elements, return to Step 1; otherwise, proceed to Step 4.

'''Step 4.''' Find the first vector ''c'' in ''B'' that is linearly dependent (mod 2) on earlier vectors in ''B''. Remove ''c'' from ''B'' and <math>z_c</math> from ''Z''. Compute coefficients <math>f_b</math> such that:

<math>\mathbf{c} \equiv \sum_{b \in B} f_b \mathbf{b} \pmod{2}</math>

Define:

<math>\mathbf{d} = (d_1, \dots, d_n) \gets \frac{1}{2} \left(\mathbf{c} + \sum f_b \mathbf{b} \right)</math>

Proceed to Step 5.

'''Step 5.''' Compute:

<math>x \gets z_c \prod_b z_b^{f_b}, \quad y \gets \prod_i p_i^{d_i}</math>

so that:

<math>x^2 \equiv \prod_i p_i^{2d_i} = y^2 \mod n.</math>

If <math>x \equiv y</math> or <math>x \equiv -y \pmod{n}</math>, return to Step 1. Otherwise, return:

<math>\gcd(n, x + y)</math>

which provides a nontrivial factor of ''n'', and terminate successfully.