Dixon's factorization method

In number theory, Dixon's factorization method (also Dixon's random squares method^[1] 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.

The algorithm was designed by John D. Dixon, a mathematician at Carleton University, and was published in 1981.^[2]

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 x² mod N is a perfect square (in the integers):

$x^{2}\equiv y^{2}\quad ({\hbox{mod }}N),\qquad x\not \equiv \pm y\quad ({\hbox{mod }}N).$

For example, if N = 84923, we notice (by starting at 292, the first number greater than √N and counting up) that 505² 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 $a_{1}\ldots a_{n}$ whose squares can be factorized as $a_{i}^{2}\mod N=\prod _{{j=1}}^{m}b_{j}^{{e_{{ij}}}}$ for a fixed set $b_{1}\ldots b_{m}$ of small primes, linear algebra modulo 2 on the matrix $e_{ij}$ will give us a subset of the $a_{i}$ whose squares combine to a product of small primes to an even power — that is, a subset of the $a_{i}$ whose squares multiply to the square of a (hopefully different) number mod N.

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 z² mod N is B-smooth. We can therefore write, for suitable exponents a_k,

$z^{2}\equiv \prod _{{p_{i}\in P}}p_{i}^{{a_{i}}}{\pmod {N}}$

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:

${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}})}$

This gives us a congruence of squares of the form a² ≡ b² (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 $\left\lceil {\sqrt {84923}}\right\rceil =292$ and N whose squares are B-smooth. Suppose that two of the numbers we find are 513 and 537:

$513^{2}\mod 84923=8400=2^{4}\cdot 3\cdot 5^{2}\cdot 7$

$537^{2}\mod 84923=33600=2^{6}\cdot 3\cdot 5^{2}\cdot 7$

So

$(513\cdot 537)^{2}\mod 84923=2^{{10}}\cdot 3^{2}\cdot 5^{4}\cdot 7^{2}$

Then

${\begin{aligned}&{}\qquad (513\cdot 537)^{2}\mod 84923=(275481)^{2}\mod 84923\\&=(84923\cdot 3+20712)^{2}\mod 84923\\&=(84923\cdot 3)^{2}+2\cdot (84923\cdot 3\cdot 20712)+20712^{2}\mod 84923\\&=0+0+20712^{2}\mod 84923\end{aligned}}$

That is, $20712^{2}\mod 84923=(2^{5}\cdot 3\cdot 5^{2}\cdot 7)^{2}\mod 84923=16800^{2}\mod 84923.$

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 x² 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 $\log _{2}z$ 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 $N^{{1/a}}$ with probability about $a^{{-a}}$ (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 $\exp \left({\sqrt {\log N\log \log N}}\right)$.

The optimal complexity of Dixon's method is

$O\left(\exp \left(2{\sqrt 2}{\sqrt {\log n\log \log n}}\right)\right)$

in big-O notation, or

$L_{n}[1/2,2{\sqrt 2}]$

in L-notation.

References

1. Kleinjung, Thorsten; et al. (2010). "Factorization of a 768-bit RSA modulus". Advances in Cryptology – CRYPTO 2010. Lecture Notes in Computer Science. 6223. pp. 333–350. doi:10.1007/978-3-642-14623-7_18.
2. Dixon, J. D. (1981). "Asymptotically fast factorization of integers". Math. Comp. 36 (153): 255–260. doi:10.1090/S0025-5718-1981-0595059-1. JSTOR 2007743.