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