Cryptography Reference
In-Depth Information
2
2
8
Example 6.11
A much more difficult example is the Fermat number
F
8
=
1.
This number was known to be composite long ago but remained unfactored until
1980 when Brent and Pollard factored it by means of the rho method [41], which
constitutes the greatest success of this algorithm. They used several modifications of
the method, one of them being a specific improvement that took advantage of the fact
that the prime factors of a Fermat number
F
k
=
+
2
2
k
1 are congruent to 1 modulo
2
k
+
2
(see [60, Theorem 1.3.5] and the discussion on how to choose the function
F
in [60, p. 231]). Now, we use the basic Pollard rho algorithm on this number and we
obtain:
+
> RhoFactor(2ˆ(2ˆ8)+1);
1238926361552897
This completely factors
F
8
because the remaining cofactor is a 62-digit prime
as can easily be checked by using a primality test. The fact that this factorization
can now easily be accomplished with Maple on a home computer bears testimony to
the enormous advances (indeed exponential because of Moore's law) in computing
power during the last years. One should bear in mind, however, that the rho method
is probabilistic and a “chance factor” will influence the actual time taken to factor a
number in each run of the algorithm.
Exercise 6.14
In their factorization of
F
8
[41], Brent and Pollard applied a heuristic
argument of the latter that says that if the factors
p
satisfy
p
≡
1
(
mod
m
)
then
the use of the polynomial
x
m
b
(instead of
x
2
+
+
b
) for the function
F
reduces the
expected number of steps in the rho method by a factor of
√
m
−
1. In the case of
F
8
,
the polynomial
x
2
10
+
=
1 and the initial value
s
3 were used. Modify the function
RhoFactor
so that it uses the polynomial
x
1024
+
1 and either
s
=
3or
s
equal to
a random value in
[
2
,
n
−
1
]
and use it to factor
F
8
in a matter of seconds.
6.4.3 Fermat's Factorization Method
We will now describe a factoring algorithm that, although rather old and of expo-
nential complexity, contains the basic idea on which the fastest currently known
factorization methods are based. This wonderful idea is due to Fermat and it starts
with the basic remark that, given a composite integer
n
, if we are able to write it as
a difference of squares:
x
2
y
2
n
=
−
,
where
x
and
y
are non-consecutive integers, then we have a nontrivial factorization
of
n
:
n
=
(
x
+
y
)(
x
−
y
).
Proposition 6.2
Let n be an odd positive integer. Then there exists a bijective cor-
respondence between factorizations
