Cryptography Reference
In-Depth Information
notation, as corresponds to an elliptic curve group, is used). In practice, one often uses
a partition function which, in the case of three subsets, is a function q
:
→{
,
,
}
G
1
2
3
q 1
which is efficiently computable and defines the sets S i as S j
=
(
j
)
for j
=
1
,
2
,
3.
This means that, in the recursive formulas above, the conditions x i
S j are verified
by checking that q
j .
Since the expected number of steps is O
(
x i ) =
( n
, the running time of th e rho method
is the same as that of the baby-step giant-step algorithm, namely O
)
( n
,
but the advantage of the rho method is that now storage requirements are minimal.
Observe, on the other hand that, in contrast with the BSGS method which is com-
pletely rigorous, the rho method is heuristic for we do not have a proof that the
method always works and finishes within the stated time bound. But, in practice, the
rho method works well and is usually preferable to BSGS.
The original formulation of Pollard was for the group
·
polylog
(
n
))
Z p , where p is a prime, and
: Z p →{
the partition he proposed is given by the function q
1
,
2
,
3
}
defined by:
1
3
1f 0
<
x
<
p
,
2f 3
2
3
q
(
x
) =
<
<
,
p
x
p
3f 3
p
<
x
<
p
.
The rho algorithm is summarized in Algorithm 6.7. Given F
:
G
G , defined as
above in terms of g and a , and
(
x i ,
r i ,
s i )
G
×Z n ×Z n such that h
(
r i ,
s i ) =
x i ,we
define f
(
x i ,
r i ,
s i ) = (
F
(
x i ),
r i + 1 ,
s i + 1 )
(where r i + 1 , s i + 1 are the exponents of g and
a when F
(
x i )
is expressed in terms of these elements, so that h
(
r i + 1 ,
s i + 1 ) =
F
(
x i ))
.
Algorithm 6.7. Pollard's rho for discrete logarithms.
Input : A finite cyclic group G of order n , a generator g
G and a
G .
Output :log g a .
Define f
:
G
× Z n
× Z n
G
× Z n
× Z n so that if
(
x i
,
r i
,
s i
)
G
× Z n
× Z n then, with
the previous notation:
f
(
x i
,
r i
,
s i
) = (
F
(
x i
),
r i + 1
,
s i + 1
)
.
Set b := ( 1 , 0 , 0 ) and c := ( 1 , 0 , 0 ) .
repeat
b
:=
f
(
b
)
;
c
:=
f
(
f
(
c
))
;
until b
[
1
]=
c
[
1
]
.
if b
) then
Find log g a among the solutions of the congruence:
(
[
3
] ≡
c
[
3
] (
mod n
b
[
3
]−
c
[
3
] )
x
c
[
2
]−
b
[
2
] (
mod n
)
;
return log g a
else
Restart computation with new values of b and c
end if .
 
 
Search WWH ::




Custom Search