A new index calculus algorithm

with complexity L(1/4 + o(1)) in small

characteristic
Antoine Joux
CryptoExperts and
Universite de Versailles Saint-Quentin-en-Yvelines, Laboratoire PRISM,
45 avenue des

Etats-Unis, F-78035 Versailles Cedex, France
antoine.joux@m4x.org
Abstract. In this paper, we describe a new algorithm for discrete loga-
rithms in small characteristic. This algorithm is based on index calculus
and includes two new contributions. The rst is a new method for gen-
erating multiplicative relations among elements of a small smoothness
basis. The second is a new descent strategy that allows us to express
the logarithm of an arbitrary nite eld element in terms of the loga-
rithm of elements from the smoothness basis. For a small characteristic
nite eld of size Q = p
n
, this algorithm achieves heuristic complexity
LQ(1/4 + o(1)). For technical reasons, unless n is already a composite
with factors of the right size, this is done by embedding FQ in a small
extension FQ
e with e 2log
p
n.
1 Introduction
The discrete logarithm problem is one of the major hard problems used in cryp-
tography. In this paper, we show that for nite elds of small characteristic, this
problem can be solved with heuristic complexity L(1/4 + o(1)). Moreover, the
algorithm yields very practical improvements compared to the previous state-of-
the-art.
One of the two main ideas used for our algorithm is a generalization of the
pinpointing technique proposed in [10]. Another independent algorithm for char-
acteristic 2 was proposed in [5], yielding an algorithm with complexity L
Q
(1/3),
with a better constant than the Function Field Sieve.
2 A reminder of discrete logarithm algorithms in small
characteristic
As usual when studying index calculus algorithms, we write:
L
Q
(, c) = exp((c +o(1))(log Q)

(log log Q)
1
),
where Q = p
n
denotes the size of the nite eld.
2 Antoine Joux
When considering the computation of discrete logarithms, in elds of the
form F
Q
, where p is relatively small compared to Q, the state of the art choice
is to use one of the numerous variation of the function eld sieve. For larger
values of p, it becomes preferable to use a variation of the number eld sieve.
The choice between the two family of algorithms is made by comparing p and
L
Q
(
1
3
) (see [12]).
All these variants of the function eld sieve nd multiplicative relations by
factoring various polynomials into polynomials of low degree. A classical useful
result is the logarithm of the probability that a random polynomial of degree
n decomposes into factors of degree m over a nite eld is close to:

n
m
log
_
n
m
_
,
for a wide range of parameters [13].
When using function eld sieve algorithms, a standard heuristic assumption
is to assume that all polynomials that arise in the algorithm also follow this
smoothness probability. In the new algorithm presented here, this is false by
construction, because we consider polynomials than decompose more frequently
than usual. However, we still use the heuristic assumption on some polynomials:
those for which there is no known reason to expect that they would deviate from
the normal behavior.
Despite the new ingredients we are using, there are deep similarities between
our algorithm and its predecessors. In particular, some features are reminiscent
of Coppersmiths algorithm [3], while others are inspired from [11]. In the present
section, we recall these two algorithms.
2.1 Coppersmiths algorithm
Coppersmiths algorithm was published in 1984 in [3]. Historically, it was the
rst discrete logarithm algorithm to achieve complexity L(1/3). In its original
presentation, this algorithm is dedicated to characteristic 2, but it can easily be
generalized to any xed characteristic [14].
Consider as usual a nite eld of size Q = p
n
. Coppersmith assumes that
F
Q
is constructed using a polynomial P(x) = x
n
P
0
(x), where P
0
(x) is a
polynomial of low degree. He then chooses k a power of p close to

n and writes
n = hk n
0
, with 0 n
0
< k.
Let A and B be two polynomials of low degree. Coppersmith considers the
polynomial C(x) = x
h
A(x) + B(x), let D = C
k
and remarks that since k is a
power of p, the linearity of the Frobenius map implies:
D(x) = C(x)
k
= x
hk
A(x)
k
+B(x)
k
(mod P(x))
= x
n0
P
0
(x)A(x)
k
+B(x)
k
(mod P(x))
As a consequence, both C and D have moderate degrees O(

n). If both factors

into low degree polynomials, we obtain a multiplicative relation between the
factors; in this relation, the factors of C are raised to the power k.
A new index calculus algorithm in small characteristic 3
The complexity of Coppersmiths index calculus algorithm is L(1/3, c) with
a value of c that depends on the extension degree n. This constant is minimized
when n is close to a power of p
2
.
2.2 Function eld sieve
The general function eld sieve algorithm was proposed in 1999 by Adleman and
Huang in [1]. It improves on Coppermiths algorithm when the extension degree
n is not close to a power of p
2
. In its general form, it uses multiplicative relations
between ideals in function elds and technicalities arise due to this. A simplied
version was proposed in [11]. This simplied version only involves polynomial
rings (instead of function elds), which has the merit of removing most of these
technicalities.
The algorithm from [11] is particularly well suited to the computation of
discrete logarithms in elds that contain a medium-sized subeld (not necessarily
prime). To emphasize this, we write the nite eld as F
q
n, a degree n extension of
the medium-sized eld F
q
. In the optimal case where q = L
q
n(1/3), the constant
in the complexity can even be reduced compared to usual function eld sieve.
By convention, in the rest of the section, X and Y are formal variables,
while x and y are elements of F
q
n. In order to dene the extension eld F
q
n,
the algorithm selects g
1
and g
2
two univariate polynomials of respective degree
d
1
and d
2
with coecients in F
q
. If the polynomial g
2
(g
1
(Y )) + Y has an
irreducible factor J(Y ) of degree n over F
q
, then J can be used to dene F
q
n
and we denote by y a root of J in this eld. When this occurs, g
1
(g
2
(X)) +X
also has an irreducible factor J

(X) of degree n over F

q
. Moreover, x = g
1
(y) is a
root of J

in F
q
n. Abstractly, we consider that the algorithm is, in fact, dening
the nite eld F
q
n implicitly by the two relations:
x = g
1
(y), y = g
2
(x), (1)
As explained in [11], it is easy to nd polynomials g
1
and g
2
that satisfy this
requirement. This denition of the nite eld induces the commutative diagram
in Figure 1. On the right-hand side, we use the J(Y ) to dene F
q
n and on the
left-hand side, we use J

(X).
Fq[X, Y ]
Fq[X] Fq[Y ]
Fq
n
Y g
2
(X)
Xg
1
(Y )
Xx
Y y
Fig. 1. Commutative diagram for the algorithm of [11]
4 Antoine Joux
The relative degrees of d
1
and d
2
in the construction are controlled by an
extra parameter D, whose choice is determined by the size of q compared to q
n
.
More precisely, we have d
1

Dn and d
2

_
n/D. The simplest and most
ecient case occurs when we can choose D = 1, i.e. d
1
d
2


n.
Starting from this denition of the nite eld, the medium prime eld algo-
rithms consider objects of the form /(Y ) X+B(Y ), where / and B are univari-
ate polynomials of degree D and / is unitary. Substituting g
1
(Y ) for X on one
side and g
2
(X) for Y on the other, we obtain two univariate polynomials whose
images in F
q
n are equal, i.e. an equation:
/(y) g
1
(y) +B(y) = /(g
2
(x)) x +B(g
2
(x)).
This relates the images of a polynomial of degree d
1
+D in Y and a polynomial
of degree Dd
2
+ 1 in X.
Following [11] , we only keep the relations, where /(Y ) g
1
(Y ) + B(Y ) and
/(g
2
(X)) X +B(g
2
(X)) both factor into unitary polynomials of degree at most
D in X or Y . This yields multiplicative relations between the images in F
q
n of
these low-degree polynomials, which form the smoothness basis. Classically the
good pairs (/, B) are found using a sieving approach
1
.
Complexity. To express the complexity, [11] let Q = q
n
and assumes that there
exists a parameter such that:
n =
1

_
log Q
log log Q
_
2/3
, q = exp
_

3
_
log Q log
2
log Q
_
.
In this setting, the heuristic asymptotic complexity of the sieving phase is
L
q
n(
1
3
, c
1
) and the complexity of the linear algebra is L
q
n(
1
3
, c
2
), with:
c
1
=
2
3

D
+D and c
2
= 2D.
Note that the algorithm with parameter D only works under the condition that
we can obtain enough linear equations to build the linear system of equations.
This requires:
(D + 1)
2
3

