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