Paper 2014/924

Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms - Simplified Setting for Small Characteristic Finite Fields

Antoine Joux and Cécile Pierrot

Abstract

In this paper, we revisit the recent small characteristic discrete logarithm algorithms. We show that a simplified description of the algorithm, together with some additional ideas, permits to obtain an improved complexity for the polynomial time precomputation that arises during the discrete logarithm computation. With our new improvements, this is reduced to O(q^6), where q is the cardinality of the basefield we are considering. This should be compared to the best currently documented complexity for this part, namely O(q^7). With our simplified setting, the complexity of the precomputation in the general case becomes similar to the complexity known for Kummer (or twisted Kummer) extensions.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2014
Keywords
discrete logarithm problemfinite fields
Contact author(s)
Cecile Pierrot @ lip6 fr
History
2014-11-11: received
Short URL
https://ia.cr/2014/924
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/924,
      author = {Antoine Joux and Cécile Pierrot},
      title = {Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms - Simplified Setting for Small Characteristic Finite Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2014/924},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/924}},
      url = {https://eprint.iacr.org/2014/924}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.