Editing Dixon's factorization method (section)

==Basic idea==
Dixon's method is based on finding a [[congruence of squares]] modulo the integer N which is intended to factor. [[Fermat's factorization method]] finds such a congruence by selecting random or [[pseudo-random]] ''x'' values and hoping that the integer ''x''<sup>2</sup>&nbsp;mod&nbsp;N is a [[square number|perfect square]] (in the integers):

:<math>x^2\equiv y^2\quad(\hbox{mod }N),\qquad x\not\equiv\pm y\quad(\hbox{mod }N).</math>

For example, if {{nowrap|''N'' {{=}} 84923}}, (by starting at 292, the first number greater than {{radic|''N''}} and counting up) the {{nowrap|505<sup>2</sup> mod 84923}} is 256, the square of 16. So {{nowrap|(505 &minus; 16)(505 + 16) {{=}} 0 mod 84923}}.  Computing the [[greatest common divisor]] of {{nowrap|505 &minus; 16}} and ''N'' using [[Euclid's algorithm]] gives 163, which is a factor of ''N''.

In practice, selecting random ''x'' values will take an impractically long time to find a congruence of squares, since there are only {{radic|''N''}} squares less than ''N''.

Dixon's method replaces the condition "is the square of an integer" with the much weaker one "has only small prime factors"; for example, there are 292 squares smaller than 84923; 662 numbers smaller than 84923 whose prime factors are only 2,3,5 or 7; and 4767 whose prime factors are all less than 30. (Such numbers are called ''[[Smooth number|B-smooth]]'' with respect to some bound ''B''.)

If there are many numbers <math>a_1 \ldots a_n</math> whose squares can be factorized as <math>a_i^2 \mod N = \prod_{j=1}^m b_j^{e_{ij}}</math> for a fixed set <math>b_1 \ldots b_m</math> of small primes, linear algebra modulo 2 on the matrix <math>e_{ij}</math> will give a subset of the <math>a_i</math> whose squares combine to a product of small primes to an even power &mdash; that is, a subset of the <math>a_i</math> whose squares multiply to the square of a (hopefully different) number mod N.