Dixon's factorization method

Template:Short description 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. We explain the basic idea here by first describing Fermat's factorization method, then how Dixon's method proceeds differently.

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 nontrivial perfect square (in the integers):

$x^2\equiv y^2(\text{mod }N),x\equiv ̸\pm y(\text{mod }N).$

For example, if Template:Nowrap, (by starting at 292, the first number greater than Template:Radic and counting up) the Template:Nowrap is 256, the square of 16. So Template:Nowrap. Computing the greatest common divisor of Template:Nowrap 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 Template:Radic squares less than N.

Dixon's method replaces the condition "is a nontrivial perfect square" 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 7-smooth and 30-smooth, respectively, since they are B-smooth with respect to some bound B.)

Once enough of these B-smooth values are found, linear algebra can be used to search for nontrivial perfect squares for Fermat's factorization method. If there are many numbers $a_1\dots a_n$ whose squares can be factorized as $a_i^{2}modN=\prod _{j=1}^m{b}_j^{e_{ij}}$ for a fixed set $b_1\dots b_m$ of small primes, linear algebra modulo 2 on the matrix $e_{ij}$ will give 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 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 we can write, for suitable exponents a_i,

$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, 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:

$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}}(\mathrm{mod}N)(\text{where }{a}_{i,1}+a_{i,2}+\cdots +a_{i,k}\equiv 0(\mathrm{mod}2))$

This yields a congruence of squares of the form Template:Nowrap which can be turned into a factorization of N, Template:Nowrap This factorization might turn out to be trivial (i.e. Template:Nowrap), which can only happen if Template:Nowrap 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

This section is taken directly from Dixon (1981).

Dixon's algorithm

Initialization. Let L be a list of integers in the range [1, n], and let P = {p₁, ..., p_h} be the list of the h primes ≤ v. Let B and Z be initially empty lists (Z will be indexed by B).

Step 1. If L is empty, exit (algorithm unsuccessful). Otherwise, take the first term z from L, remove it from L, and proceed to Step 2.

Step 2. Compute w as the least positive remainder of z² mod n. Factor w as:

$w=w^{\prime }\prod _i{p}_i^{a_i}$

where Template:Prime has no factor in P. If Template:Prime = 1, proceed to Step 3; otherwise, return to Step 1.

Step 3. Let a ← (a₁, ..., a_h). Add a to B and z to Z. If B has at most h elements, return to Step 1; otherwise, proceed to Step 4.

Step 4. Find the first vector c in B that is linearly dependent (mod 2) on earlier vectors in B. Remove c from B and $z_c$ from Z. Compute coefficients $f_b$ such that:

$𝐜\equiv \sum _{b\in B}{f}_b𝐛(\mathrm{mod}2)$

Define:

$𝐝=(d_1,\dots ,d_n)\leftarrow \frac{1}{2}(𝐜+\sum f_b𝐛)$

Proceed to Step 5.

Step 5. Compute:

$x\leftarrow z_c\prod _b{z}_b^{f_b},y\leftarrow \prod _i{p}_i^{d_i}$

so that:

$x^2\equiv \prod _i{p}_i^{2d_i}=y^{2}modn.$

If $x\equiv y$ or $x\equiv -y(\mathrm{mod}n)$, return to Step 1. Otherwise, return:

$gcd(n,x+y)$

which provides a nontrivial factor of n, and terminate successfully.

Step-by-step example

In this example, we factorize (n = 84923) using Dixon's algorithm. This example is lightly adapted from the LeetArxiv substack. Credit is given to the original author.

• Initialization:
  • Define a list of numbers L, ranging from 1 to 84923:

$L=\{1,\dots ,84923\}$

• Define a value v, which is the smoothness factor:

$v=7$

• Define a list P containing all the prime numbers less than or equal to v:

$P=2,3,5,7$

• Define B and Z, two empty lists. B is a list of powers, while Z is a list of accepted integers:

$B=[]$

$Z=[]$

• Step 1: Iterating $z$ values
  • Start a for loop that indexes the list $L$. The current element in $L$ is labeled as $z$. The for loop exits at the end of the list, or when Step 5 breaks the loop.

int n = 84923;
for (int i = 1; i <= n; i++)
{
    int z = i;
    // Remaining steps go here.
    // Step 4 can trigger Step 5.
    // Step 5 can break the loop.
}

