• About
  • Members
  • Seminar
  • Visitors
  • Publications
  • Conferences
  • Magma
  • Login
Computational Algebra Group
Computational Algebra Seminar
  • 2000-2004
  • 2005-2009
  • 2010-2014
  • 2015
  • 2016
  • 2017
  • 2018
  • 2024
  • 2025
  • Frederik Vercauteren
  • (KU Leuven)
  • The number field sieve in the medium prime case
  • 3pm–4pm, Thursday 19th October, 2006
  • Carslaw 173
  • This talk describes several variations of the number field sieve to compute discrete logarithms in finite fields of the form GF(pn), with p a medium to large prime. We show that when n is not too large, this yields a Lpn(1/3) algorithm with efficiency similar to that of the regular number field sieve over prime fields. This approach complements the recent results of Joux and Lercier on the function field sieve. Combining both results, we deduce that computing discrete logarithms have heuristic complexity Lpn(1/3) in all finite fields. To illustrate the efficiency of the algorithm, we provide details of a discrete logarithm computation in a 120-digit finite field Fp3.

The Computational Algebra Group is a research group within the School of Mathematics and Statistics, University of Sydney.
Copyright © 2010-2025 Computational Algebra Group.