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

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

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

${\displaystyle z^{2}{\text{ mod }}N=\prod _{p_{i}\in P}p_{i}^{a_{i}}}$

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 can be used (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:

${\displaystyle {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 yields 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 another try has to be made with a different combination of relations; but a nontrivial pair of factors of N can be reached, and the algorithm will terminate.

Pseudocode

input: positive integer ${\textstyle N}$
output: non-trivial factor of ${\textstyle N}$

Choose bound ${\textstyle B}$
Let ${\textstyle P:=\{p_{1},p_{2},\ldots ,p_{k}\}}$ be all primes ${\textstyle \leq B}$

repeat
    for ${\textstyle i=1}$ to ${\textstyle k+1}$ do
        Choose ${\textstyle 0<z_{i}<N}$ such that ${\textstyle z_{i}^{2}{\text{ mod }}N}$ is ${\textstyle B}$-smooth
        Let ${\textstyle a_{i}:=\{a_{i1},a_{i2},\ldots ,a_{ik}\}}$ such that ${\textstyle z_{i}^{2}{\text{ mod }}N=\prod _{p_{j}\in P}p_{j}^{a_{ij}}}$
    end for

    Find non-empty ${\textstyle T\subseteq \{1,2,\ldots ,k+1\}}$ such that ${\textstyle \sum _{i\in T}a_{i}\equiv {\vec {0}}{\pmod {2}}}$
    Let ${\textstyle x:=\left(\prod _{i\in T}z_{i}\right){\text{ mod }}N}$
        ${\textstyle y:=\left(\prod _{p_{j}\in P}p_{j}^{\left(\sum _{i\in T}a_{ij}\right)/2}\right){\text{ mod }}N}$
while ${\textstyle x\equiv \pm y{\pmod {N}}}$ 

return ${\textstyle \gcd(x+y,N)}$

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 ${\displaystyle \left\lceil {\sqrt {84923}}\right\rceil =292}$ and N whose squares mod N are B-smooth. Suppose that two of the numbers found are 513 and 537:

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

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

So

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

Then

${\displaystyle {\begin{aligned}&{}(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, ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle N^{1/a}}$ with probability about ${\displaystyle 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 ${\displaystyle \exp \left({\sqrt {\log N\log \log N}}\right)}$.

The optimal complexity of Dixon's method is

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

in big-O notation, or

${\displaystyle 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. ISBN 978-3-642-14622-0.
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.