Cryptography Reference
In-Depth Information
Note also that the computation of the discrete logarithms of the factor base primes
is a precomputation that does not require the element a as input, since it depends
only on g and p . Because of this, its output can later be used to compute the discrete
logarithm of any a
∈ Z p , without having to redo this precomputation each time.
Once this first step is finished, the next one looks, again for r randomly chosen,
for a special relation of the form:
k
p c j
j
g r a mod p
=
,
j
=
1
which, in turn, gives a linear equation modulo p
1:
log g a
≡−
r
+
c 1 log g p 1 +
c 2 log g p 1 +···+
c k log g p k (
mod p
1
).
Plugging into this equation the values of the discrete logarithms of the primes,
which were obtained in the previous step, the discrete logarithm of a is found.
These steps admit many variants and refinements. For example,
1 can be added
to the factor base and this allows us to factor the least absolute residue of g t i (i.e.,
the integer closest to 0 which is congruent to g t i modulo p ) instead of the least non-
negative residue, with a noticeable efficiency gain due to the fact that the residues
obtained are smaller and hence more likely to factor over the factor base. Note that
this variant is possible because the discrete logarithm of
1 is known in advance,
namely, log g (
2.
The algorithm thus sketched is summarized in Algorithm 6.8:
1
) = (
p
1
)/
Z p .
Input :Aprime p , a primitive root modulo p , g , and an element a
Algorithm 6.8. Index calculus method for
Z p .
Output :log g a
Z p 1 .
Precomputation :
1. Choose a smoothness bound B and the factor base FB
={
p 1
,...,
p k
}
formed by the
B .
2. Choose random integers t
primes
10 (or other similar target number)
B -smooth residues g t mod p are found and save the corresponding relations.
3. Solve the linear system given by the relations and find log g p 1 ,..., log g p k .
Computation of log g a :
∈[
1
,
p
2
]
until k
+
= k j = 1 p c j
until r is found such that g r a mod p
1. Choose random integers in
[
1
,
p
2
]
j
is B -smooth.
2. return log g a
+ k j = 1 c j log g p j
= (
r
)
mod
(
p
1
)
.
There are a few things that have not been specified in the preceding description of
the algorithm. Perhaps the most important is how to choose the smoothness bound
B which, as happens with the quadratic sieve, has a direct impact on the complexity
 
Search WWH ::




Custom Search