Paper 2018/647

A new perspective on the powers of two descent for discrete logarithms in finite fields

Thorsten Kleinjung and Benjamin Wesolowski

Abstract

A new proof is given for the correctness of the powers of two descent method for computing discrete logarithms. The result is slightly stronger than the original work, but more importantly we provide a unified geometric argument, eliminating the need to analyse all possible subgroups of $\mathrm{PGL}_2(\mathbb{F}_q)$. Our approach sheds new light on the role of $\mathrm{PGL}_2$, in the hope to eventually lead to a complete proof that discrete logarithms can be computed in quasi-polynomial time in finite fields of fixed characteristic.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. ANTS-XIII, Thirteenth Algorithmic Number Theory Symposium
Keywords
discrete logarithm problem
Contact author(s)
benjamin wesolowski @ epfl ch
History
2018-07-06: received
Short URL
https://ia.cr/2018/647
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/647,
      author = {Thorsten Kleinjung and Benjamin Wesolowski},
      title = {A new perspective on the powers of two descent for discrete logarithms in finite fields},
      howpublished = {Cryptology ePrint Archive, Paper 2018/647},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/647}},
      url = {https://eprint.iacr.org/2018/647}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.