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: SpringerVerlag, pp. 102104, 1989.
Dixon, J. D. ``Asymptotically Fast Factorization of Integers.'' Math. Comput. 36, 255260, 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. 673715, 1990.
Pomerance, C. ``A Tale of Two Sieves.'' Not. Amer. Math. Soc. 43, 14731485, 1996.
© 19969 Eric W. Weisstein
19990524