TOPICS
Search

Dixon's Factorization Method


In order to find integers x and y such that

 x^2=y^2 (mod n)
(1)

(a modified form of Fermat's factorization method), in which case there is a 50% chance that GCD(n,x-y) is a factor of n, choose a random integer r_i, compute

 g(r_i)=r_i^2 (mod n),
(2)

and try to factor g(r_i). If g(r_i) is not easily factorable (up to some small trial divisor d), try another r_i. In practice, the trial rs are usually taken to be |_sqrt(n)_|+k, with k=1, 2, ..., which allows the quadratic sieve factorization method to be used. Continue finding and factoring g(r_i)s until N=pid are found, where pi is the prime counting function. Now for each g(r_i), write

 g(r_i)=p_(1i)^(a_(1i))p_(2i)^(a_(2i))...p_(Ni)^(a_(Ni)),
(3)

and form the exponent vector

 v(r_i)=[a_(1i); a_(2i); |; a_(Ni)].
(4)

Now, if a_(ki) are even for any k, then g(r_i) is a square number and we have found a solution to (◇). If not, look for a linear combination sum_(i)c_iv(r_i) such that the elements are all even, i.e.,

 c_1[a_(11); a_(21); |; a_(N1)]+c_2[a_(12); a_(22); |; a_(N2)]+...+c_N[a_(1N); a_(2N); |; a_(NN)]=[0; 0; |; 0]  (mod 2)
(5)
 [a_(11) a_(12) ... a_(1N); a_(21) a_(22) ... a_(2N); | | ... |; a_(N1) a_(N2) ... a_(NN)][c_1; c_2; |; c_N]=[0; 0; |; 0]  (mod 2).
(6)

Since this must be solved only mod 2, the problem can be simplified by replacing the a_(ij)s with

 b_(ij)={0   for a_(ij) even; 1   for a_(ij) odd.
(7)

Gaussian elimination can then be used to solve

 bc=z
(8)

for c, where z is a vector equal to 0 (mod 2). Once c is known, then we have

 product_(k)g(r_k)=product_(k)r_k^2 (mod n),
(9)

where the products are taken over all k for which c_k=1. Both sides are perfect squares, so we have a 50% chance that this yields a nontrivial factor of n. If it does not, then we proceed to a different z and repeat the procedure. There is no guarantee that this method will yield a factor, but in practice it produces factors faster than any method using trial divisors. It is especially amenable to parallel processing, since each processor can work on a different value of r.


Explore with Wolfram|Alpha

References

Bressoud, D. M. Factorization and Primality Testing. New York: Springer-Verlag, pp. 102-104, 1989.Dixon, J. D. "Asymptotically Fast Factorization of Integers." Math. Comput. 36, 255-260, 1981.Lenstra, A. K. and Lenstra, H. W. Jr. "Algorithms in Number Theory." In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (Ed. J. van Leeuwen). New York: Elsevier, pp. 673-715, 1990.Pomerance, C. "A Tale of Two Sieves." Not. Amer. Math. Soc. 43, 1473-1485, 1996.

Referenced on Wolfram|Alpha

Dixon's Factorization Method

Cite this as:

Weisstein, Eric W. "Dixon's Factorization Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DixonsFactorizationMethod.html

Subject classifications