Cryptography Reference
In-Depth Information
operations were done on the blackboard and Cole famously did not pronounce a
single word during his “talk”. When he was later asked by E.T. Bell, in 1911, how
long it had taken him to crack
M
67
, he answered:
“three years of Sundays”
.This
episode is a nice illustration of the fact that the factorization problem belongs to the
class
but also of the enormous advances made in the problem during the last
century—with a decisive role being played by computers. Even trial division, the
humblest of all factoring algorithms, can now factor this number very quickly:
NP
> TrialDivisionFactor(2ˆ67-1);
[193707721, 761838257287]
Exercise 6.13
Modify the function
TrialDivisionFactor
so that the array
containing the primes is computed and stored in a local variable each time the pro-
cedure is run. The size of this array should then be made dependent on the size of
the number to be factored.
6.4.2 Pollard's Rho Method and Its Maple Implementation
We are going to describe a factorization algorithm introduced by Pollard in 1975.
This algorithm is inspired by the birthday problem and, despite being exponential,
is substantially faster than trial division. Although this algorithm cannot usually be
directly used to factor numbers of cryptographic size, there are several good reasons to
study it. One of them is that it may be used as a subroutine in more powerful methods
in order to factor auxiliary numbers of small size. Another important reason is that
the rho method is the basis for a similar algorithm to compute discrete logarithms.
In the specific case of the discrete logarithm problem for elliptic curves we will see
that the strongest known attacks are based precisely on this algorithm.
The idea underlying the rhomethod is the following. Suppose that
n
is a composite
number and
F
is a random function from
Z
n
to itself that, for each prime factor
(
)
≡
(
)(
)
p
of
n
, satisfies that
F
x
F
x
mod
p
mod
p
, so that
F
factors through
Z
n
to
Z
p
and induces a function
f
: Z
p
→ Z
p
,
the canonical projection from
given by
f
∈ Z
p
. All the polynomial functions
F
satisfy this condition and experiments suggest that, although not random, the function
F
(
x
)
=
F
(
x
)
mod
p
for all
x
x
2
(
x
)
=
(
+
b
)
mod
n
heuristically behaves “like a random function” provided
that
b
=
0 and
b
=−
2 (see [194] and [60] for a discussion of these issues). Now
let
s
∈ Z
n
be a random element and consider the sequence obtained by iterating
F
: Z
n
→ Z
n
:
s
,
F
(
s
),
F
(
F
(
s
)),
F
(
F
(
F
(
s
))),...
Then, if
p
is an unknown prime factor of
n
and
r
=
s
mod
p
,wealsohavean
induced sequence of elements in
Z
p
:
