Cryptography Reference
In-Depth Information
=
(
−
+
+
+
+
log
g
9876543210
10951180283336
4log
g
2
log
g
3
log
g
5
log
g
7
+
+
+
+
+
+
)
log
g
11
log
g
29
log
g
37
log
g
43
log
g
61
log
g
79
mod
(
p
−
1
).
Since the discrete logarithms of the factor base primes are nowknown, this identity
can be used to find log
g
9876543210 as follows:
> (-10951180283336+4*7426253006290+4492127725870+11192451597521+17081013481576+
15896098548408+4469420019618+11127950744169+8646993757009+7580738887351+
16066730563529) mod (p-1);
11628971657383
We see that the result obtained is the same as the one provided by the function
IndexCalculus
. As a final check, let us use binary exponentiation to see that the
result is correct:
> Power(g, 11628971657383) mod p;
9876543210
Of course, this discrete logarithm may also be computed in one pass by calling
the function
IndexCalculus
with default values as follows:
> IndexCalculus(p, g, 9876543210);
11628971657383
Exercise 6.35
Write variants of the function
IndexCalculus
(and the associated
auxiliary functions) with each one of the following changes:
(i) Replace trial division by the elliptic curve method (implemented in
ifactor
with the option 'lenstra').
(ii) Solve the system involving both the discrete logarithms of the primes and the
discrete logarithm being computed, after the final relation is found.
Exercise 6.36
Do an experimental study by timing the function
Index
Calculus
on primes of different sizes in order to check how well the running
time agrees with the expected subexponential time.
6.5.7 Extensions of the Index Calculus Method
Z
p
, where
p
is prime,
but this method can be extended to other classes of cyclic groups as well. The most
immediate generalization is for the multiplicative group
We have discussed the index calculus method for the group
F
p
n
of the nonzero elements
Z
p
= F
p
of a finite field
F
p
n
, of which
is the particular case corresponding to
n
=
1.
F
p
n
is quite different from
F
p
when
n
It should be noted, however, that
>
1. In this
case there is no direct relation between
Z
p
n
and, although we have seen a
way to represent the elements of the former as integers, the field operations between
F
p
n
and
