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 (◇). 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 .