In number theory, Dixon's factorization method (also Dixon's random squares method or Dixon's algorithm) is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run-time bound comes with a rigorous proof that does not rely on conjectures about the smoothness properties of the values taken by a polynomial.
The algorithm was designed by John D. Dixon, a mathematician at Carleton University, and was published in 1981.
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"2 mod N is a perfect square (in the integers):
formula_1
For example, if "N" 
 84923, (by starting at 292, the first number greater than √"N" and counting up) the 5052 mod 84923 is 256, the square of 16. So (505 − 16)(505 + 16) 
 0 mod 84923. Computing the greatest common divisor of 505 − 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 √"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 "B-smooth" with respect to some bound "B".)
If there are many numbers formula_2 whose squares can be factorized as formula_3 for a fixed set formula_4 of small primes, linear algebra modulo 2 on the matrix formula_5 will give a subset of the formula_6 whose squares combine to a product of small primes to an even power — that is, a subset of the formula_6 whose squares multiply to the square of a (hopefully different) number mod N.
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"2 mod "N" is "B"-smooth. Therefore we can write, for suitable exponents "ai",
 formula_8
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:
 formula_9
This yields a congruence of squares of the form "a"2 ≡ "b"2 (mod "N"), which can be turned into a factorization of "N", "N" 
 gcd("a" + "b", "N") × ("N"/gcd("a" + "b", "N")). This factorization might turn out to be trivial (i.e. "N" 
 "N" × 1), which can only happen if "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.
Pseudocode.
 input: positive integer formula_10
 output: non-trivial factor of formula_10
 Choose bound formula_12
 Let formula_13 be all primes formula_14
 repeat
 for formula_15 to formula_16 do
 Choose formula_17 such that formula_18 is formula_12-smooth
 Let formula_20 such that formula_21
 end for
 Find non-empty formula_22 such that formula_23
 Let formula_24
 formula_25
 while formula_26 
 return formula_27
Example.
This example will try to factor "N" = 84923 using bound "B" = 7. The factor base is then "P" = {2, 3, 5, 7}. A search can be made for integers between formula_28 and "N" whose squares mod "N" are "B"-smooth. Suppose that two of the numbers found are 513 and 537:
 formula_29
 formula_30
So
 formula_31
Then
formula_32
That is, formula_33
The resulting factorization is 84923 = gcd(20712 − 16800, 84923) × gcd(20712 + 16800, 84923) = 163 × 521.
Optimizations.
The quadratic sieve is an optimization of Dixon's method. It selects values of "x" close to the square root of N such that "x2" modulo "N" is small, thereby largely increasing the chance of obtaining a smooth number.
Other ways to optimize Dixon's method include using a better algorithm to solve the matrix equation, taking advantage of the sparsity of the matrix: a number "z" cannot have more than formula_34 factors, so each row of the matrix is almost all zeros. In practice, the block Lanczos algorithm is often used. Also, the size of the factor base must be chosen carefully: if it is too small, it will be difficult to find numbers that factorize completely over it, and if it is too large, more relations will have to be collected.
A more sophisticated analysis, using the approximation that a number has all its prime factors less than formula_35 with probability about formula_36 (an approximation to the Dickman–de Bruijn function), indicates that choosing too small a factor base is much worse than too large, and that the ideal factor base size is some power of formula_37.
The optimal complexity of Dixon's method is 
formula_38
in big-O notation, or
formula_39
in L-notation.