• Weil's bounds
• discrete log

Given a group G and two elements g,h ∈ G, solving the discrete logarithm problem consists of finding an integer x ∈ Z such that g^x = h, if it exists. Its connection to many cryptographic protocols has motivated a large amount of research intended to find efficient algorithms to solve this problem for special groups, like the group of rational points of an elliptic curve over a finite field or the group of invertible elements of a finite field.
Among these cryptographic protocols some are very general and can be implemented in every group, while others are more specific: for example, the security of the digital signature standard is based on the assumption that the discrete logarithm problem is computationally hard for the multiplicative groups of finite fields of prime order. The study of the discrete logarithm problem over finite fields of “small” characteristic has become important since the use of pairing attacks on the discrete logarithm problem for elliptic curves.

Recently the work of A. Joux has led to algorithms heuristically faster than the previous ones for the discrete logarithm problem over finite fields of small characteristic, i.e. fields of prime characteristic p and cardinality p n for some n > p. This progress is the central topic of the thesis: we study the connection of the new algorithms with the previous ones and we show how the new ideas can be used to rigorously prove that the complexity of the discrete logarithm problem in small characteristic is at most quasi-polynomial.

In the first chapter we analyze classical algorithms that fall in the category of the index calculus whose complexity has the form
L[α,c] := exp{(c + o(1))(log(p^n) )^α (loglog(p^n^ )^(1−α) }
for real numbers c > 0, and α ∈ (0,1) (sub-exponential complexity). The common idea of these algorithms comes from the Morrison-Brillhart factorization method and consists of seeking for polynomials with irreducible factors of small degree. In particular, their analysis needs estimates of this probability in specific situations.
We look at the simplest algorithm of index calculus in two different forms: the first one to show clearly the ideas, the second to make rigorous analysis and prove that the expected running time is L[1/2,c]. Then we turn our attention to the function field sieve which is a family of algorithms of complexity L[1/3,c].We focus on the algorithm presented by Coppersmith in 1984, that could be seen as a “father” of the actual function field sieve, published by Adleman ten years later. This choice is motivated by the resemblance between Coppersmith’s and Joux’s algorithms.

In the second chapter we look at the recent developments. We analyze the ideas contained in Joux’s article “A new index calculus algorithm of complexity L[1/4,c] in small characteristic” and we see how these ideas lead to a quasi-polynomial algorithm, i.e. an algorithm having complexity exp{O((loglogp n ) c )}for some c > 0. Indeed, in 2014 Joux together with Barbulescu, Gaudry and Thomé has published an article that, under some heuristic assumptions on the probability of certain families of polynomials to be factored in terms of polynomial of “smaller degree”, solves the discrete logarithm problem in quasi-
polynomial time on every finite field admitting a certain kind of presentation.
Then we analyze another quasi-polynomial algorithm published by Granger, Kleinjung and Zumbrägel based on the same ideas: this algorithm can be rigorously analyzed and proves without any heuristic assumption that the discrete logarithm problem has at most quasi-polynomial complexity on every finite field admitting that certain kind of presentation.

In the last chapter we define another kind of presentation for finite fields of small characteristic, similar to the one seen in the second chapter, and we describe a new version of Granger’s algorithm adapted to this setting. Using the classical theory of elliptic curves over finite fields we prove that any finite field of small characteristic can be embedded into a slightly larger field that admits a presentation of this new type. Thus our algorithm can be applied to solve the discrete logarithm problem for every finite fields of small characteristic and can be proved to run in quasi-polynomial time. At the moment we unfortunately only have a partial proof of the correctness of our algorithm: we reduce it to the proof of two similar technical statements and we give a full proof of one of these
two statements with the use of some intersection theory and of the Riemann hypothesis for curves over finite fields. We expect that the other statement is provable by similar arguments, despite the difficulties in the calculations.