cispa_all_3872.pdf (643.25 kB)

Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms

Download (643.25 kB)
journal contribution
posted on 2023-11-29, 18:05 authored by Antoine JouxAntoine Joux, Cécile Pierrot
Elliptic bases, introduced by Couveignes and Lercier in 2009, give an elegant way of representing finite field extensions. A natural question which seems to have been considered independently by several groups is to use this representation as a starting point for discrete logarithm algorithms in small characteristic finite fields. This idea has been recently proposed by two groups working on it, in order to achieve provable quasi-polynomial time for discrete logarithms in small characteristic finite fields. In this paper, we do not try to achieve a provable algorithm but, instead, investigate the practicality of heuristic algorithms based on elliptic bases. Our key idea is to use a different model of the elliptic curve used for the elliptic basis that allows for a relatively simple adaptation of the techniques used with former Frobenius representation algorithms. We have not performed any record computation with this new method but our experiments with the field $\F_{3^{1345}}$ indicate that switching to elliptic representations might be possible with performances comparable to the current best practical methods.


Preferred Citation

Antoine Joux and Cécile Pierrot. Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms. In: Advances in Mathematics of Communications. 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Legacy Posted Date



Advances in Mathematics of Communications

Open Access Type

  • Green

Sub Type

  • Article


@article{cispa_all_3872, title = "Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms", author = "Joux, Antoine and Pierrot, Cécile", journal="{Advances in Mathematics of Communications}", year="2022", }

Usage metrics


    No categories selected


    Ref. manager