Cryptography Reference
In-Depth Information
The next function implements this algorithm inMaple. The function takes as input
the integer to be factored, and as optional inputs, the maximum number of steps to
be performed and an argument that tells the function whether to print the number of
iterations used to find the factors. The output is a sequence consisting of two factors
a
,
b
such that
n
ab
and, in case
numsteps
is set to
true
, with an additional
term indicating the number of iterations used.
=
> FermatFactor := proc(n::And(posint,odd), maxnumsteps::posint:= 10ˆ7,
{numsteps::truefalse := false})
local x, k, r, i, y;
x := isqrt(n);
if xˆ2 < n then
x:=x+1
end if;
k := 2*x+1;
r := xˆ2-n;
for i to maxnumsteps while not issqr(r) do
r := r+k;
k:=k+2
end do;
if issqr(r) then
x := (k-1)/2;
y := isqrt(r)
else
error "%1 could not be factored in %2 iterations", n, maxnumsteps
end if;
if not numsteps then
x-y, x+y
else
x-y, x+y, i
end if;
end proc:
As a first, easy example, let us try Jevons' number 8616460799:
> FermatFactor(8616460799, numsteps = true);
89681, 96079, 56
We see that the number was easily factored in 56 steps. Thus Fermat could indeed
have done it by hand, especially bearing in mind that he already knew some tricks
to speed up the verification of whether an integer is a square (we will mention these
tricks below). Next, we do a couple of experiments to test how well the number of
iterations agrees with that expected according to Proposition 6.3.
Example 6.12
We first give a Maple function to generate a composite number
n
which is the product
n
pq
of two primes
p
,
q
of the same given length and such
that the approximate length of
p
=
−
q
is also given.
> composite := proc(length, lengthdiff)
local p, q;
randomize();
p:=0;
while not isprime(p) do
p := (rand(2ˆ(length-1) .. 2ˆlength-1))()
end do;
q := nextprime(p+(rand(2ˆ(lengthdiff-1) .. 2ˆlengthdiff-1))());
p*q
end proc:
