Fermat's Factorization Method - Sieve Improvement

Sieve Improvement

It is not necessary to compute all the square-roots of, nor even examine all the values for . Examine the tableau for :

One can quickly tell that none of these values of b2 are squares. Squares end with 0, 1, 4, 5, 9, or 16 modulo 20. The values repeat with each increase of by 10. For this example, adding '-17' mod 20 (or 3), produces 3, 4, 7, 8, 12, and 19 modulo 20 for these values. It is apparent that only the 4 from this list can be a square. Thus, must be 1 mod 20, which means that is 1 or 9 mod 10; it will produce a b2 which ends in 4 mod 20 and, if square, will end in 2 or 8 mod 10.

This can be performed with any modulus. Using the same ,

One generally chooses a power of a different prime for each modulus.

Given a sequence of a-values (start, end, and step) and a modulus, one can proceed thus:

FermatSieve(N, astart, aend, astep, modulus)

a ← astart

do modulus times:

b2 ← a*a - N

if b2 is a square, modulo modulus:

FermatSieve(N, a, aend, astep * modulus, NextModulus)

endif

a ← a + astep

enddo

But the recursion is stopped when few a-values remain; that is, when (aend-astart)/astep is small. Also, because a's step-size is constant, one can compute successive b2's with additions.