Cryptography Reference
In-Depth Information
Exercise 15.5.15
Let the notation be as above. Show that the complexity of this algorithm
is at most
u
u
(1
+
o
(1))
log(
q
)
3
)
2
+
o
(1)
M
(log(
r
))
c
1
#
B
+
c
2
(#
B
p
n
.
bit operations (for some constants
c
1
and
c
2
)as
n
→∞
in
q
=
For the complexity analysis it is natural to arrange that #
B
≈
L
p
n
(1
/
2
,c
) for a suitable
p
b
/b
.Tohave
p
b
/b
constant
c
. Recall that #
B
≈
=
L
p
n
(1
/
2
,c
) then, taking logs,
c
n
log(
p
)(log(
n
)
b
log(
p
)
−
log(
b
)
=
+
log(log(
p
)))
.
c
√
n
log(
n
)
/
log(
p
).
≈
It follows that
b
F
p
n
in expected
Exercise 15.5
.1
6
Show that one can compute discrete logarithms in
O
(
L
p
n
(1
/
2
,
√
2
+
o
(1))) bit operations for fixed
p
and as
n
→∞
. (Note that this result
does not rely on any heuristic assumptions.)
Exercise 15.5.17
Adapt the trick of Exercise
15.5.10
to this algorithm. Explain that the
complexity of the algorithm remains the same, but is now heuristic.
Lovorn Bender and Pomerance [
358
] give rigorous complexity
L
p
n
(1
/
2
,
√
2
+
o
(1)) bit
operations as
p
n
n
o
(
n
)
.
→∞
and
p
≤
F
2
n
This algorithm (inspired by the “systematic equations” of Blake, Fuji-Hara, Mullin and
Vanstone [
57
]) was the first algorithm in computational number theory to have heuristic
subexponential complexity of the form
L
q
(1
/
3
,c
15.5.4 Coppersmith's algorithm for the DLP in
+
o
(1)).
F
2
n
of the form
F
2
[
x
]
/
(
F
(
x
)) for
F
(
x
)
=
The method uses a polynomial basis for
x
n
1).
The “systematic equations” of Blake
et al.
are relations among elements of the factor base
that come almost for free. For example, in
+
F
1
(
x
) where
F
1
(
x
) has very small degree. For example,
F
2
127
= F
2
[
x
]
/
(
x
127
+
x
+
F
2
127
,if
A
(
x
)
∈ F
2
[
x
] is an irreducible polynomial
in the factor base then
A
(
x
)
128
A
(
x
128
)
A
(
x
2
x
)(mod
F
(
x
)) and
A
(
x
2
=
≡
+
+
x
) is either
irreducible or is a product
P
(
x
)
P
(
x
1) of irreducible polynomials of the same degree
(Exercise
15.5.18
). Hence, for many polynomials
A
(
x
) in the factor base one gets a non-
trivial relation.
+
∈ F
2
[
x
] be an irreducible polynomial. Show that
A
(
x
2
Exercise 15.5.18
Let
A
(
x
)
+
x
)is
either irreducible or a product of two polynomials of the same degree.
Coppersmith
[
130
]
extended
the
idea
as
follows:
let
b
∈ N
be
such
that
b
=
cn
1
/
3
log(
n
)
2
/
3
(2
/
(3 lo
g(
2)))
2
/
3
)
, let
k
fo
r a s
uitable constant
c
(later we take
c
=
∈ N
be
≈
√
nb
≈
√
n/b
≈
√
cn
2
/
3
log(
n
)
1
/
3
.
such that 2
k
√
c
(
n/
log(
n
))
1
/
3
1
n/
2
k
≈
and let
l
=
2
b
/b
by Exer-
Let
B
={
A
(
x
)
∈ F
2
[
x
]:deg(
A
(
x
))
≤
b,A
(
x
) irreducible
}
. Note that #
B
≈
cise
15.5.14
.
Suppose
A
(
x
)
,B
(
x
)
∈ F
2
[
x
]
are
such
that
deg(
A
(
x
))
=
d
A
≈
b
and
