Cryptography Reference
In-Depth Information
the residues are squares modulo 55440 is given below. This function is similar to
FermatFactor
except that before starting the iterations of the method it computes
the elements
a
∈ Z
54440
such that
a
2
Z
54440
. This is done by using
Maple's function
numtheory:-quadres
which computes a sort of “generalized
Legendre symbol” that detects squares modulo
m
. Then one starts at
x
−
n
is a square in
=
√
n
and
keeps increasing it by 1 in each iteration, while checking whether
x
mod 55440 is
one of these pre-computed values and, if this is the case, whether
x
2
−
n
is indeed
a square. This way only a small fraction of the values
x
2
−
n
need to be computed
and submitted to the
issqr
test.
> FermatFactorR := proc(n::(And(posint, odd)), maxnumsteps := 10ˆ8,
{numsteps::truefalse := false})
local x, fact, m, i, y, q;
x := isqrt(n);
if n <= xˆ2 then
x:=x-1
end if;
fact := false;
m := n mod 55440;
q := Array(0 .. 55439, proc(a) numtheory:-quadres(aˆ2-m, 55440) end proc);
for i to maxnumsteps while not fact do
x := x+1;
if q[x mod 55440] = 1 then
fact := issqr(xˆ2-n)
end if
end do;
if fact then
y := isqrt(xˆ2-n)
else
error "unable to factor %1 in %2 iterations", n, maxnumsteps
end if;
if not numsteps then
x-y, x+y
else
x-y, x+y, i-1
end if
end proc:
One can readily check that this function is more than three times faster than
FactFermat
for numbers similar to
c2
above.
Exercise 6.17
Write a Maple function to test whether an integer is a square, which
uses an array of precomputed data and is faster than
issqr
on large integers. (Hint:
The function should use a modulus like 55440 and Maple's
issqr
; it will actually
be slower than the latter on numbers that turn out to be squares but it will be much
faster on the majority of non-squares, so faster on average.)
Exercise 6.18
Experiment with variants of the procedure
FermatFactorR
based
on other moduli (like, for example, 720720) and find numbers for which these variants
are faster than
FermatFactorR
.
