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

Publication date: 13 June 2022

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.

Has companion code repository: https://github.com/guidoshore/log_small_example

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Cryptography (94A60) Varieties over finite and local fields (11G25)

This page was built for publication: A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402717)