Discrete logarithm in GF(2^809) with FFS

Razvan Barbulescu; Cyril Bouvier; Jérémie Detrey; Pierrick Gaudry; Hamza Jeljeli; Emmanuel Thomé; Marion Videau; Paul Zimmermann

Paper 2013/197 Original: eprint.iacr.org/2013/197 ↗

Discrete logarithm in GF(2^809) with FFS

Razvan Barbulescu

Cyril Bouvier

Jérémie Detrey

Pierrick Gaudry

Hamza Jeljeli

Emmanuel Thomé

Marion Videau

Paul Zimmermann

Abstract

The year 2013 has seen several major complexity advances for the discrete logarithm problem in multiplicative groups of small characteristic finite fields. These outmatch, asymptotically, the Function Field Sieve (FFS) approach, which was so far the most efficient algorithm known for this task. Yet, on the practical side, it is not clear whether the new algorithms are uniformly better than FFS. This article presents the state of the art with regard to the FFS algorithm, and reports data from a record-sized discrete logarithm computation in a prime-degree extension field.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2013-11-05: last updated; 2013-04-09: published
Short URL: https://ia.cr/2013/197
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2013/197,
      author = {Razvan Barbulescu and Cyril Bouvier and Jérémie Detrey and Pierrick Gaudry and Hamza Jeljeli and Emmanuel Thomé and Marion Videau and Paul Zimmermann},
      title = {Discrete logarithm in GF(2^809) with FFS},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/197},
      year = {2013},
      url = {https://eprint.iacr.org/2013/197}
}