Fast algorithms for ℓ-adic towers over finite fields

research paper presented at ISSAC 2013

View slides Preprint Source .zip Source .tar.gz View on GitHub

Authors: Luca De Feo, Javad Doliskani and Éric Schost

Inspired by previous work of Shoup, Lenstra-De Smit and Couveignes-Lercier, we give fast algorithms to compute in (the first levels of) the ℓ-adic closure of a finite field. In many cases, our algorithms have quasi-linear complexity.

Notice: this is the authors' version of a work that will be presented at the International Symposium on Symbolic and Algebraic Computation 2013 in Boston. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version will be subsequently published.

The GitHub sources contain the LaTeX source code as well as the Sage scripts demonstrating the concepts involved.