Cryptography Reference
In-Depth Information
Each
processor runs for
√
πr/
2
/N
P
+
1
/θ
steps and therefore is expected to send
θ
√
πr/
2
/N
P
+
1 distinguished points in its lifetime. The total number of points to store is
therefore
θ
√
πr/
2
+
N
P
.
Exercise
14.2.
15
shows that the complexity in the case
N
P
=
1 can be taken to be
o
(1))
√
πr/
2 group operations with polynomial storage.
(1
+
Exercise 14.3.3
When distributing the algorithm it is important to ensure that, with very
high probability, each processor finds at least one distinguished p
oint i
n less than its total
expected running time. Show that this will be the case if 1
/θ
≤
√
πr/
2
/
(
N
P
log(
r
)
)
.
Schulte-Geers [
480
] analyses the choice
of
θ
and shows that Heuristics
14.2.13
and
14.3.1
are not valid asymptotically if
θ
o
(1
/
√
r
)as
r
(e.g., walks in this situation are
more likely to fall into a cycle than t
o hit
a distinguished point). In any case, since
e
ach
processor only travels a distance of
√
πr/
2
/N
P
it follows we should take
θ>N
P
/
√
r
.In
practice, one tends to determ
ine t
he available storage first (say,
c
group elements where
c>
10
9
) and to set
θ
=
→∞
c/
√
πr/
2 so that the total number of distinguished points visited
is expected to be
c
. The results of [
480
] validate this approach. In particular, it is extremely
unlikely that there is a self-collision (and hence a cycle) before hitting a distinguished point.
=
14.4 Speeding up the rho algorithm using equivalence classes
Gallant, Lambert and Vanstone [
215
] and Wiener and Zuccherato [
565
] showed that one
can speed up the rho method in certain cases by defining the pseudorandom walk not on the
group
but on a set of equivalence classes. This is essentially the same thing as working
in an algebraic group quotient instead of the algebraic group.
Suppose there is an equivalence relation on
g
g
. Denote by
x
the equivalence class
of
x
∈
g
.Let
N
C
be the size of a generic equivalence class. We require the following
properties:
1. One can define a unique representative
x
of each equivalence class
x
.
2. Given (
x
i
,a
i
,b
i
) such that
x
i
=
g
a
i
h
b
i
one can efficiently compute (
x
i
, a
i
, b
i
) such that
g
a
i
h
b
i
.
x
i
=
We give some examples in Section
14.4.1
below.
One can implement the rho algorithm on equivalence classes by defining a pseudorandom
walk function
walk
(
x
i
,a
i
,b
i
) as in Definition
14.2.1
. More precisely, set
x
1
=
g,a
1
=
1
,b
1
=
0 and define the sequence
x
i
by (this is the “original walk”)
x
i
if
S
(
x
i
)
=
0
x
i
+
1
=
f
(
x
i
)
=
(14.6)
x
i
g
j
if
S
(
x
i
)
=
j, j
∈{
1
,...,n
S
−
1
}
g
u
j
h
v
j
are as in Definition
14.2.1
. When
using distinguished points one defines an equivalence class to be distinguished if the unique
equivalence class representative has the distinguished property.
where the selection function
S
and the values
g
j
=
