## Dixon's Factorization Method

In order to find Integers and such that

 (1)

(a modified form of Fermat's Factorization Method), in which case there is a 50% chance that is a Factor of , choose a Random Integer , compute
 (2)

and try to factor . If is not easily factorable (up to some small trial divisor ), try another . In practice, the trial s are usually taken to be , with , 2, ..., which allows the Quadratic Sieve Factorization Method to be used. Continue finding and factoring s until are found, where is the Prime Counting Function. Now for each , write
 (3)

and form the Exponent Vector
 (4)

Now, if are even for any , then is a Square Number and we have found a solution to (1). If not, look for a linear combination such that the elements are all even, i.e.,

 (5)

 (6)

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

Gaussian Elimination can then be used to solve
 (8)

for , where is a Vector equal to (mod 2). Once is known, then we have
 (9)

where the products are taken over all for which . Both sides are Perfect Squares, so we have a 50% chance that this yields a nontrivial factor of . If it does not, then we proceed to a different 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 .

References

Bressoud, D. M. Factorization and Prime 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.