Fast Arithmetics in Artin-Schreier Towers over Finite Fields

Abstract

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.

28 pages, 4 figures, 3 tables, uses mathdots.sty, yjsco.sty Submitted to J. Symb. Comput

References in corpus (1)

• Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic

Cited by in corpus (4)

• Fast algorithms for ell-adic towers over finite fields
• Explicit isogenies in quadratic time in any characteristic
• Change of basis for m-primary ideals in one and two variables
• Standard Lattices of Compatibly Embedded Finite Fields