Cryptography Reference
In-Depth Information
If we compute
P
0
,P
1
=
f
(
P
0
)
,P
2
=
f
(
P
1
)
,...
,weobtain
P
0
= (326
,
69)
,P
1
= (727
,
589)
,P
2
= (560
,
365)
,P
3
= (1070
,
260)
,
P
4
= (473
,
903)
,P
5
= (1006
,
951)
,P
6
= (523
,
938)
, ...,
P
57
= (895
,
337)
,P
58
= (1006
,
951)
,P
59
= (523
,
938)
, ....
Therefore, the sequence starts repeating at
P
5
=
P
58
.
If we keep track of the coe
cients of
P
and
Q
in the calculations, we find
that
P
5
=88
P
+46
Q
and
P
58
= 685
P
+ 620
Q.
Therefore,
∞
=
P
58
− P
5
= 597
P
+ 574
Q.
Since
P
has order 1067, we calculate
574
−
1
597
−
≡
499
(mod 1067)
.
Therefore,
Q
= 499
P
,so
k
= 499.
We stored all of the points
P
0
,P
1
,...,P
58
until we found a match. Instead,
let's repeat the computation, but compute the pairs (
P
i
,P
2
i
) and store nothing
except the current pair. We then find that for
i
=53thereisthematch
P
53
=
P
106
. This yields
620
P
+ 557
Q
=
P
53
=
P
106
= 1217
P
+ 1131
Q.
Therefore, 597
P
+ 574
Q
=
∞
, which yields
k
= 499, as before.
Pollard's
λ
method
uses a function
f
as in the
ρ
method, but several
random starting points
P
(1)
,...,P
(
r
)
are used. We then get sequences defined
0
0
by
P
(
)
i
+1
=
f
(
P
(
)
)
,
1
≤
≤
r,
i
=0
,
1
,
2
, ....
i
These can be computed by several computers in parallel. Points satisfying
certain conditions are called distinguished and are reported to a central com-
puter. When a match is found among the inputs from the various computers,
we have a relation that should allow us to solve the discrete log problem, as
in the
ρ
method. When there is a match between two sequences, these two
sequences will always match from that point on. We only need to look at
distinguished points because distinguished points should occur soon after a
match occurs.
When there are only two random starting points, we have two random
walks. Eventually they will have a point in common, and therefore they will
coincide thereafter. The picture of this process resembles the Greek letter
λ
,
hence the name.
Sometimes the
λ
method is described in terms of kangaroos jumping around
a field (this is the random walk). A variant of the
λ
method with two random
Search WWH ::
Custom Search