Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
arXiv:1906.10668v220 citations
Originality Highly original
AI Analysis
This is a foundational breakthrough for cryptography, as it significantly improves the efficiency of solving discrete logarithms, impacting security protocols that rely on this problem.
The paper tackles the discrete logarithm problem in finite fields of fixed characteristic, proving it can be solved in quasi-polynomial expected time, specifically in expected time (pn)^{2 log_2(n) + O(1)} for fields of cardinality p^n.
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)}$.