Cryptography Reference
In-Depth Information
7.4.4
Factor Base and Index Calculus Algorithm
Factorization algorithms using factor bases can be adapted to the DLKOP problem,
which makes some researchers believe that the two problems might have the same
intrinsic complexity. This is the
index calculus algorithm
.
To compute the discrete logarithm of
y
in base
g
in a group
G
of known order
#
G
, we first take a factor base
B
={
p
1
,...,
p
r
}
. The first step consists of getting several
B
-numbers of the form
g
k
p
α
1
,
r
random relations. When we
have
r
+
c
relations for a small constant
c
, we can solve the linear system in
Z
#
G
, which
leads to the discrete logarithms of all
p
i
. Now we can pick a random
yg
k
p
α
1
,
1
1
and to collect
g
k
i
=
···
until it is a
B
-number and get the discrete logarithm of
y
:
p
α
i
,
r
relations,
2. solve the linear system defined by all
k
i
=
α
1
,
1
x
1
+···+
α
i
,
r
x
i
in
Z
#
G
,
3. obtain
yg
k
p
α
i
,
1
1
1. obtain several
g
k
i
=
···
···
p
β
r
,
4. infer
log
g
y
= β
1
x
1
+···+β
r
x
r
−
k
.
=
p
β
1
1
With
a
judicious
choice
of
B
the
complexity
of
this
algorithm
in
G
=
Z
p
is
e
(
c
+
o
(1))
√
log
p
log log
p
.
O
As an example, let us compute the discrete logarithm of
y
=
123
in base
g
=
7777
in
Z
34631
. We use the factor base
B
={
2
,
3
,
5
,
7
,
11
,
13
}
. We first collect the
relations
g
9
5
3
11
1
13
1
≡
×
×
g
109
2
2
3
5
5
1
7
1
≡
×
×
×
g
130
3
1
5
2
11
2
≡
×
×
g
131
2
5
3
1
7
3
≡
×
×
g
138
3
3
5
1
13
1
≡
×
×
g
161
≡
2
5
×
11
1
×
13
1
g
174
≡
2
3
×
3
7
g
185
≡
2
1
×
5
3
×
7
1
×
13
1
then we write
⎛
⎝
⎞
⎠
⎛
⎝
⎞
⎠
9
109
130
131
138
161
174
185
3
1
1
⎛
⎝
⎞
⎠
2511
12
x
1
x
2
x
3
x
4
x
5
x
6
2
51
3
=
×
31
1
5
1
1
37
1
3
1
1
Search WWH ::
Custom Search