Paper 2019/751 Original: eprint.iacr.org/2019/751 ↗
Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
Abstract
We prove that the discrete logarithm problem can be solved in quasi-polynomial expected time in the multiplicative group of finite fields of fixed characteristic. More generally, we prove that it can be solved in the field of cardinality $p^n$ in expected time $(pn)^{2\log_2(n) + O(1)}$.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2021-09-10: last updated
- 2019-06-25: published
- Short URL
- https://ia.cr/2019/751
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2019/751,
author = {Thorsten Kleinjung and Benjamin Wesolowski},
title = {Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/751},
year = {2019},
url = {https://eprint.iacr.org/2019/751}
}