• Step 2: Computing $z^{2}modn$ and v-smooth Prime Factorization
  • To proceed, compute $z^{2}mod84923$ for each z, then express the result as a prime factorization.

$1^{2}mod84923\equiv 1mod84923=2^0\cdot 3^0\cdot 5^0\cdot 7^{0}mod84923$

$⋮$

$513^{2}mod84923=8400mod84923=2^4\cdot 3^1\cdot 5^2\cdot 7^{1}mod84923$

$⋮$

$537^{2}mod84923=33600mod84923=2^6\cdot 3^1\cdot 5^2\cdot 7^{1}mod84923$

$538^{2}mod84923=34675mod84923=5^2\cdot 19^1\cdot 73^{1}mod84923$

This step continues for all values of z in the range.

• Step 3: Appending v-smooth results
  • If $z^{2}mod84923$ is 7-smooth, then append its powers to list $B$ and append $z$ to list $Z$.
  • If $B$ has at most $h=4$ elements, return to Step 1. Otherwise, proceed to Step 4.
  • For example, after 537 iterations, we have:

$Z=\{1,\dots ,513,537\}$

$B=\{[0,0,0,0],\dots ,[4,1,2,1],[6,1,2,1]\}$

and we proceed on to Step 4 since we would have more than $h=4$ vectors in $B$.

• Step 4: This step is split into two parts.
  • Part 1: Finding $B$ modulo 2

$B=\left(\begin{array}{cccc}0& 0& 0& 0\\ 4& 1& 2& 1\\ 6& 1& 2& 1\end{array}\right)mod2\equiv B=\left(\begin{array}{cccc}0& 0& 0& 0\\ 0& 1& 0& 1\\ 0& 1& 0& 1\end{array}\right)$

• Part 2: Finding a row combination of $B$ that sums to even numbers

For example, summing Row $2$ and Row $3$ gives us a vector of even numbers.

$R_2=\{0,1,0,1\}$ and $R_3=\{0,1,0,1\}$

then

$R_2+R_3=\{0,1,0,1\}+\{0,1,0,1\}$

$R_2+R_3=\{0,2,0,2\}$.

• Step 5: This step is split into four parts.
  • Part 1: Computing x
    • Multiply the corresponding $z$ values for the rows found in Step 4, mod $n$ to get $x$.

Rows 2 and 3 correspond with 513 and 537, so $x=(513\cdot 537)=20712mod84923$

• Part 2: Computing $y$

• Add the rows found in Step 4.
• Divide by 2. (Since these represent exponents, this effectively takes a square root.)
• Apply as exponents to the primes in $P$ to get $y$.
• Return to Step 1 if $x=\pm y$.

Find the half the sum of Rows 2 and 3:

$\begin{array}{ccccc}& 4& 1& 2& 1\\ +& 6& 1& 2& 1\\ & 10& 2& 4& 2\\ ÷2\\ & 5& 1& 2& 1\end{array}$

Apply those as exponents to $P=\{2,3,5,7\}$:

$y=2^5\cdot 3^1\cdot 5^2\cdot 7^1=16800$

• Since $x\ne \pm y$, we proceed to Part 3.

• Part 3: Computing $x+y$ and $x-y$ where $x=20712$ and $y=16800$

$x+y=20712+16800=37512$

$x-y=20712-16800=3912$

• Part 4: Computing $gcd(x+y,n)$ and $gcd(x-y,n)$ where $n=84923$, $x+y=292281$ and $x-y=258681$

$\begin{array}{c}gcd(37512,84923)=521\\ gcd(3912,84923)=163\end{array}$

Quick check shows $84923=521\cdot 163$.

The pseudocode says to only calculate $x+y$ and return $gcd(x+y,n)$. This is because it is the faster GCD to compute, and once you have it, dividing $n$ by the result is faster than computing $gcd(x-y,n)$.

Optimizations

The quadratic sieve is an optimization of Dixon's method. It selects values of x close to the square root of Template:Var 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(\exp \left(2\sqrt{2}\sqrt{\log n\log \log n}\right))$

in big-O notation, or

$L_n[1/2,2\sqrt{2}]$

in L-notation.