Cryptography Reference
In-Depth Information
15.5.5 The Joux-Lercier algorithm
The function field sieve of Adleman is a general algorithm for discrete logarithms in
F
p
n
where
p
is relatively small compared with
n
. Joux and Lercier gave a much simpler and
better algorithm. We will sketch this algorithm, but refer to Joux and Lercier [
284
] and
Section 15.2 of [
283
] for full details. We also refer to [
465
] for a survey of the function
field sieve.
Let
p
be prime and
n
=
√
n
∈ N
.Let
d
. Suppose one has monic polynomials
F
1
(
t
)
,F
2
(
t
)
∈ F
p
[
t
] such that deg(
F
1
(
t
))
=
deg(
F
2
(
t
))
=
d
and
F
2
(
F
1
(
t
))
−
t
has an irre-
ducible factor
F
(
t
)ofdegree
n
. We represent
F
p
[
t
]
/
(
F
(
t
)).
Given a prime
p
and an integer
n
one can find such polynomials
F
1
(
t
) and
F
2
(
t
)invery
little time.
F
p
n
with the polynomial basis
Exercise 15.5.22
Let
n
=
15. Find polynomials
F
1
(
t
)
,F
2
(
t
)
∈ F
2
[
t
] of degree 4 such that
F
2
(
F
1
(
t
))
−
t
has an irreducible factor of degree 15.
Now consider the polynomial ring
A
= F
p
[
x,y
] and two ring homomorphisms
ψ
1
:
A
→
A
1
= F
p
[
x
]by
ψ
1
(
y
)
=
F
1
(
x
) and
ψ
2
:
A
→
A
2
= F
p
[
y
]by
ψ
2
(
x
)
=
F
2
(
y
).
Define
φ
1
:
A
1
→ F
p
n
by
φ
1
(
x
)
=
t
(mod
F
(
t
)) and
φ
2
:
A
2
→ F
p
n
by
φ
2
(
y
)
=
F
1
(
t
)
(mod
F
(
t
)).
Exercise 15.5.23
Let the notation be as above and
G
(
x,y
)
∈ F
p
[
x,y
]. Show that
φ
1
(
ψ
1
(
G
(
x,y
)))
=
φ
2
(
ψ
2
(
G
(
x,y
))) in
F
p
n
.
B
2
⊆ F
p
[
y
] be the sets of linear polynomials. The idea of the
algorithm is simply to consider polynomials in
Let
B
1
⊆
A
1
= F
p
[
x
] and
F
p
[
x,y
] of the form
G
(
x,y
)
=
xy
+
ax
+
B
1
as
d
+
1
by
+
c
.If
ψ
1
(
G
(
x,y
))
=
(
x
+
b
)
F
1
(
x
)
+
(
ax
+
c
) factors over
i
=
1
(
x
−
u
i
) and if
B
2
as
d
+
1
ψ
2
(
G
(
x,y
))
=
(
y
+
a
)
F
2
(
y
)
+
(
by
+
c
) factors over
j
=
1
(
y
−
v
j
) then we have a
relation. The point is that such a relation corresponds to
d
+
1
d
+
1
(
t
−
u
i
)
=
(
F
1
(
t
)
−
v
j
)
i
=
j
=
1
1
in
F
p
n
.
One also needs to introduce the DLP instance by using a special
q
-descent: given
an irreducible polynomial
q
(
x
) one constructs polynomials
a
(
x
)
,b
(
x
) such that
q
(
x
)
|
(
a
(
x
)
F
1
(
x
)
+
b
(
x
)) and one hopes that (
a
(
x
)
F
1
(
x
)
+
b
(
x
))
/q
(
x
) has small factors and
that
a
(
F
2
(
y
))
y
b
(
F
2
(
y
)) has small factors, and hence iterate the process. When enough
relations are collected (including at least one “systematic equation” to remove the par-
asitic solution explained on page 442 of Joux [283]) one can perform linear algebra to
solve the DLP. The heuristic complexity of this algorithm is shown in [
284
] and Section
15.2.1.2 of [
283
] to be between
L
p
n
(1
/
3
,
3
1
/
3
+
o
(1)) and
L
p
n
(1
/
3
,
(32
/
9)
1
/
3
+
+
o
(1)) for
L
p
n
(1
/
3
,
(4
/
9)
1
/
3
p
≤
+
o
(1)).
