Cryptography Reference
In-Depth Information
To perform Pollard's ρ algorithm for discrete logarithms, we partition the set of all integers between 0 and p
- 1 into three partitions of roughly equal size: P 0 , P 1 , and P 2 . These three sets can be simple, such as either the
integers below p divided into three contiguous sets (the first third of numbers less than p , the second third, the
third third), or split by the remainder of the number when divided by 3 (so that 2 belongs in P 2 , 10 belongs in
P 1 , and 15 belongs in P 0 ).
The algorithm expects to solve the problem a x = b in the group G, thus it takes a and b as arguments.
It relies on three functions to operate: the function f , which takes one argument — an integer modulo p - and
returns an integer modulo p ; the function g, which takes an integer modulo p and a normal integer and returns
an integer modulo p - 1; and a function h that takes an integer modulo p and an integer and returns an integer
module p - 1.
The functions are defined based on the partition they are in. Thus:
Pollard's p for Discrete Logarithms.
1. Set a 0 = 0 and b 0 = 0, two of our starting helper values.
2. Set x 0 = 1, our starting point in G.
3. Let i = 0.
4. Repeat the following steps until, at the end, x i = x 2i , and thus, we have found that our paths have
merged.
(a) Let i = i + 1.
Now, we calculate the next value for the function traveling slowly:
(b) Calculate the next x : x i = f ( x i-1 ).
(c) Calculate the next a : a i = g ( x i-1 , a i -1 ).
(d) Calculate the next b : b i = h ( x i -1 , b i-1 ).
Now, we calculate the next value for the function traveling quickly:
(e) Calculate the next x : x 2 i = f ( f ( x 2 i -2 )).
(f) Calculate the next a : a 2 i = g( f ( x 2 i - 2 ), g ( x 2 i -2 , a 2 i -2 )).
(g) Calculate the next b : b 2 i = h ( f ( x 2 i - 2 ), h ( x 2 i -2 , b 2 i -2 )).
5. If our b 's match, that is, b i = b 2 i , then the algorithm failed.
6. Set m = a i - a 2 i mod ( p - 1).
7. Set n = b 2 i - b i mod ( p - 1).
Search WWH ::




Custom Search