Discrete Logarithm Factory

Haetham AL ASWAD; Cécile PIERROT; Emmanuel THOMÉ

Paper 2023/834

Discrete Logarithm Factory

Haetham AL ASWAD

, University of Lorraine, French National Centre for Scientific Research, Inria Nancy - Grand-Est research centre

Cécile PIERROT, University of Lorraine, French National Centre for Scientific Research, Inria Nancy - Grand-Est research centre

Emmanuel THOMÉ, University of Lorraine, French National Centre for Scientific Research, Inria Nancy - Grand-Est research centre

Abstract

The Number Field Sieve and its variants are the best algorithms to solve the discrete logarithm problem in finite fields. The Factory variant accelerates the computation when several prime fields are targeted. This article adapts the Factory variant to non-prime finite fields of medium and large characteristic. We combine this idea with two other variants of NFS, namely the tower and special variant. This combination leads to improvements in the asymptotic complexity. Besides, we lay out estimates of the practicality of this method for 1024-bit targets and extension degree $6$.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Public Key Finite Fields Discrete Logarithm Discrete Logarithm Factory Number Field Sieve Tower NFS Special NFS
Contact author(s): haetham al-aswad @ inria fr
cecile pierrot @ inria fr
emmanuel thome @ inria fr
History: 2023-10-14: last of 2 revisions; 2023-06-05: received; See all versions
Short URL: https://ia.cr/2023/834
License: CC BY

BibTeX

@misc{cryptoeprint:2023/834,
      author = {Haetham AL ASWAD and Cécile PIERROT and Emmanuel THOMÉ},
      title = {Discrete Logarithm Factory},
      howpublished = {Cryptology ePrint Archive, Paper 2023/834},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/834}},
      url = {https://eprint.iacr.org/2023/834}
}