Cryptography Reference
In-Depth Information
Fermat's method admits many variants that improve its running time. The costliest
part in each iteration of the algorithm is the “squareness test” which, in Maple,
consists of a computation of the integral part of the square root of the number followed
by its squaring to checkwhether it agrees with the number. A trick that Fermat already
knew in order to speed up this process was to look at the last digit or the last two digits
of the number r one wants to check for squareness. The last decimal digit of a square
must be one of the following: 0, 1, 4, 5, 6 or 9. Thus if the number ends in 2, 3, 7 or 8,
one already knows that it cannot be a square. Similarly, only 22 two-digit numbers
may occur as the last two decimal digits of a square. The reason is that the residue
class modulo m of a square must be a square in
Z m for each integer m
2 and, for
example, the six digits mentioned above are the squares in
Z 10 while there are only
22 squares in
Z 100 . There is no need to take 10 or 100 as the modulus and, in fact,
there are other moduli which are more advantageous for this purpose. For example,
there are only four squares in
Z 16 so checking the least non-negative residue of r
modulo 16 will detect 75% of non-squares.
In order to apply this idea to speed up Fermat's method one needs to find a
modulus m such that the ratio between the number of squares in
Z m and m is as
low as possible (we stress that here we are counting squares in
Z m and not quadratic
Z m ). Moreover, this m should not be too large because in that case the
computation of the squares would take a long time. Using the Chinese remainder
theorem and, in particular, Theorem 2.14, it is easy to see that the function that to
each m
residues in
2 assigns the number of squares in
Z m is multiplicative, i.e., if m
=
uv
Z m equals the product
with u , v , relatively prime, then the number of squares in
Z u by the number of squares in
Z v . This follows from
of the number of squares in
the isomorphism
Z m
→ Z u × Z v , in which a square in
Z m corresponds to a pair
formed by a square in
Z v . Thus the computation of the number
of squares modulo m , and also the computation of the squares themselves, reduce to
the analogous computations modulo the prime powers dividing m .
Z u and a square in
Exercise 6.16 Use Maple to compute the value of m below a given bound, which
has the smallest ratio of squares modulo m to m . Show that these ratios have values
0
720720,
respectively, and that no other value of m less than one of these has a smaller ratio.
(Hint: One may use either brute force or the function numtheory:-quadres to
compute the squares. A more efficient alternative would be to use the formulas in
[187] for the number of squares modulo a prime power and the fact that the number
of squares is a multiplicative function.)
.
038095, 0
.
020779, 0
.
011189 for m
=
5040, m
=
55440 and m
=
The preceding exercise shows that by checking the congruence class of r modulo
55440 we can detect almost 98% of the tested numbers as being non-squares. Even
more will be detected if we take 720720 as modulus at the cost of computing many
more modular squares; this would only be advantageous if the number of iterations
is very large. So we will take m
55440 for factorizations that require several
million iterations such as, for example, that of the number c2 above. The function
that does Fermat factoring with the modified squareness test that checks first whether
=
Search WWH ::




Custom Search