D
. (2)
For a given nite eld F
q
n, [11] indicates that the best possible complexity is
obtained by choosing the smallest acceptable value for the parameter D.
Individual logarithms phase. Another very important phase that appears
in index calculus algorithms is the individual discrete logarithms phase which
allows to compute the logarithm of an arbitrary nite eld element by nd-
ing a multiplicative relation which relates this element to the elements of the
smoothness basis whose logarithms have already been computed.
1
Asymptotically, exhaustive search of good pairs is as ecient. However, using sieving
improves things by a large constant factor.
A new index calculus algorithm in small characteristic 5
We now detail this phase in the case of [11]. The ultimate goal of expressing a
given element as a product of elements from the smoothness basis is not achieved
in a single pass. Instead, it is done by rst expressing the desired element in F
q
n
as a product of univariate polynomials in either x or y and with degree smaller
than that of the desired element. These polynomials can in turn be related to
polynomials of a lower degree and so on, until hitting degree D, i.e. elements
of the smoothness basis. For this reason, the individual logarithm phase is also
called the descent phase.
In order to create relations between a polynomial in either X or Y (i.e.
coming either from the left or right side of a previous equation) and polynomials
of lower degree, [11] proceeds as follows: Let Q(X) (resp. Q(Y )) denote the
polynomial that represent the desired element. One considers a set of monomials
S
Q
= X
i
Y
j
[i [0 D
x
(Q)], j [0 D
y
(Q)], where D
x
(Q) and D
y
(Q) are
parameters that we determine later on. Each monomial in S
Q
can be expressed
as a univariate polynomial in X (resp. Y ), after replacing Y by g
2
(X) (or X
by g
1
(Y )). For a monomial m we denote by V
Q
(m) the value modulo Q of the
univariate polynomial corresponding to m. Clearly, V
Q
(m) can be represented by
a vector of deg Q nite eld elements. We now build a matrix M
Q
by assembling
all the vectors V
Q
(m) for m S
Q
. Any vector in the kernel of M
Q
can then be
interpreted as a polynomial whose univariate representation is divisible by Q. If
both the quotient after dividing by Q and the univariate representation in the
other unknown decompose into products of polynomials of low enough degree,
we obtain the desired relation.
Clearly, this approach requires us to take enough monomials to make sure
that the kernel contains suciently many polynomials in order to nd a satis-
fying relation. This can be achieved by choosing D
x
(Q) and D
y
(Q) such that
D
x
(Q)D
y
(Q) deg Q. Moreover to balance the degrees after replacing X or Y ,
we make sure that D
y
(Q)/D
x
(Q) D. With these choices, the degree on each
side after replacement is close to

ndeg Q. The logarithm of the probability

that each of the two sides decompose into polynomials of degree at most deg Q
(after factoring out Q) is estimated by:

_
n
deg Q
log
_
2

_
n
deg Q
_
.
The cost of this descent step increases when the degree of Q decreases. As
a consequence, the total cost of the descent is dominated by the lowest degree
polynomials that still need to be processed. In [11], the descent is used all the
way down to constant degree D. As a consequence, with the relative sizes of n
and q that [11] considers, the asymptotic complexity of the descent is L
Q
(1/3).
3 New algorithm: Basic ideas
The new index calculus algorithms proposed in this paper hinges on a few basic
ideas, which can be arranged into a functional discrete logarithm algorithm.
6 Antoine Joux
Basic idea 1: Homographies. In [10], it was remarked that a single polynomial
f that nicely factors can be transformed into several such polynomials, simply
by a linear change of variable: f(X) f(aX), for any non-zero constant a.
Our rst idea consists in remarking that this is also true for a larger class of
change of variables. Basically, we consider changes induced by homographies:
X
aX +b
cX +d
.
The reader might object that an homography is not going to transform f into
polynomial. To cover this, we instead perform homogeneous evaluation of f at
(aX +b)/(cX +d).
In other words, we consider the polynomial:
F
abcd
(X) = (cX +d)
deg f
f
_
aX +b
cX +d
_
.
Theorem 1. Let f(Y ) be a monic polynomial of degree D over F
q
and F
q
k be an
extension eld of F
q
. Let F
abcd
(X) = (cX+d)
deg f
f
_
aX+b
cX+d
_
with (a, b, c, d) F
4
q
k
and ad ,= bc. Write the factorization of f into monic irreducible polynomials as
f(Y ) =

k
i=1
F
i
(Y )
ei
. It induces a factorization of F
abcd
F
abcd
(X) =
k

i=1
_
(cX +d)
deg Fi
F
i
_
aX +b
cX +d
__
ei
.
Note that the factors in this decomposition are not necessary monic, not neces-
sary irreducible and may have a lower degree than the corresponding factor in
F
i
.
Proof. The induced factorization is clear. It suces to perform the change of
variable on both sides and remark that the grouped terms
(cX +d)
deg Fi
F
i
_
aX +b
cX +d
_
are indeed polynomials.
It is also clear that the transformed factors have no reason to be irreducible
in the extension eld F
q
k.
Remark that when c ,= 0 the coecient of X
deg Fi
in the factor coming from
F
i
is c
deg Fi
F
i
(a/c). Since this is not necessarily 1 and can even be 0, we see that
the transformed polynomials are not necessarily monic and may have degree
strictly smaller than the corresponding F
i
. .
Thanks to this, it is now possible to amplify a single polynomial to a much
larger extend than previously. More precisely, with a linear change of variables,
the number of amplied copies of a single polynomial is close to the size of
the nite eld in which a is picked. With homographies, the number of copies
becomes larger (see Section 4.2 for a detailed analysis).
A new index calculus algorithm in small characteristic 7
Basic idea 2: Systematic polynomial splitting. The second idea directly stems
from this fact. Since it is possible to make so many copies of one polynomial, it
suces to start from a single polynomial f. Thus, instead of considering many
polynomials until we nd some candidate, we are going to choose a polyno-
mial with factors by design. Over a small nite eld F
q
, an extremely natural
candidate to consider is:
f(X) = X
q
X.
It is well-known that this polynomial splits into linear factors, since any element
of F
q
is a root of f.
Geometrically, using the homogeneous evaluation of f (with multiplication
by (cX + d)
q+1
) at an homography h is equivalent to considering the image of
the projective line (including its point at innity) P
1
(F
q
) by h.
Basic idea 3: Field denition The image of X
q
X by an homography is a
polynomial which only contains the monomials X
q+1
, X
q
, X and 1. To obtain
a multiplicative relation, it is thus desirable to nd a nite eld representation
that transforms such a polynomial into a low degree polynomial. This can be
achieved by choosing the nite eld representation in a way that is reminiscent
both of Coppersmiths algorithm and of [11].
More precisely, we ask for a relation in F
q
n of the form:
x
q
=
h
0
(x)
h
1
(x)
.
This denes the nite eld F
q
n, if and only if, h
1
(X)X
q
h
0
(X) admits an
irreducible factor of degree n.
This construction is similar to Coppersmiths algorithm, since we require a
simple expression of the Frobenius map x x
q
. It is similar to [11], because we
do not ask for the relation to directly give an irreducible polynomial but only
require a factor of the proper degree.
The rest of the paper gives the details of how to put together these basic ideas
into a working discrete logarithm algorithm. Another application of the same
ideas has been described in [7], where a new deterministic algorithm (based on
similar heuristics to ours) is proposed to nd a provable multiplicative generator
of a nite eld.
4 Description of the new algorithm
In this section, we present the new discrete logarithm algorithm for small charac-
teristic elds that arises when putting together the basic ideas from the previous
section. We rst describe the general setting of our algorithm, before considering
its relation collection phase. We skip the description of the linear algebra phase
that takes as input the relations and outputs logarithms of the elements of our
factor basis, since it is left unchanged compared to previous algorithms. Finally,
we study the computation of individual discrete logarithms, for arbitrary eld
8 Antoine Joux
elements. This phase relies on a descent method which contains two main strate-
gies. For elements with representations of high degree, one proceeds as in [11],
while for lower degrees we introduce a new strategy based on the resolution of
multivariate systems of bilinear equations.
4.1 Choosing the parameters
Given a small characteristic nite eld F
p
n, we start be embedding it into a eld
of the form F
q
2k, with k q. This can be achieved by taking a degree e extension
of F
p
n, with e 2,log
p
n|.
After this initial embedding, the nite eld F
q
2k is constructed has a degree k
extension of F
q
2. This degree k extension is obtained by using a irreducible factor
of a low degree bivariate polynomial, evaluated at (X, X
p
). More precisely, we
follow the third idea of Section 3 and choose two low degree polynomials h
0
(X)
and h
1
(X) with coecients in F
q
2 such that h
1
(X)X
q
h
0
(X) has an irreducible
factor J(X) of degree k. This eld representation leads to the commutative
diagram in Figure 2. Heuristically, we expect arbitrary extension degrees to
appear with this form of denition polynomials. Indeed, we expect that a fraction
close to 1/k of random polynomials has a factor of degree k. Thus considering
polynomials h
0
and h
1
of degree 2, we have a very large number of degrees of
freedom and expect to get a good representation. However, this argument is not
a proof. This is emphasized by the fact that with linear polynomials h
0
and h
1
we can only reach a fraction of the possible extension degrees (see the simple
cases below).
In order to increase the condence level in this heuristic hypothesis, we have
performed some experiments in characteristic 2. This yields some numerical ev-
idence supporting the heuristic which is described in Appendix B.
Fq[X, X

]
Fq[X] Fq[X]
F
q
2k
Fp
n
X

X
q
X

h
0
(X)/h
1
(X)
Xx
Xx
Degree e extension
Fig. 2. Commutative diagram for our new algorithm
Moreover, since we have also the option of raising the degree of h
0
and h
1
to
an arbitrary constant, it should be easy to achieve any extension degree k (up
to q + deg(h
1
).)
A new index calculus algorithm in small characteristic 9
Illustration of some simple cases. Some kind of extensions are especially
well-suited to this form of representation. To illustrate our construction, we now
describe these simple cases.
A rst example concerns extensions of degree k = q 1. They can be repre-
sented as Kummer extensions by an irreducible polynomial J(X) = X
q1
g,
where g is a generator of the multiplicative group F

q
. This can be achieved easily
in our setting by letting h
0
(X) = gX and h
1
(X) = 1.
Similarly extensions of degree k = q + 1 can be represented by a Kummer
extension by an irreducible polynomial J(X) = X
q+1
+ G
q1
, where G is a
generator of the multiplicative group F

q
2
. This can be achieved easily in our
setting by letting h
0
(X) = G
q1
and h
1
(X) = X.
Alternatively, extensions of degree q + 1 can also be represented using a
twisted Kummer form, i.e. using an irreducible polynomial of the form X
q+1

AXB, with coecients A and B in F

q
. This twisted Kummer form is used for
the record computation presented in Section 8.
Another special case is k = p, which can be represented by an Artin-Schreier
extension with J(X) = X
p
X 1. This can be achieved by choosing h
0
(X) =
(X + 1) and h
1
(X) = 1. However, since our algorithm is dedicated to small
characteristic, this only leads to low degree extensions.
Action of Frobenius. When using Kummer, twisted Kummer or Artin-Schreier
extensions, the fact that the Frobenius maps X to an homography in X allows
to reduce the size of the factor basis by a factor close to the extension degree.
Indeed, we can remark that:
1. In the Kummer case:
(x +)
q
= x
q
+
q
= g(x +
q
/g).
2. In the twisted Kummer case:
(x +)
q
= x
q
+
q
=
1
x
(( +A)x +B).
3. In the Artin-Schreier case:
(x +)
p
= x
p
+
p
+ 1.
These relations yield simple linear relations between the elements of the smooth-
ness basis and allow to reduce its size. It is easy to check that similar relations
also relate polynomials of degree 2 in x.
4.2 Logarithms of linear polynomials
The rst step in the algorithm is to generate the logarithms of all linear polyno-
mials in the nite eld. As usual in index calculus, we construct multiplicative
relations between these elements. These equations can be viewed as linear equa-
tions on the values of their logarithms which are then obtained by linear algebra.
10 Antoine Joux
In order to generate the relations, we start from the polynomial identity:

Fq
(Y ) = Y
q
Y, (3)
and perform a change of variable Y =
aX+b
cX+d
, with (a, b, c, d) F
4
q
2
satisfying
ad bc ,= 0.
Evaluating Equation (3) and multiplying by (cX +d)
q+1
, we nd that:
(cX +d)

Fq
((a c)X + (b d)) = (cX +d)(aX +b)
q
(aX +b)(cX +d)
q
.
Moreover the right-hand side can be evaluated to:
(ca
q
ac
q
)X
q+1
+ (da
q
bc
q
)X
q
+ (cb
q
ad
q
)X + (db
q
bd
q
)

(ca
q
ac
q
)Xh
0
(X) + (da
q
bc
q
)h
0
(X) + (cb
q
ad
q
)Xh
1
(X) + (db
q
bd
q
)h
1
(X)
h
1
(X)
(mod J(X)).
As a consequence, we get an equality in F
q
2k between a product of linear
polynomials and a fraction with low-degree numerator and constant denomi-
nator. Considering h
1
(X) as an extra element of the smoothness basis, we get
a multiplicative relation whenever the right-hand sides numerator factors into
linear factors.
Counting the relation candidates. The above description that generates a
candidate relation from a quadruple (a, b, c, d) disregards some important struc-
ture in the set of candidates. In particular, the reader should be aware that
the same relation may be encountered several times (with dierent quadruples
(a, b, c, d)). Typically, when (a, b, c, d) F
4
q
, we obtain a trivial equation. Indeed,
in this case, for each v in a, b, c, d, we have v
q
= v. As a consequence, after
evaluation, we obtain the polynomial (ad bc)(X
q
X). Since this a just a
multiple of the basic polynomial X
q
X, this cannot form a new relation.
This is the reason why we need to take coecients
2
(a, b, c, d) in F
q
2 and to
consider a smoothness basis with coecients in F
q
2.
To understand the way Equation (3) is transformed, we need to recall a few
facts about the geometric action of homographies on a projective line. Given
a non-singular matrix M with coecients in a eld K and a point P on the
projective line P
1
(K) with homogeneous coordinates (X
P
, Y
P
), we dene the
image of P by M to be the point MP, whose coordinates are obtained by
2
At this point, there is nothing really special with F
q
2, it is just the smallest supereld
of Fq. A larger supereld would also work.
A new index calculus algorithm in small characteristic 11
multiplying the matrix M and the vector of coordinates of P. In other words,
when
M =
_
a b
c d
_
,
MP is dened as the point with homogeneous coordinates (aX
P
+ bY
P
, cX
P
+
dY
P
). It is clear that multiplying M by an arbitrary non-zero scalar does not
change the induced geometric action. Since the scalar matrices form a normal
subgroup of the invertible matrices, it is better to consider M as an element
from the corresponding quotient group which is traditionally called PGL
2
(K). It
is well known that for a nite eld K, the cardinality of PGL
2
(K) is ([K[
2
1)[K[.
Geometrically, the change of variables we considered in the Equation (3)
is equivalent to writing a polynomial equation for the image of the projective
line P
1
(F
q
) by an element of PGL
2
(F
q
2). Since PGL
2
(F
q
) leaves P
1
(F
q
) globally
invariant, it is now clear that the same equation can arise multiple times. More
precisely, for any M in PGL
2
(F
q
2) and any N in PGL
2
(F
q
), M and NM send
P
1
(F
q
) to the same image and induce the same equation. Since PGL
2
(F
q
) is
not a distinguished subgroup of PGL
2
(F
q
2), we cannot form a quotient group.
Instead, we need to regroup the matrices of PGL
2
(F
q
2) into orbits induced by
the (left-)action of PGL
2
(F
q
). One can check that this action is free and thus
that the cardinality of the set of orbits is simply the quotient of the cardinalities
of PGL
2
(F
q
2) and PGL
2
(F
q
). As a consequence, the number of orbits and, thus,
of candidate equations is:
q
6
q
2
q
3
q
= q
3
+q.
Cost of relation nding. We now would like to estimate the probability of nding
a relation for a random quadruple. Under the usual heuristic that the right-
hand sides numerator factors into linear with a probability close to a random
polynomial of the same degree, we need to perform D! trials, where D denotes the
degree of the right-hand numerator. We note that D 1 + max(deg h
0
, deg h
1
).
As a consequence, since D can heuristically be chosen as a constant, we expect
to nd enough relations by considering O(q
2
) quadruples. To avoid duplicates,
we can either use the structure of the orbits of PGL
2
(F
q
2) under the action of
PGL
2
(F
q
) or simply keep hash values of the relations to remove collisions. Since
we only need O(q
2
) distinct elements in a set of size close to q
3
, the number of
expected collisions between relations for randomly chosen quadruples (a, b, c, d)
is O(q). As a consequence, dealing with these collisions does not induce any
noticeable slow-down.
4.3 Extending the basis to degree 2 polynomials
The above process together with linear algebra can thus give us the logarithms of
linear polynomials. Unfortunately, this is not enough. Indeed, we do not know, in
general, how to compute arbitrary logarithms using a smoothness basis that only
contains linear polynomials. Instead, we extend our basis of known logarithms
to include polynomials of degree 2.
12 Antoine Joux
We rst describe a natural approach that does not work, before proposing a
successful approach that requires some additional linear algebra steps.
A natural strategy that fails. The idea of this strategy is to reconsider the
relations produced for nding the linear polynomials. But, instead of keeping
the relations with a right-hand side that splits into linear factors, it also keeps
relations with a single degree 2 factor and some linear factors. This clearly allows
us to compute the logarithm of the degree 2 polynomial.
A simple counting argument shows that in general, this approach must fail.
Indeed, on the one-hand, the number of quadratic polynomials with coecients
in F
q
2 is O(q
4
), while on the other hand, the number of relations that can be ob-
tained from homographies with coecients in F
q
2 is close to q
3
when removing
the duplicates arising from homographies with coecients in F
q
. As a conse-
quence, it is not possible to derive the logarithms of all quadratic polynomials
in this way.
It is interesting to note that if we replace the eld F
q
2 by a larger eld for
the coecients of the homographies, the natural approach becomes workable.
However, we can see that the same counting argument shows that, in general,
using F
q
3 is not good enough since a fraction of the equation are lost due to
the right-hand side splitting probability. Thus, to be able to recover the degree 2
polynomials with the simple strategy we need to, at least, use F
q
4 as our baseeld.
Since the number of linear polynomials in this case is q
4
, it is clearly preferable
to stay with F
q
2 and pay the price of constructing quadratic polynomials with
the strategy below.
A working strategy. For this second strategy, we produce some extra equa-
tions, using the same approach as for linear polynomials together with a slightly
more general change of variable. More precisely, we consider changes of the form:
Y =
aX
2
+bX +c
dX
2
+eX +f
.
With this choice, the left-hand side factors into polynomials of degree at most 2.
If the left-hand side also factors into polynomials of degree at most 2, we obtain
an equation that involves the extended basis. Once we get enough equations, it
suces to perform a linear algebra step to recover the extra logarithms.
However, this linear algebra step is much bigger than the rst one. In fact, it
is almost as expensive as initially building all linear polynomials over the larger
baseeld F
q
4. Thankfully, it is often possible to improve this, by separating the
degree 2 polynomials into several subsets which can be adressed independently.
Basically, the idea is to choose
Y =
a(X
2
+X) +b
c(X
2
+X) +d
.
With this choice, thanks to the repetition of X
2
+ X in the numerator and
denominator, all the degree 2 factors on the left are of the form X
2
+X+K. If
A new index calculus algorithm in small characteristic 13
we only keep relations with a right-hand side that factors into linear polynomials,
a set of relations that all share the same value for then produce a much
smaller linear system. Indeed, the unknowns are the logarithms of irreducible
polynomials of degree 2 from the subset X
2
+ X + K, with a xed . As a
consequence, instead of solving a large system of size O(q
4
), we need to solve
q
2
smaller system (on for each ), of size O(q
2
). This system is obtained by
selecting equations with a smooth left-hand side in a set of O(q
3
) candidates.
Depending on the exact parameters of the nite eld and the number of
logarithms that need to be computed, it might also be useful to further extend
the smoothness basis and include polynomials of higher degree (3 or more).
5 New algorithm: Descent phase
Once the logarithms of smoothness basis elements are known, we want to be able
to compute the logarithm of an arbitrary element of the nite eld. We wish to
proceed using a descent approach similar to [11]. The basic idea is to rst obtain
a good representation of the desired element into a product of polynomials whose
degrees are not too high. Then, proceeding recursively, we express the logarithms
of those polynomials as sums of logarithms of polynomials of decreasing degree.
Once we reach the polynomials of the smoothness basis, we are done.
In our context, we cannot, in general, use the preexisting method for this
descent step. Yet, we rst recall this method, discuss when it can be used and
explain why we cannot use it generally. Then, we propose an alternative method
that is more suited to the eld representations we are using. This new method
involves the resolution of bilinear multivariate systems of equations over F
q
2.
The resolution of such systems has been analyzed carefully in Spaenlehauers
PhD thesis [15] and in [4].
5.1 Practical preliminary step
Before going into the descent itself, it is useful to start by nding a good repre-
sentation of the element Z whose logarithm is desired. Initially, Z is expressed
as a polynomial of degree up to k 1 over F
q
2. Assuming that g denotes a gen-
erator of F
q
2k, we consider the decomposition of the polynomials that represent
g
i
Z, until we nd one which decomposes into elements of reasonably low degree.
These lower degree elements are then processed by the descent step.
A classical improvement on this is to use a continued fraction algorithm to
rst express g
i
Z as a quotient of two polynomials of degree at most k/2.
This preliminary step gives no improvement on the asymptotic complexity
of the descent phase.
5.2 Classical Descent method
The classical descent technique as described in [11] and recalled in Section 2.2
is based on Special-Q sieving. More precisely, it creates relations in a linear
14 Antoine Joux
subspace where by construction one side of the equation is divisible by the desired
polynomial.
In the description of this method, we have two related variables X and Y . The
relations are constructed by considering bivariate polynomials h(X, Y ), which
can lead to relations of the form h(X, f
1
(X)) = h(f
2
(Y ), Y ). To create a rela-
tion that involves a xed polynomial Q(X), we want to enforce the condition
h(X, f
1
(X)) 0 (mod Q(X)). This condition is equivalent to deg(Q) linear
equations on the coecients of h. When the baseeld is not too small, to get
enough equations, it suces to build the polynomials h as linear combination of
deg(Q) + 2 monomials.
In general characteristic, we cannot use this method in our context, because
we do not known how to create two related variables X and Y to use in this
descent step. However, with small characteristic elds, this become possible. Let
p denote the characteristic of the nite eld. We can then write q = p

and let
Y = X
p
r
, where r = /2|. Then following our construction, we see that:
Y
qp
r
= X
q
=
h
0
(X)
h
1
(X)
.
For the Kummer (or Artin-Schreier) case, where h
0
and h
1
have degree at most
one, this directly gives X as a polynomial g in Y and the usual descent can be
applied without modication. When h
0
or h
1
have higher degree, the method
still works, but we need to use a slight variation. Instead of considering the
relation h(X, X
p
r
) = h(g(Y ), Y ), we consider a relation (h(X, X
p
r
))
qp
r
=
h

(X
qp
r
, h
0
(X)/h
1
(X)), where h

is obtained from h by raising the coecient

to the power q p
r
. This has the additional advantage of completely eliminating
the auxiliary variable Y .
As seen in Section 2.2, this becomes less and less ecient as the degree of
Q decreases and the complexity is dominated by the lowest degree of Q that we
consider.
However, by itself, this method cannot descend to very low degrees which is
a problem when we want to keep a small smoothness basis. As a consequence,
we combine it with a newer method described below, which works better on low
degree polynomials.
5.3 Bilinear system based Descent
The basic idea of the new descent method we propose to complement the clas-
sical descent works as follows: given a polynomial Q, we search for a pair of
polynomials of lower degree, k
1
and k
2
such that Q(X) divides (k
1
(X)
q
k
2
(X)
k
1
(X)k
2
(X)
q
) mod J(X). As a consequence, the relation:
(k
1
(X)
q
k
2
(X) k
1
(X)k
2
(X)
q
) (k
1
(X)
q
k
2
(X) k
1
(X)k
2
(X)
q
) mod I(x),
has a factor equal to Q on the right-hand side and factors of degree at most
D
m
= max(deg k
1
, deg k
2
) on the left-hand side. Since the total degree of the
A new index calculus algorithm in small characteristic 15
right-hand side is bounded by a small multiple of D
m
(related to the degrees of h
0
and h
1
the polynomials which dened out extension eld), with good probability,
we obtain a relation between Q and polynomials of degree at most D
m
.
The question is thus to construct such polynomials k
1
and k
2
. We remark that
the condition that (k
1
(X)
q
k
2
(X) k
1
(X)k
2
(X)
q
) mod J(X) vanishes modulo Q
can be rewritten as a quadratic system of multivariate equations over F
q
. In
fact, this system is even bilinear, since each monomial that appear in it contains
at most one unknown for each of k
1
and k
2
. As a consequence, this system
can be quite eciently solved using a Grobner basis algorithm. More precisely,
consider each coecient of k
1
and k
2
as a formal unknown belonging to the
eld of coecients F
q
2. If x is one of these unknowns, we express x as x
0
+zx
1
,
where (1, z) is a polynomial basis for F
q
2 over F
q
, x
0
and x
1
are unknowns
belonging to F
q
. With this convention, we have x
q
= x
0
+z
q
x
1
and we can check
that our polynomial system of equations is indeed bilinear over F
q
. This system
contains deg Q equations over F
q
2 which are rewritten as 2 deg Q equations over
F
q
. Assuming k
1
to be unitary, the maximal number of unknowns that can t in
k
1
and k
2
is 2(deg k
1
+deg k
2
+1). However, due to the action of PGL
2
(F
q
), several
distinct pairs k
1
, k
2
yield the same polynomial for (k
1
(X)
q
k
2
(X)k
1
(X)k
2
(X)
q
).
To avoid this issue, we need to x at least one of the unknowns over F
q
2 to an
element of F
q
2 F
q
. After this, the number of remaining unknowns over F
q
is
2(deg k
1
+ deg k
2
).
At this point, we need a new heuristic argument concerning the resulting
system of equations. Namely, we require two important properties of the system
that arise after xing any additional unknowns to values. The resulting system
is bilinear and its number of unknowns N is equal to its number of equations.
We ask that with good probability this system should be zero-dimensional with
at least one solution with values in the nite eld F
q
. In order to apply this
heuristic, we need at least one extra unknown over F
q
2 that can be set to a
random value. As a consequence, we require deg k
1
+ deg k
2
deg Q+ 1.
Under this heuristic, we can analyze the cost of the bilinear descent by study-
ing the complexity of solving one such system. The main result from [4, 15] is
that this complexity is exponential in min(deg k
1
, deg k
2
). For this reason, we
do not use our descent strategy with balanced degrees deg k
1
deg k
2
), in-
stead we let d = deg k
2
parametrize the smallest of the two degrees and x
deg k
1
= deg Q+ 1 d.
We recall the complexity analysis given in [4, 15]:
Theorem 2. [Corollary 3 from [4]]
The arithmetic complexity of computing a Grobner basis of a generic bilinear
system f
1
, , f
nx+ny
K[x
0
, , x
nx1
, y
0
, , y
ny1
] with the F
5
algorithm
is upper bounded by:
O
__
n
x
+n
y
+ min(n
x
+ 1, n
y
+ 1)
min(n
x
+ 1, n
y
+ 1)
_

_
,
where 2 3 is the linear algebra constant.
16 Antoine Joux
In our application, we have n
x
= 2(deg Q+1d), n
y
= 2d and min(n
x
, n
y
) =
2d. Thus, the cost of one descent step becomes:
_
2 deg Q+ 3
2d + 1
_

.
An asymptotic choice for d is given in Section 6. It is obtained by making d
large enough to make sure that the top level nodes of the descent tree dominate
the total cost. Note that, in practical computations, the best choice is usually
to make d as large as feasible. Indeed, the feasibility of the Grobner step mostly
depends on the available amount of memory and it is important to descent as
steeply as possible to minimize the total cost.
6 Complexity Analysis
According to the heuristic argument of Section 4.1, the creation of the nite eld
representation runs in randomized polynomial time, just by trying random poly-
nomials h
0
and h
1
of degree 2 (or higher constant degree). Similarly, the creation
of the logarithms of linear and quadratic elements can be done in polynomial
time. The dominating part of this initial creation of logarithms is dominated
by the linear algebra required for the quadratic elements. Since we are solving
q
2
linear systems of dimension O(q
2
) with O(q) entries per line, the total cost
of this polynomial part is O(q
7
) arithmetic operations. Note that for Kummer
extensions,the number of linear systems is reduced to O(q), which lowers the
cost to O(q
6
).
A similar polynomial time behavior for computing the logarithms of the
smoothness basis is also given in [5].
The rest of this section analyzes the descent phases which dominates the
asymptotic cost of our algorithm.
6.1 Individual logarithms
To analyze this phase it is convenient to write k = q, for some constant
1 +
deg h1
q
. Under this hypothesis, remark that:
L
q
2k(, c) = exp((c +o(1))(2k log q)

(log(2k log q))

1
)
exp((c

+o(1))q

log(q)), where c

= (2)

c
We now give the analysis of the complexity, which shows that we can reach
complexity L(1/4 + o(1)) when the characteristic is small enough. Namely, we
require q = p

for some 2.
We start with the classical descent approach, which it is compatible with our
algorithm when 2. The analysis of this method is recalled in Section 2.2.
Since the cost increases when deg Q decreases, it suces to write the cost for
A new index calculus algorithm in small characteristic 17
the lowest degree we wish to attain, namely c
c
_
q/ log q for some constant c
c
.
The total cost in this case becomes:
exp
_
1
2
_

c
c
q
1/4
log q
5/4
_
,
where < 1.
Of course stopping at polynomials of degree O(q
1/2
) is not enough to n-
ish the computation. To continue the descent, we use the newer approach,
starting from polynomials of degree deg Q = c
c
_
q/ log q. We need to deter-
mine the value of the parameter d = deg k
2
introduced in Section 5.3. The
left-hand side in the bilinear descent contains q + 1 polynomials of degree at
most deg k
1
= deg Q + 1 d. The degree of the right-hand side is bounded by
deg k
1
(max(deg h
0
, deg h
1
) + 1), i.e., by a small multiple of deg Q, a solution of
the system yields with heuristic constant probability a new equation relating the
desired polynomial to polynomials of degree at most deg k
1
. The total number of
polynomials of degree between deg k
1
d and deg k
1
after decomposing each side
into irreducible polynomial is at most q + O(1). Note that the contribution of
lower degree polynomials to the complexity is negligible, since the computation
of their logarithms is deferred to a lower level of the computation tree, where
they represent a tiny fraction of the polynomials to be addressed.
Thus, the running time to compute the logarithm of a degree D
Q
= deg Q
polynomial is T(D
Q
, d) T
0
(D
Q
, d) + qT(D
Q
d, d). In Section 5.3, we nd
that:
T
0
(D
Q
, d) =
_
2D
Q
+ 3
2d + 1
_

.
We now choose d to ensure that T
0
(D
Q
, d) dominates the computation. This
requires d to be large enough to be able to neglect the powers of q in the sum
(when the expression of T(D
Q
, d) is unrolled). To simplify the analysis, we re-
place T
0
by T
1
(D
Q
, d) = D
6(d+1)
Q
, which is asymptotically larger. We nd that
we need to choose d such that:
q (D
q
d)
6(d+1)
D
Q
6(d+1)
.
Taking the logarithm, and using log(1 ) , it asymptotically suces to
have
d
2

D
Q
log q
6
.
With D
Q
= c
c
_
q/ log q, we can choose d =
_
_
cc
6

q log q
_
1/2
_
.
This yields:
T
1
(D
Q
, d) = exp
__
6c
c
4
+o(1)
_
q
1/4
log
5/4
q
_
.
Of course, this cost should be multiplied by the number of polynomials after
the classical descent. When < 1, the number of levels in the classical descent
18 Antoine Joux
tree is logarithmic in q and each level multiplies the number of polynomials by a
constant. As a consequence, the total number of polynomials after the classical
descent is polynomial in q and vanishes into the o(1) in the exponent of the
complexity. In order the balance the two phases of the descent, we can take:
c
c
=
1

_
2
3
,
which achieves complexity:
exp
__
1
2

_
3
2
_
1/4
+o(1)
_
q
1/4
log
5/4
q
_
.
The constant in the above complexity could be improved by taking into
account a value of the linear algebra constant < 3 and letting tend toward 1.
Note that due to the presence of an extra log
1/2
(q) term, this is strictly bigger
than L(1/4). However, it can be rewritten as L(1/4 +o(1)).
Impact of more ecient algorithms to solve the bilinear systems. It is important
to remark that given an oracle (or ecient algorithm) to solve the bilinear sys-
tems, we could use a much faster descent from degree deg Q to ,(deg Q+ 1)/2|
at each step. In this case, the complexity would be dominated by the number of
nodes in the descent tree, i.e. q
log D
. Starting directly from deg Q = k 1 would
then give a quasi-polynomial complexity exp(O(log
2
q)).
Moreover, this would get rid of the use of classical descent, together with the
constraint of having q = p

, with 2.
7 Remarks on the special case of F
p
k, p and k prime
As already mentioned, in order to use our algorithm, we need to embed F
p
k with
p and k prime into a small extension F
q
2k, with q = p
e
and e = 2,log k|. From
an asymptotic point of view, this is of little impact, indeed the complexity would
become:
exp
_
Ck
1/4
log
5/4
k
_
,
for some constant C. Since log p
k
= k log p k/2, expressed as a function of p
k
,
it becomes:
exp
_
C

log
1/4
p
k
log log
5/4
p
k
_
= L
p
k(1/4 +o(1)).
In practice, it is also interesting to consider computations in F
2
p with 1024 <
p < 2048 prime. We know from Appendix B that this can be done by taking
q = 2
11
and having polynomials h
0
and h
1
of degree 2. In this case, we expect
the complexity to be dominated by the computation of logarithms of quadratic
polynomials. This would require approximately 2
77
arithmetic operations on
numbers of p bits, since we only need the value of logarithms modulo 2
p
1.
Comparing with the most recent data of the function eld sieve [2], this L(1/3)
algorithm remains more ecient in this range.
A new index calculus algorithm in small characteristic 19
8 A couple of experiments on Kummer extensions in
characteristic 2
For practical experiments, it is very convenient to use nite elds containing
a subeld of adequate size and to chose an extension that can be represented
with polynomials h
0
and h
1
of degree 1. In practice, this means choosing a
Kummer or twisted Kummer extension, which also a reduction of the size of
the smoothness basis by a nice factor. We recently announce two computation
records that illustrate the algorithm described here in this context. For numerical
details about these records, we refer the reader to [8, 9].
8.1 A Kummer extension F
256
2255
Our rst example is representative of our algorithm in the special case of Kum-
mer extension. More precisely, we let q = 256 and consider the nite eld F
q
2k,
with k = q 1.
In this computation, the most costly part is the linear algebra step for com-
puting the discrete logarithms of approximately 2
22
quadratic polynomials. This
is decomposed into 129 independent linear systems, one containing 2
14
elements
and 128 with 2
15
elements. On average, these system contain 128 non-zero coef-
cients per line.
An initial phase of continued fractions reduced the problem to computed
logarithms of polynomials of degree at most 29. The classical descent step was
used to reduce this down to degree 12. The bilinear system approach permitted
to conclude the computation.
The total cost of the individual logarithm was approximately one half of the
cost of linear algebra. However, by using improved parameter choices (as in the
next computation), it would be possible to reduce this by a large factor.
8.2 A twisted Kummer extension F
256
3257
This second example is interesting because it shows that pairing-based cryptog-
raphy over F
2
257 cannot be secure. However, it is too specic to be representative,
indeed, it crucially relies on the fact that F
256
3 = F
64
4.
The main specicity of this computation is a descent strategy, similar to
the one presented in [6], that allows a descent from polynomials of degree 2 to
polynomials of degree 1. This requires 3 conditions, the use of a Kummer or
twisted Kummer extension, the replacement of the eld of coecients F
q
2 by
F
q
3 and the use of two dierent polynomials to generate the systematic side of
relations. Namely, we used both X
256
+X and (X
64
+X)
4
.
As a direct consequence, the costly phase of generating quadratic polynomi-
als as a whole is removed. Thus, the computation becomes dominated by the
descent phase. Compared to the previous computation, this was largely opti-
mized. Indeed, the cost of the descent in this computation is about 1/10 of the
descent in the previous example.
20 Antoine Joux
Acknowledgements
We acknowledge that the results in this paper have been achieved using the
PRACE Research Infrastructure resource Curie based in France at TGCC, Bruy`eres-
le-Chatel (project number 2011050868) and the PRACE Research Infrastructure
resource Jugene/Juqueen based in Germany at the J ulich Supercomputing Cen-
tre (project number 2011050868).
References
1. Leonard M. Adleman and Ming-Deh A. Huang. Function eld sieve method for
discrete logarithms over nite elds. In Information and Computation, volume 151,
pages 516. Academic Press, 1999.
2. Razvan Barbulescu, Cyril Bouvier, Jeremie Detrey, Pierrick Gaudry, Hamza Jeljeli,
Emmanuel Thome, Marion Videau, and Paul Zimmermann. Discrete logarithm in
GF(2
809
) with FFS. IACR Cryptology ePrint Archive, 2013:197, 2013.
3. Don Coppersmith. Fast evaluation of logarithms in elds of characteristic two.
IEEE transactions on information theory, IT-30(4):587594, July 1984.
4. Jean-Charles Faug`ere, Mohab Safey El Din, and Pierre-Jean Spaenlehauer.
Gr obner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1):
Algorithms and complexity. Journal Of Symbolic Computation, 46(4):406437,
2011.
5. Faruk Gologlu, Robert Granger, Gary McGuire, and Jens Zumbr agel. On the
function eld sieve and the impact of higher splitting probabilities: Application to
discrete logarithms in F
2
1971. IACR Cryptology ePrint Archive, 2013/074, 2013.
6. Faruk G ologlu, Robert Granger, Gary McGuire, and Jens Zumbr agel. Solving a
6120-bit DLP on a desktop computer. IACR Cryptology ePrint Archive, 2013/306,
2013.
7. Ming-Deh Huang and Anand Kumar Narayanan. Finding primitive elements in
nite elds of small characteristic. CoRR, abs/1304.1206, 2013.
8. Antoine Joux. Discrete logarithms in GF(2
4080
). NMBRTHRY list, March 2013.
9. Antoine Joux. Discrete logarithms in GF(2
6168
)= GF((2
257
)
24
). NMBRTHRY list,
May 2013.
10. Antoine Joux. Faster index calculus for the medium prime case application to
1175-bit and 1425-bit nite elds. In EUROCRYPT, pages 177193, 2013.
11. Antoine Joux and Reynald Lercier. The function eld sieve in the medium prime
case. In Serge Vaudenay, editor, EUROCRYPT2006, volume 4004 of Lecture Notes
in Computer Science, pages 254270. Springer, 2006.
12. Antoine Joux, Reynald Lercier, Nigel P. Smart, and Frederik Vercauteren. The
number eld sieve in the medium prime case. In CRYPTO, pages 326344, 2006.
13. Daniel Panario, Xavier Gourdon, and Philippe Flajolet. An analytic approach
to smooth polynomials over nite elds. In J. Buhler, editor, Algorithmic Num-
ber Theory, Proceedings of the ANTS-III conference, volume 1423, pages 226236.
Springer, 1998.
14. Igor Semaev. An algorithm for evaluation of discrete logarithms in some nonprime
nite elds. Mathematics of Computation, 67:16791689, 1998.
15. Pierre-Jean Spaenlehauer. Solving multihomogeneous and determinantal systems
Algorithms - Complexity - Applications. PhD thesis, Universite Pierre et Marie
Curie (UPMC), 2012.
A new index calculus algorithm in small characteristic 21
A Alternative polynomials
Throughout the paper, we used the polynomial X
q
X as our starting point.
However, it is also possible to use other polynomials for this purpose. In order to
be usable in our algorithm, a polynomial needs to satisfy two basic properties.
First, it should factor into linear factors over a small degree extension of F
q
.
Second, it should be possible to write it as a low degree polynomial in X and
X
q
.
Two possible alternative polynomials are X
q+1
1 and X
q+1
+ 1 which
factor into linear terms over F
q
2. Another possibility is to use X
q+1
X + 1 or
X
q+1
+ X + 1 which factor into linear terms over F
q
3. For example, let us this
factorization in the case of X
q+1
X+1. Let x denote a root of this polynomial
in F
q
. It is clear that x satises:
x
q
=
x 1
x
.
As a consequence:
x
q
2
=
x
q
1
x
q
=
1
x 1
,
and
x
q
3
=
1
x
q
1
= x.
Thus x belongs to F
q
3. The polynomials X
q+1
X + 1 are very closely related
to the discrete logarithm approach proposed in [5].
A.1 Equivalence of using the alternative polynomials
Assume that we are working with a subeld F
q
of characteristic q. Dene v to be
a root of X
q+1
1 in F
q
2. Consider now the homography given by the quadruple
(a, b, c, d) = (v, 1, 1, v). It is easy to check that the image of X
q
X by this
homography is:
(ca
q
ac
q
)X
q+1
+ (da
q
bc
q
)X
q
+ (cb
q
ad
q
)X + (db
q
bd
q
)
(v
q
v)X
q+1
+ (v
q+1
1)X
q
+ (1 v
q+1
)X + (v v
q
)
(v
q
v)(X
q+1
1).
Up to a multiplicative constant, this yields the polynomial X
q+1
1.
Similarly, if v denotes a root of X
q+1
+ 1 in F
q
2, consider the homography
induced by the quadruple (a, b, c, d) = (v, 1, 1, v). The image of X
q
X is:
(ca
q
ac
q
)X
q+1
+ (da
q
bc
q
)X
q
+ (cb
q
ad
q
)X + (db
q
bd
q
)
(v
q
v)X
q+1
+ (v
q+1
+ 1)X
q
+ (1 v
q+1
)X + (v +v
q
)
(v
q
v)(X
q+1
+ 1).
22 Antoine Joux
As a consequence, the polynomials X
q+1
1 can be obtained by applying
a well-chosen homography to X
q
X. Thus, they do not generate any extra
multiplicative relations in the nite eld.
Similarly, the use of X
q+1
X + 1 is equivalent to the use of X
q
X when
taking coecients in F
q
3. To see that, dene v to be a root of X
q+1
X + 1 in
F
q
3. Consider the homography given by (a, b, c, d) = (v, v 1, 1, v). We see that
after applying the homography, X
q
X becomes:
(ca
q
ac
q
)X
q+1
+ (da
q
bc
q
)X
q
+ (cb
q
ad
q
)X + (db
q
bd
q
)
(v
q
v)X
q+1
+ (v
q+1
v + 1)X
q
+ (v
q
1 v
q+1
)X + (v
q+1
v v
q+1
+v
q
)
(v
q
v)(X
q+1
+X + 1).
Finally, with v a root of X
q+1
+X + 1 in F
q
3 and the homography given by
(a, b, c, d) = (v, v 1, 1, v), we nd after applying the homography:
(ca
q
ac
q
)X
q+1
+ (da
q
bc
q
)X
q
+ (cb
q
ad
q
)X + (db
q
bd
q
)
(v
q
v)X
q+1
+ (v
q+1
+v + 1)X
q
+ (v
q
1 v
q+1
)X + (v
q+1
v +v
q+1
+v
q
)

(v
q
v)(X
q+1
X + 1).
As a consequence, we see that the four natural alternative polynomials that
can be used with coecients in F
q
2 or F
q
3 turn out to be equivalent to the use
of X
q
X.
B Evidence for the existence of the h
0
and h
1
polynomials
Since our algorithm replies on the existence of low degree polynomials h
0
and h
1
such that h
1
(X) X
q
h
0
(X) has a factor of degree k, it is important to study
this heuristic hypothesis in more details.
In this appendix, we give some practical evidence for the existence of such
polynomials in some practically interesting case. Assume that we wish to com-
pute discrete logarithm inF
2
p for a prime p in the interval [2
10
, 2
11
]. We expect
this to be achievable by embedding the nite eld in F
2
11p, i.e. by taking q = 2
11
.
We dene the nite eld F
q
as F
2
[a], with a
11
+a
2
+1 = 0, and search for good
polynomials h
0
and h
1
with coecient in F
q
.
The result of this search is given in Table 1. It shows that all of the desired
extension elds can be represented with polynomials h
0
and h
1
of degree 2.
A new index calculus algorithm in small characteristic 23
Extension Degree h
0
h
1
Extension Degree h
0
h
1
1031 X
2
+ a
1555
X + a
148
X
2
+ a
1962
X + a
1465
1033 X
2
+ a
277
X + a
702
X
2
+ a
131
X + a
1619
1039 X
2
+ a
1161
X + a
498
X
2
+ a
1519
X + a
1482
1049 X
2
+ a
1768
X + a
709
X
2
+ a
131
X + a
283
1051 X
2
+ a
1967
X + a
1919
X
2
+ a
304
X + a
272
1061 X
2
+ a
638
X + a
1905
X
2
+ a
347
X + a
651
1063 X
2
+ a
1079
X + a
525
X
2
+ a
904
X + a
2029
1069 X
2
+ a
1050
X + a
1725
X
2
+ a
1842
X + a
1551
1087 X
2
+ a
421
X + a
1405
X
2
+ a
1404
X + a
901
1091 X
2
+ a
609
X + a
1744
X
2
+ a
1945
X + a
781
1093 X
2
+ a
608
X + a
468
X
2
+ a
342
X + a
1200
1097 X
2
+ a
1603
X + a
452
X
2
+ a
1910
X + a
1892
1103 X
2
+ a
155
X + a
1694
X
2
+ a
732
X + a
779
1109 X
2
+ a
414
X + a
612
X
2
+ a
656
X + a
1029
1117 X
2
+ a
409
X + a
1303
X
2
+ a
1591
X + a
1159
1123 X
2
+ a
46
X + a
1131
X
2
+ a
1615
X + a
1379
1129 X
2
+ a
194
X + a
315
X
2
+ a
1379
X + a
1184
1151 X
2
+ a
394
X + a
391
X
2
+ a
1305
X + a
125
1153 X
2
+ a
1673
X + a
171
X
2
+ a
870
X + a
302
1163 X
2
+ a
694
X + a
1368
X
2
+ a
220
X + a
24
1171 X
2
+ a
771
X + a
1996
X
2
+ a
306
X + a
805
1181 X
2
+ a
506
X + a
2018
X
2
+ a
326
X + a
1698
1187 X
2
+ a
1351
X + a
1709
X
2
+ a
1810
X + a
1518
1193 X
2
+ a
845
X + a
42
X
2
+ a
572
X + a
900
1201 X
2
+ a
1053
X + a
175
X
2
+ a
734
X + a
1402
1213 X
2
+ a
1562
X + a
1541
X
2
+ a
597
X + a
704
1217 X
2
+ a
715
X + a
1251
X
2
+ a
1085
X + a
147
1223 X
2
+ a
807
X + a
1818
X
2
+ a
599
X + a
162
1229 X
2
+ a
397
X + a
1837
X
2
+ a
823
X + a
245
1231 X
2
+ a
1750
X + a
356
X
2
+ a
59
X + a
724
1237 X
2
+ a
572
X + a
922
X
2
+ a
1784
X + a
2037
1249 X
2
+ a
673
X + a
902
X
2
+ a
43
X + a
877
1259 X
2
+ a
1700
X + a
1480
X
2
+ a
1780
X + a
1750
1277 X
2
+ a
1380
X + a
1484
X
2
+ a
1861
X + a
538
1279 X
2
+ a
431
X + a
1433
X
2
+ a
1695
X + a
438
1283 X
2
+ a
493
X + a
208
X
2
+ a
85
X + a
1672
1289 X
2
+ a
1934
X + a
1863
X
2
+ a
1273
X + a
1829
1291 X
2
+ a
375
X + a
524
X
2
+ a
1236
X + a
1945
1297 X
2
+ a
1921
X + a
1736
X
2
+ a
598
X + a
1530
1301 X
2
+ a
1029
X + a
478
X
2
+ a
1434
X + a
1418
1303 X
2
+ a
1194
X + a
1801
X
2
+ a
208
X + a
1592
1307 X
2
+ a
1754
X + a
626
X
2
+ a
235
X + a
979
1319 X
2
+ a
1437
X + a
282
X
2
+ a
148
X + a
744
1321 X
2
+ a
982
X + a
1089
X
2
+ a
1632
X + a
1598
1327 X
2
+ a
1455
X + a
181
X
2
+ a
508
X + a
373
1361 X
2
+ a
1451
X + a
882
X
2
+ a
1035
X + a
634
1367 X
2
+ a
331
X + a
198
X
2
+ a
1167
X + a
1818
1373 X
2
+ a
459
X + a
1461
X
2
+ a
946
X + a
957
1381 X
2
+ a
45
X + a
1524
X
2
+ a
1816
X + a
766
1399 X
2
+ a
684
X + a
1574
X
2
+ a
580
X + a
1611
1409 X
2
+ a
1439
X + a
454
X
2
+ a
1599
X + a
1039
1423 X
2
+ a
792
X + a
1028
X
2
+ a
940
X + a
1662
1427 X
2
+ a
345
X + a
908
X
2
+ a
1392
X + a
864
1429 X
2
+ a
667
X + a
1656
X
2
+ a
1867
X + a
830
1433 X
2
+ a
219
X + a
362
X
2
+ a
141
X + a
1881
1439 X
2
+ a
1417
X + a
1761
X
2
+ a
1224
X + a
766
1447 X
2
+ a
994
X + a
1216
X
2
+ a
15
X + a
756
1451 X
2
+ a
718
X + a
766
X
2
+ a
509
X + a
702
1453 X
2
+ a
1180
X + a
129
X
2
+ a
130
X + a
1659
1459 X
2
+ a
619
X + a
782
X
2
+ a
1423
X + a
793
1471 X
2
+ a
757
X + a
210
X
2
+ a
1192
X + a
1976
1481 X
2
+ a
1880
X + a
882
X
2
+ a
773
X + a
339
1483 X
2
+ a
670
X + a
20
X
2
+ a
24
X + a
1514
1487 X
2
+ a
1972
X + a
1964
X
2
+ a
1370
X + a
528
1489 X
2
+ a
1501
X + a
116
X
2
+ a
866
X + a
694
1493 X
2
+ a
1957
X + a
987
X
2
+ a
979
X + a
781
1499 X
2
+ a
1456
X + a
1644
X
2
+ a
1479
X + a
600
1511 X
2
+ a
279
X + a
1360
X
2
+ a
591
X + a
1944
1523 X
2
+ a
810
X + a
25
X
2
+ a
1924
X + a
927
1531 X
2
+ a
1415
X + a
632
X
2
+ a
1575
X + a
911
1543 X
2
+ a
1957
X + a
1106
X
2
+ a
1098
X + a
1111
1549 X
2
+ a
140
X + a
498
X
2
+ a
513
X + a
1876
1553 X
2
+ a
1109
X + a
883
X
2
+ a
1256
X + a
524
1559 X
2
+ a
485
X + a
1312
X
2
+ a
1102
X + a
847
1567 X
2
+ a
908
X + a
128
X
2
+ a
188
X + a
194
1571 X
2
+ a
29
X + a
1916
X
2
+ a
1825
X + a
1266
1579 X
2
+ a
953
X + a
1192
X
2
+ a
1113
X + a
1334
1583 X
2
+ a
792
X + a
1459
X
2
+ a
1115
X + a
645
1597 X
2
+ a
874
X + a
1697
X
2
+ a
387
X + a
763
1601 X
2
+ a
138
X + a
1728
X
2
+ a
1623
X + a
961
1607 X
2
+ a
737
X + a
119
X
2
+ a
1858
X + a
1788
1609 X
2
+ a
1641
X + a
355
X
2
+ a
1823
X + a
963
1613 X
2
+ a
801
X + a
730
X
2
+ a
193
X + a
292
1619 X
2
+ a
1715
X + a
167
X
2
+ a
510
X + a
1166
1621 X
2
+ a
1359
X + a
745
X
2
+ a
1157
X + a
145
1627 X
2
+ a
1560
X + a
1074
X
2
+ a
1631
X + a
1624
1637 X
2
+ a
575
X + a
1741
X
2
+ a
1620
X + a
110
1657 X
2
+ a
1727
X + a
1064
X
2
+ a
1968
X + a
1714
1663 X
2
+ a
960
X + a
270
X
2
+ a
744
X + a
157
1667 X
2
+ a
176
X + a
536
X
2
+ a
1208
X + a
1919
1669 X
2
+ a
229
X + a
407
X
2
+ a
1723
X + a
1999
1693 X
2
+ a
73
X + a
642
X
2
+ a
889
X + a
489
1697 X
2
+ a
441
X + a
722
X
2
+ a
1454
X + a
1566
1699 X
2
+ a
387
X + a
1300
X
2
+ a
44
X + a
684
1709 X
2
+ a
1475
X + a
1582
X
2
+ a
63
X + a
1779
1721 X
2
+ a
1051
X + a
846
X
2
+ a
1536
X + a
1506
1723 X
2
+ a
1493
X + a
1551
X
2
+ a
1293
X + a
1781
1733 X
2
+ a
1536
X + a
708
X
2
+ a
836
X + a
1518
1741 X
2
+ a
1215
X + a
455
X
2
+ a
2013
X + a
1400
1747 X
2
+ a
978
X + a
1676
X
2
+ a
1444
X + a
1102
1753 X
2
+ a
450
X + a
1685
X
2
+ a
392
X + a
136
1759 X
2
+ a
1010
X + a
1438
X
2
+ a
1215
X + a
63
1777 X
2
+ a
1293
X + a
249
X
2
+ a
569
X + a
554
1783 X
2
+ a
150
X + a
1608
X
2
+ a
1185
X + a
1061
1787 X
2
+ a
1563
X + 1 X
2
+ a
1766
X + a
1790
1789 X
2
+ a
1435
X + a
1084
X
2
+ a
264
X + a
770
1801 X
2
+ a
1713
X + a
678
X
2
+ a
1656
X + a
1626
1811 X
2
+ a
1809
X + a
2036
X
2
+ a
1859
X + a
525
1823 X
2
+ a
659
X + a
567
X
2
+ a
147
X + a
962
1831 X
2
+ a
1384
X + a
170
X
2
+ a
550
X + a
2035
1847 X
2
+ a
885
X + a
964
X
2
+ a
701
X + a
1221
1861 X
2
+ a
1932
X + a
1701
X
2
+ a
158
X + a
1250
1867 X
2
+ a
1363
X + a
1836
X
2
+ a
307
X + a
735
1871 X
2
+ a
749
X + a
1955
X
2
+ a
499
X + a
166
1873 X
2
+ a
757
X + a
200
X
2
+ a
971
X + a
601
1877 X
2
+ a
758
X + a
500
X
2
+ a
943
X + a
1832
1879 X
2
+ a
289
X + a
1359
X
2
+ a
913
X + a
840
1889 X
2
+ a
1076
X + a
1002
X
2
+ a
1431
X + a
476
1901 X
2
+ a
752
X + a
1060
X
2
+ a
269
X + a
1793
1907 X
2
+ a
1954
X + a
1856
X
2
+ a
255
X + a
316
1913 X
2
+ a
1142
X + a
578
X
2
+ a
1118
X + a
1052
1931 X
2
+ a
1529
X + a
777
X
2
+ a
1631
X + a
285
1933 X
2
+ a
600
X + a
509
X
2
+ a
1477
X + a
598
1949 X
2
+ a
839
X + a
1766
X
2
+ a
1232
X + a
226
1951 X
2
+ a
1016
X + a
1143
X
2
+ a
1624
X + a
1871
1973 X
2
+ a
722
X + a
769
X
2
+ a
834
X + a
1277
1979 X
2
+ a
1007
X + a
1464
X
2
+ a
966
X + a
912
1987 X
2
+ a
1002
X + a
682
X
2
+ a
1255
X + a
1006
1993 X
2
+ a
709
X + a
1676
X
2
+ a
638
X + a
957
1997 X
2
+ a
1653
X + a
1899
X
2
+ a
29
X + a
867
1999 X
2
+ a
104
X + a
1482
X
2
+ a
1019
X + a
649
2003 X
2
+ a
328
X + a
701
X
2
+ a
554
X + a
176
2011 X
2
+ a
1510
X + a
1241
X
2
+ a
1524
X + a
741
2017 X
2
+ a
1572
X + a
1645
X
2
+ a
814
X + a
298
2027 X
2
+ a
1878
X + a
1243
X
2
+ a
1474
X + a
1124
2029 X
2
+ a
1502
X + a
1998
X
2
+ a
982
X + a
721
2039 X
2
+ a
1871
X + a
1848
X
2
+ a
1346
X + a
1272
Table 1. Representation of Fq
p by X
q
= h0(X)/h1(X) for q = 2
11