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 polynomial.
Contents
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 we intend to factor. Fermat's factorization algorithm finds such a congruence by selecting random or pseudo-random x values and hoping that the integer x2 mod N is a perfect square (in the integers):
For example, if N = 84923, we notice (by starting at 292, the first number greater than √N and counting up) that 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 us 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 we have lots of numbers
Method
Suppose we are trying to factor the composite number N. We choose a bound B, and identify the factor base (which we will call P), the set of all primes less than or equal to B. Next, we search for positive integers z such that z2 mod N is B-smooth. We can therefore write, for suitable exponents ak,
When we have generated enough of these relations (it's generally sufficient that the number of relations be a few more than the size of P), we can use the methods of linear algebra (for example, Gaussian elimination) to multiply together these various relations in such a way that the exponents of the primes on the right-hand side are all even:
This gives us a congruence of squares of the form a2 ≡ b2 (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 we have to try again with a different combination of relations; but with luck we will get a nontrivial pair of factors of N, and the algorithm will terminate.
Example
We will try to factor N = 84923 using bound B = 7. Our factor base is then P = {2, 3, 5, 7}. We then search randomly for integers between
So
Then
That is,
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
A more sophisticated analysis, using the approximation that a number has all its prime factors less than
The optimal complexity of Dixon's method is
in big-O notation, or
in L-notation.