A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic

2022/06/13 by Guido Lido, Lido, Guido
Computer Science · #11G25 #11T71 #94A60 #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.2206.10327

openalex publication_date 2022/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We describe a provably quasi-polynomial algorithm to compute discrete logarithms in the multiplicative groups of finite fields of small characteristic, that is finite fields whose characteristic is logarithmic in the order. We partially follow the heuristically quasi-polynomial algorithm presented by Barbulescu, Gaudry, Joux and Thome'. The main difference is to use a presentation of the finite field based on elliptic curves: the abundance of elliptic curves ensures the existence of such a presentation.

Related

• A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
• Discrete logarithms in quasi-polynomial time in finite fields of fixed\n characteristic
• On the relation generation method of Joux for computing discrete logarithms
• Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms
• An L(1/3) algorithm for discrete logarithm computation and principality testing in certain number fields