Paper 2023/834
Discrete Logarithm Factory
Abstract
The Number Field Sieve and its variants are the best algorithms to solve the discrete logarithm problem in finite fields (except for the weak small characteristic case). 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. A precomputation, solely dependent on an approximate finite field size and an extension degree, allows to efficiently compute discrete logarithms in a constant proportion of the finite fields of the given approximate size and extension degree. We combine this idea with two other variants of NFS, namely the tower and special variant. This combination improves the asymptotic complexity. We also notice that combining our approach with the MNFS variant would be an unnecessary complication as all the potential gain of MNFS is subsumed by our Factory variant anyway. Furthermore, we demonstrate how Chebotarev's density theorem allows to compute the density of finite fields that can be solved with a given precomputation. Finally, we provide experimental data in order to assess the practical reach of our approach.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published by the IACR in CIC 2024
- DOI
- 10.62056/ah2ip2fgx
- Keywords
- Public KeyFinite FieldsDiscrete LogarithmDiscrete Logarithm FactoryNumber Field SieveTower NFSSpecial NFS
- Contact author(s)
-
haetham al-aswad @ inria fr
cecile pierrot @ inria fr
emmanuel thome @ inria fr - History
- 2024-10-10: last of 4 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},
doi = {10.62056/ah2ip2fgx},
url = {https://eprint.iacr.org/2023/834}
}