In this talk, we consider the computation of discrete logarithms in all finite fields GF(q) where q=p^n. In a first part, we show that a simple variation of the function field sieve can be used whenever p is smaller than L(1/3)[q].
This variation of the function field sieve can be described in elementary terms, using only finite fields and polynomials. In a second part, we show that a companion algorithm based on the number field sieve, can be used for larger values of p. Then we study the complexity of these algorithms and show that put together, they yield L(1/3) complexity for the discrete logarithm problem in all finite fields.
Interestingly, depending on the exact relation between p and p^n, the constant \alpha when writing the complexity as L(1/3, \alpha) greatly varies.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.