Cryptography Reference
In-Depth Information
8. Solve, for x , the equation mx n (mod ( p - 1)). More than likely, this will result in a few possible
values of x (usually a fairly small amount). Unfortunately, the only thing to do is to check each one and
see if it is the correct answer.
3.5.3.1 Analysis of Pollard's ρ for Discrete Logarithms
Pollard's ρ solves the discrete logarithm with running time on the order of (the square root of the size of the
finite field), with constant space, contrasted to the baby-step giant-step method, which takes a similar amount
of time but a large amount of space.
This makes it a great candidate for small discrete logarithm problems, where is not too big (more than
the number of calculations we are willing to make). The other issue is that this algorithm is not guaranteed to
work: The intersection we find may not yield any useful values of x.
3.5.4 Pollard's λ for Discrete Logarithms
Pollard also proposed a generalization of the ρ algorithm for discrete logarithms, called the λ method (λ is the
Greek letter lambda). Pollard's λ method of finding a discrete logarithm is a neat algorithm — interesting name,
an amusing description, and very clever. Here, we want to compute the discrete logarithm for g x = h in a group
G where we have some bound on x , such that a x < b .
The following description is derived from References [11] and [15].
This method is sometimes called the method of two kangaroos (or hares, or rabbits, depending on the au-
thor). The concept is that two kangaroos (representing iterative functions) are going to go for some “hops”
around the number field defined by the integer we wish to factor. These two kangaroos (or 'roos, as we like to
say) consist of a tame one, controlled by us and represented by T, and a wild one that we are trying to catch, W.
The tame 'roo, T, starts at a random point, t 0 = g b , while W starts at w 0 = h = g x . Define d 0 (T) = b , the initial
“distance” from the “origin” that the tame 'roo is hopping, and let d 0 (W) = 0, the initial distance of our wild
'roo from h .
Let S = { g S 1 , ... , g Sk } be a set of jumps, and let G be partitioned into k pieces G 1 , G 2 , ... , G k , with 1 ≤ f ( g ) <
k being a function telling to which partition g belongs. These exponents of g in S should be positive and small
compared to ( b - a ). Most often, we will pick these numbers to be powers of 2 (2 i ). These are the hops of both
kangaroos.
Now, the two kangaroos are going to hop. T goes from t i to
The tame 'roo will have distance
Similarly, W goes from w i to
giving the wild 'roo distance
Eventually, T will come to rest at some position t m , setting a trap to catch W . If ever d n (W) > d m (T) , then the
wild kangaroo has hopped too far, and we reset W to start at w 0 = hg z , for some small integer z > 0.
Search WWH ::




Custom Search