Cryptography Reference
In-Depth Information
composite. This list will give the complete prime factorization of
n
provided that the
second largest prime factor of
n
is smaller than 2
28
and this will always be the case if
all the factors appearing in the list are
2
56
will be
completely factored. When the last integer in the list is composite, the factorization
is not complete and the function will then print a message informing that this has
happened.
2
56
. In particular, all integers
n
≤
≤
> TrialDivisionFactor := proc(n::posint)
local s, p, t, r, f;
if isprime(n) or n=1 then
return [n]
end if;
s := isqrt(n);
t:=n;
r:=1;
f:=[];
for p in primearray while r <> 0 and p <= s do
r := modp(n, p);
while r=0do
t := iquo(t, p);
f := [op(f), p];
r := modp(t, p);
if isprime(t) then
return [op(f), t]
end if
end do;
end do;
printf("Incomplete factorization:");
[op(f), t]
end proc:
Example 6.8
We start with a historical example that illustrates the dangers of mak-
ing predictions about the future of factoring. In his 1874 treatise
The Principles of
Science: A Treatise on Logic and Scientific Method
, the English economist, logician
and statistician Jevons stated:
"Can the reader say what two numbers multiplied
together will produce the number
8616460799? I think it unlikely that anyone but
myself will ever know." The number was already factored by D.N. Lehmer in 1903
and, as Knuth remarked in [115, p. 388], Fermat could have factored it in less than 10
minutes on the back of an envelope. We will see later the method that Fermat would
have used but now we just remark that, with a computer, the above method factors
this number in a tiny fraction of a second:
> TrialDivisionFactor(8616460799);
[89681, 96079]
Example 6.9
Another famous historical example of an integer factorization also
happened in 1903. In the eighteenth century, the French monk and mathematician
Mersenne gave a list of all the primes of the form 2
p
257.
The primes of this form are now called
Mersenne primes
and Mersenne's list had a
few errors because it contained some composites while some primes were missing.
Among the numbers included was
M
67
=
−
1, with
p
prime, for
p
≤
2
67
1. At a 1903meeting of the American
Mathematical Society, F.N. Cole showed that this number is the product of two
specific primes by first raising 2 to the 67th power and subtracting 1, and then
multiplying the two primes to show that the result was precisely
M
67
. All these
−
