Cryptography Reference
In-Depth Information
concepts, the specific details vary quite widely (in particular, precisely what “linear algebra”
is required). We present in this section an algorithm that is very convenient when working
in subgroups of prime order
r
in
F
q
as it relies only on linear algebra over the field
F
r
.
∈ F
q
have prime order
r
and let
h
. The starting point is the observation that
if one can find integers 0
<Z
1
,Z
2
<r
such that
g
Z
1
h
Z
2
Let
g
∈
g
=
1
(15.6)
Z
1
Z
−
2
(mod
r
). The idea will be to find such a relation using a
factor base and linear algebra. Such algorithms go under the general name of
index calculus
algorithms; the reason for this is that
index
is another word for discrete logarithm, and the
construction of a solution to equation (
15.6
) is done by calculations using indices.
F
q
then log
g
(
h
)
in
=−
15.5.1 Rigorous subexponential discrete logarithms modulo
p
F
p
.Itis
We now sketch a subexponential algorithm for the discrete logarithm problem in
∈ F
p
have order
r
(we will assume
r
is prime, but the general case is not significantly different) and let
h
closely related to the random squares algorithm of Section
15.2
.Let
g
∈ F
p
. We will also assume, for simplicity, that
r
2
be such that
h
∈
g
(
p
−
1) (we show in
Exercise
15.5.8
that this condition can be avoided).
The natural idea is to choose the factor base
B
Z
to be the primes in
up to
B
.Welet
s
=
#
B
. One can take random powers
g
z
(mod
p
) and try to factor over
B
. One issue is
F
p
and so a strong smoothness heuristic would
be required. To get a rigorous algorithm (under the assumption that
r
2
that the values
g
z
only lie in a subgroup of
(
p
−
1)) write
G
for the subgroup of
G
at each iteration
and try to factor
g
z
δ
(mod
p
); this is now a uniformly distributed element of
F
p
of order (
p
−
1)
/r
, choose a random
δ
∈
F
p
and so
Corollary
15.1.8
can be applied. We remark that the primes
p
i
themselves do not lie in the
subgroup
g
.
1) be a prime such that
r
2
∈ F
p
have order
Exercise 15.5.1
Let
r
|
(
p
−
(
p
−
1). Let
g
dividing
r
and denote by
G
⊆ F
p
the subgroup of order (
p
G
=
−
1)
/r
. Show that
g
∩
{
1
}
.
Exercise 15.5.2
Give two ways to sample randomly from
G
. When would each be used?
[Hint: See Section
11.4
.]
G
and
The algorithm proceeds by choosing random values 1
≤
z<r
and random
δ
∈
testing
g
z
δ
(mod
p
) for smoothness. The
i
th relation is
s
p
e
i,j
j
g
z
i
δ
i
≡
(mod
p
)
.
(15.7)
j
=
1
The values
z
i
are stored in a vector and the values
e
i
=
(
e
i,
1
,...,e
i,s
) are stored as a row
in a matrix. We need
s
relations of this form. We also need at least one relation involving
h
(alternatively we could have used a power of
h
in every relation in equation (
15.7
)) so
