Cryptography Reference
In-Depth Information
Exercise 15.5.10
(Blake, Fuji-Hara, Mullin and Vanstone [
57
]) Once one has computed
w
g
z
δ
(mod
p
) one can apply the
Eu
clidean algorithm to find integers
w
1
,w
2
such that
=
w
2
(mod
p
) and
w
1
,w
2
≈
√
p
. Since
w
1
and
w
2
are smaller one would hope that
they are much more likely to both be smooth (however, note that both must be smooth). We
now make the heuristic assumption that the probability
ea
ch
w
i
is
B
-smooth is independent
and the same as the probability that any integer of size
√
p
is
B
-smooth. Show that the heuris-
tic running time of the algorithm has
u
u
replaced by (
u/
2)
u
(where
u
w
1
w
≡
=
log(
p
)
/
log(
B
))
and so the asymptotic running time remains the same.
F
p
Coppersmith, Odlyzko and Schroeppel [
1
35
] proposed an algorithm for the DLP in
=
√
p
that uses sieving. Their idea is to let
H
and define the factor base to be
B
={
q
:
q
prime
,q<L
p
(1
/
2
,
1
/
2)
}∪{
H
+
c
:1
≤
c
≤
L
p
(1
/
2
,
1
/
2
+
)
}
.
Since
H
2
p
1
/
2
(mod
p
)isofsize
≈
it follows that if (
H
+
c
1
)
,
(
H
+
c
2
)
∈
B
then (
H
+
c
2
)(mod
p
)isofsize
p
1
/
2
+
o
(1)
. One can therefore generate relations in
c
1
)(
H
. Further,
it is shown in Section 4 of [
135
] how to sieve over the choices for
c
1
and
c
2
. A heuristic
analysis of the algorithm gives complexity
L
p
(1
/
2
,
1
+
B
o
(1)) bit operations.
The
number field sieve
(NFS) is an algorithm for the DLP in
+
F
p
with heuristic com-
plexity
O
(
L
p
(1
/
3
,c
o
(1))) bit operations. It is closely related to the number field sieve
for factoring and requires algebraic number theory. As with the factoring algorithm, there
are two factor bases. Introducing the DLP instance requires an extra algorithm (we will
see an example of this in Section
15.5.4
). We do not have space to give the details
and instead refer to Schirokauer, Weber and Denny [
467
] or Schirokauer [
463
,
465
]for
details.
+
15.5.3 Discrete logarithms in small characteristic
F
q
where
q
p
n
,
p
is relatively
We now consider the discrete logarithm problem in
=
small (the case of most interest is
p
=
2) and
n
is large. We represent such a field with a
polynomial basis as
F
p
[
x
]
/
(
F
(
x
)) for some irreducible polynomial
F
(
x
)ofdegree
n
.The
natural notion of smoothness of an element
g
(
x
)
∈ F
p
[
x
]
/
(
F
(
x
)) is that it is a product of
polynomials of small degree. Since factoring polynomials over finite fields is polynomial-
time we expect to more easily get good algorithms in this case. The first work on this topic
was due to Hellman and Reyneri but we follow Odlyzko's large paper [
421
]. First we quote
some results on smooth polynomials.
Definition 15.5.11
Let
p
be prime and
n,b
∈ N
.Let
I
(
n
) be the number of monic irre-
ducible polynomials in
F
p
[
x
]ofdegree
n
. A polynomial
g
(
x
)
∈ F
p
[
x
] is called
b
-smooth
if all its irreducible factors have degree
b
.Let
N
(
n,b
) be the number of
b
-smooth poly-
nomials of degree exactly equal to
n
.Let
p
(
n,b
) be the probability that a uniformly chosen
polynomial of degree at most
n
is
b
-smooth.
≤
