Computing Discrete Logarithms in Finite Fields Faster with Galois automorphisms

The Number Field Sieve (NFS) algorithm and its variants are the best algorithms to solve the discrete logarithm problem in finite fields. We will first take a look on how NFS works, and second, explore how Galois automorphisms can accelerate the hardest steps of NFS by quite large factors. We discuss an open problem of using Galois automorphisms of any order, and present our work that solves the problem for the two orders 6 and 12—whereas the previous solved orders stand at the only order 2. Consequently, this brings acceleration factors approximately equal to 36 and 144 to one of the two hardest steps in NFS, surpassing the prior record acceleration factor of 4. The work can be found here

Prior knowledge of NFS is not required.