Cryptography Reference
In-Depth Information
14
Factoring and discrete logarithms using
pseudorandom walks
This chapter is devoted to the rho and kangaroo methods for factoring and discrete loga-
rithms (which were invented by Pollard) and some related algorithms. These methods use
pseudorandom walks and require low storage (typically a polynomial amount of storage,
rather than exponential as in the time/memory tradeoff). Although the rho factoring algo-
rithm was developed earlier than the algorithms for discrete logarithms, the latter are much
more important in practice.
1
Hence, we focus mainly on the algorithms for the discrete
logarithm problem.
As in the previous chapter, we assume
G
is an algebraic group over a finite field
F
q
written in multiplicative notation. To solve the DLP in an algebraic group quotient using
the methods in this chapter one would first lift the DLP to the covering group (though see
Section
14.4
for a method to speed up the computation of the DLP in an algebraic group
by essentially working in a quotient).
14.1 Birthday paradox
The algorithms in this chapter rely on results in probability theory. The first tool we need is
the so-called “birthday paradox”. This name comes from the following application, which
surprises most people: among a set of 23 or more randomly chosen people, the probability
that two of them share a birthday is greater than 0.5 (see Example
14.1.4
).
Theorem 14.1.1
Let
S
be a set of N elements. If elements are sampled uniformly at random
from
then the exp
ected
number of sam
ple
s to be taken before some element is sampled
twice is less than
√
πN/
2
S
1
.
253
√
N.
+
2
≈
The element that is sampled twice is variously known as a
repeat
,
match
or
collision
.
For the rest
of the
chapter we will ignore the
+
2 and say that the expected number of
samples is
√
πN/
2.
1
Pollard's paper [
437
] contains the remark “We are not aware of any particular need for such index calculations” (i.e., computing
discrete logarithms) even though [
437
] cites the paper of Diffie and Hellman. Pollard worked on the topic before hearing of the
cryptographic applications. Hence, Pollard's work is an excellent example of research pursued for its intrinsic interest, rather
than motivated by practical applications.
