Cryptography Reference
In-Depth Information
Index-Calculus Algorithm
An optimized variant of this algorithm is the fastest
known algorithm to date for computing discrete logarithms to the base
g
modulo a prime
p
,
where
g
is a generator.
To compute log
g
,
p
b
where
g
x
b
(mod
p
) using the index-calculus algorithm:
1.
Select from the numbers 2, 3, . . . ,
p
2, a subset of the first
t
primes
S
= {
p
1
,
p
2
, . . . ,
p
t
} such that “many” of the elements
g
i
where 1
≤ i
<
p
1 can be written as a product
of elements from
S
.
2 and compute the lnr of
g
j
modulo
p
.
2.
Select a random integer
j
such that 0
≤ j ≤ p
Attempt to write
g
j
as a product of elements from
S
:
3.
g
j
=
p
1
c
1
p
2
c
2
p
t
c
t
,
...
c
i
≥
0
∀
i.
If this is not successful, return to step 2; otherwise, continue.
4.
Take the logarithm modulo
p
of both sides to produce a congruence;
j
log(
g
)
j
c
1
log(
p
1
) +
c
2
log(
p
2
) + . . . +
c
t
log(
p
t
) (mod
p
1).
(Simplify using the properties of discrete logarithms, as shown.)
5.
Repeat steps 2 through 4 to make a system of at least
t
such congruences. Attempt to
find a unique solution for each logarithm by solving the system. If the system is linearly
dependent, go back to step 2 and generate new congruences to replace those that are lin-
early dependent on the others.
Select a random integer
k
such that 0
≤ k ≤ p
2, and compute the lnr of
b g
k
modulo
p
.
6.
Attempt to write
b g
k
as a product of elements from
S
:
7.
b g
k
=
p
1
d
1
p
2
d
2
p
t
d
t
,
...
d
i
≥
0
∀i
.
If this attempt is not successful, return to step 6; otherwise, continue.
8.
Take the logarithm to the base
g
of both sides; this yields
log(
b g
k
)
log(
b
) +
k
log(
g
)
log(
b
) +
k
d
1
log(
p
1
) +
d
2
log(
p
2
) + . . . +
d
t
log(
p
t
) (mod
p
1).
which we then solve for log
g
,
p
b
:
log(
b
)
d
1
log(
p
1
) +
d
2
.
log(
p
2
) + . . . +
d
t
log(
p
t
)
k
(mod
p
1).
E
XAMPLE
.
We will use the index-calculus algorithm to find a solution to 6
x
57 (mod
107). Note that 107 is prime, and that 6 is a generator modulo 107 (verify). So, the parameters
Search WWH ::
Custom Search