Editing Dixon's factorization method (section)

==Method==
Suppose the composite number ''N'' is being factored. Bound ''B'' is chosen, and the ''[[factor base]]'' is identified (which is called ''P''), the set of all primes less than or equal to ''B''. Next, positive integers ''z'' are sought such that ''z''<sup>2</sup>&nbsp;mod&nbsp;''N'' is ''B''-smooth. Therefore we can write, for suitable exponents ''a<sub>i</sub>'',

: <math>z^2 \text{ mod } N = \prod_{p_i\in P} p_i^{a_i}</math>

When enough of these relations have been generated (it is generally sufficient that the number of relations be a few more than the size of ''P''), the methods of [[linear algebra]], such as [[Gaussian elimination]], can be used to multiply together these various relations in such a way that the exponents of the primes on the right-hand side are all even:

: <math>{z_1^2 z_2^2 \cdots z_k^2 \equiv \prod_{p_i\in P} p_i^{a_{i,1}+a_{i,2}+\cdots+a_{i,k}}\ \pmod{N}\quad (\text{where } a_{i,1}+a_{i,2}+\cdots+a_{i,k} \equiv 0\pmod{2}) }</math>

This yields a [[congruence of squares]] of the form {{nowrap|''a''<sup>2</sup> ≡ ''b''<sup>2</sup> (mod ''N''),}} which can be turned into a factorization of ''N'', {{nowrap|''N'' {{=}} [[Greatest common divisor|gcd]](''a'' + ''b'', ''N'') × (''N''/gcd(''a'' + ''b'', ''N'')).}} This factorization might turn out to be trivial (i.e. {{nowrap|''N'' {{=}} ''N'' × 1}}), which can only happen if {{nowrap|''a'' ≡ ±''b'' (mod ''N''),}} in which case another try must be made with a different combination of relations; but if a nontrivial pair of factors of ''N'' is reached, the algorithm terminates.