Fast Arithmetics in Artin-Schreier Towers over Finite Fields

Luca de Feo (1, 2, 3) , Éric Schost (4)

1 GRACE - Geometry, arithmetic, algorithms, codes and encryption
2 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
3 TANC - Algorithmic number theory for cryptology
4 Department of Computer Science

An Artin-Schreier tower over the finite field F_p is a tower of field extensions generated by polynomials of the form X^p - X - a. Following Cantor and Couveignes, we give algorithms with quasi-linear time complexity for arithmetic operations in such towers. As an application, we present an implementation of Couveignes' algorithm for computing isogenies between elliptic curves using the p-torsion.

Mots clés: Algorithms; Complexity; Artin-Schreier

Domaines: Calcul formel [cs.SC]; Logiciel mathématique [cs.MS]

Luca de Feo, Éric Schost. Fast Arithmetics in Artin-Schreier Towers over Finite Fields. Journal of Symbolic Computation, 2012, 47 (7), pp.771-792. ⟨10.1016/j.jsc.2011.12.008⟩. ⟨hal-00505799⟩