Cryptography Reference
In-Depth Information
Also, the “slower” sequence x i is visiting group elements which have already been com-
puted during the walk of the “faster” sequence x 2 i . Brent [ 93 ] has given an improved
cycle finding method 4 that still only requires storage for two group elements, but which
requires fewer group operations. Montgomery has given an improvement to Brent's method
in [ 392 ].
One can do even better by using more storage, as was shown by Sedgewick, Szymanski
and Yao [ 482 ], Schnorr and Lenstra [ 474 ] (also see Teske [ 541 ]) and Nivasch [ 419 ].
T he rho algorithm u sing Nivasch cycle finding has the optimal expected running time of
πr/ 2
1 . 253 r group operations and is expected to require polynomial storage.
Finally, a very efficient way to find cycles is to use distinguished points. More impor-
tantly, distinguished points allow us to think about the rho method in a different way and
this leads to a version of the algorithm that can be parallelised. We discuss this in the next
section. Hence, in practice one always uses distinguished points.
14.2.4 Distinguished points and Pollard rho
The idea of using distinguished points in search problems apparently goes back to Rivest.
The first application of this idea to computing discrete logarithms is by van Oorschot and
Wiener [ 423 ].
Definition 14.2.9 An element g
G is a distinguished point if its binary representation
b ( g ) satisfies some easily checked property. Denote by
D
G the set of distinguished
points. The probability #
D / # G that a uniformly chosen group element is a distinguished
point is denoted θ .
A typical example is the following.
Example 14.2.10 Let E be an elliptic curve over
F p . A point P
E (
F p ) that is not the point
at infinity is represented by an x -coordinate 0
x P <p and a y -coordinate 0
y P <p .
Let H be a hash function, where the output is interpreted as being in
Z 0 .
Fix an integer n D . Define
D
to be the points P
E (
F p ) such that the n D least significant
bits of H ( x P ) are zero. Note that
O E D
. In other words
0(mod2 n D ) where 0
D ={
P
=
( x P ,y P )
E (
F p ): H ( x P )
x P <p
}
.
1 / 2 n D .
Then θ
The rho algorithm with distinguished points is as follows. First, choose integers 0
g a 1 h b 1
a 1 ,b 1 <r uniformly and independently at random, compute the group element x 1 =
g a n h b n
is found. Store ( x n ,a n ,b n ) in some easily searched data structure (searchable on x n ). Then
choose a fresh randomly chosen group element x 1 =
and run the usual deterministic pseudorandom walk until a distinguished point x n =
g a 1 h b 1 and repeat. Eventually two
walks will visit the same group element, in which case their paths will continue to the same
4
This was originally developed to speed up the Pollard rho factoring algorithm.
Search WWH ::




Custom Search