Cryptography Reference
In-Depth Information
5.1 The Index Calculus
Let
p
be a prime and let
g
be primitive root (see Appendix A) mod
p
,
which means that
g
is a generator for the cyclic group
F
p
. In other words,
every
h ≡
0(mod
p
)canbewrittenintheform
h ≡ g
k
for some integer
k
that is uniquely determined mod
p −
1. Let
k
=
L
(
h
)denotethe
discrete
logarithm
of
h
with respect to
g
and
p
,so
g
L
(
h
)
≡
h
(mod
p
)
.
Suppose we have
h
1
and
h
2
.Then
g
L
(
h
1
h
2
)
≡ h
1
h
2
≡ g
L
(
h
1
)+
L
(
h
2
)
(mod
p
)
,
which implies that
L
(
h
1
h
2
)
≡ L
(
h
1
)+
L
(
h
2
)(mod
p −
1)
.
Therefore,
L
changes multiplication into addition, just like the classical loga-
rithm function.
The
index calculus
is a method for computing values of the discrete log
function
L
. The idea is to compute
L
(
) for several small primes
,thenuse
this information to compute
L
(
h
) for arbitrary
h
. It is easiest to describe the
method with an example.
Example 5.1
Let
p
= 1217 and
g
= 3.
We want to solve 3
k
≡
37 (mod 1217). Most
of our work will be precomputation that will be independent of the number
37. Let's choose a set of small primes, called the
factor base
,tobe
B
=
{
2
,
3
,
5
,
7
,
11
,
13
}
. First, we find relations of the form
3
x
≡±
product of some primes in
B
(mod 1217)
.
Eventually, we find the following:
3
1
≡
3
(mod 1217)
3
24
≡−
2
2
·
7
·
13
3
25
≡
5
3
3
30
≡−
2
·
5
2
3
54
≡−
5
·
11
3
87
≡
13
These can be changed into equations for discrete logs, where now the congru-
ences are all mod
p−
1 = 1216. Note that we already know that 3
(
p−
1)
/
2
≡−
1
Search WWH ::
Custom Search