Cryptography Reference
In-Depth Information
(mod
p
), so
L
(
−
1) = 608.
1
≡
L
(3)
(mod 1216)
24
608 + 2
L
(2) +
L
(7) +
L
(13)
25
≡
3
L
(5)
30
≡
608 +
L
(2) + 2
L
(5)
54
≡
608 +
L
(5) +
L
(11)
87
≡ L
(13)
≡
The first equation yields
L
(3)
≡
1. The third yields
L
(5)
≡
819 (mod 1216).
The sixth yields
L
(13)
≡
87. The fourth gives
L
(2)
≡
30
−
608
−
2
·
819
≡
216
(mod 1216)
.
The fifth yields
L
(11)
≡
54
−
608
−
L
(5)
≡
1059. Finally, the second gives
L
(7)
≡
24
−
608
−
2
L
(2)
−
L
(13)
≡
113
(mod 1216)
.
We now know the discrete logs of all the elements of the factor base.
Recall that we want to solve 3
k
We compute 3
j
·
37
(mod
p
) for several random values of
j
until we obtain an integer that can be
factored into a product of primes in
B
. In our case, we find that
≡
37 (mod 1216).
3
16
2
3
·
37
≡
·
7
·
11
(mod 1217)
.
Therefore,
L
(37)
≡
3
L
(2) +
L
(7) +
L
(11)
−
16
≡
588
(mod 1216)
,
and 3
588
≡
37 (mod 1217).
The choice of the size of the factor base
B
is important. If
B
is too small,
then it will be very hard to find powers of
g
that factor with primes in
B
.If
B
is too large, it will be easy to find relations, but the linear algebra needed to
solve for the logs of the elements of
B
will be unwieldy. An example that was
completed in 2001 by A. Joux and R. Lercier used the first 1 million primes
to compute discrete logs mod a 120-digit prime.
There are various methods that produce relations of the form
g
x
≡
product
of primes in
B
. A popular one uses the number field sieve. See [58].
The expec
ted running
time of the index calculus is approximately a constant
times exp(
√
2ln
p
ln ln
p
) (see [81, p. 129]), which means that it is a subex-
ponential algorithm. The algorithms in
S
ection 5.2, which are
exponential
algorithms, run in time approximately
√
p
=exp(
2
ln
p
). Since
√
2ln
p
ln ln
p
is much smaller than
1
2
ln
p
for large
p
, the index calculus is generally much
faster when it can be used.
Search WWH ::
Custom Search