Cryptography Reference
In-Depth Information
Continue to choose (at least)
B
such
k
so that we are successful in securing
B
relations as in (D.6). Here we are trying to solve for log
α
(
p
j
) for
j
=
1
,
2
,...,B
.
Calculation of discrete logs stage
:
≤
≤
(3) For each
k
in (D.6), determine the value of log
α
(
p
j
) for 1
j
B
by
solving the
B
(modular) linear equations with unknowns log
α
(
p
j
).
(4) Select a random nonnegative integer
t
2 and compute
βα
t
.
≤
p
−
(5) If possible,
factor
βα
t
over
B
, namely, write
B
p
t
j
βα
t
=
(
t
j
≥
0)
.
(D.7)
j
=1
If it is not possible to get (D.7), then go to step (4). If (D.7) is successfully
obtained, then
B
≡
−
log
α
(
β
)+
t
t
j
log
α
(
p
j
) (mod
p
1)
,
j
=1
from which we can calculate log
α
(
β
).
As usual, a small example will suGce to illustrate the algorithm.
Example D.3
Let
p
= 3361
,
α
=22
, and
B
=
{
2
,
3
,
5
,
7
}
. We wish to compute
F
3361
using the index-calculus method. We choose randomly
k
=
48
,
100
,
186
,
2986
and get
log
22
(4)
in
22
48
2
5
3
2
(mod 3361)
,
22
100
2
6
≡
·
≡
·
7 (mod 3361)
,
22
186
2
9
22
2986
2
3
5
2
(mod 3361)
.
≡
·
5 (mod 3361)
,
≡
·
3
·
Thus we get the system of four congruences in four unknowns:
≡
48
5 log
22
(2) + 2 log
22
(3) (mod 3360)
,
100
≡
6 log
22
(2) + log
22
(7) (mod 3360)
,
186
≡
9 log
22
(2) + log
22
(5) (mod 3360)
and,
3 log
22
(2) + log
22
(3) + 2 log
22
(5) (mod 3360)
.
This completes the precomputation stage. Now we use this to compute
2986
≡
log
22
(2) = 1100; log
22
(3) = 2314; log
22
(5) = 366
; and
log
22
(7) = 220
.
Search WWH ::
Custom Search