Fast algorithms for -adic towers over finite fields

DOI10.1145/2465506.2465956MaRDI QIDQ2963230zbMATH OpenOpenAlexFDO

Authors Luca De Feo, Javad Doliskani, Éric Schost

Publication date 10 February 2017

Published in Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.6021

zbMATH Keywords

elliptic curvesalgebraic torifinite fieldsirreducible polynomialsPell's equationextension towers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16)

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

Recommendations

• Fast arithmetics in Artin-Schreier towers over finite fields
• Fast arithmetics in Artin-Schreier towers over finite fields
• Algorithms for finite field arithmetic
• Fast arithmetic for the algebraic closure of finite fields
• Accelerated tower arithmetic

Cited in

(10)

• Standard generators of finite fields and their cyclic subgroups
• Fast arithmetic in unramified \(p\)-adic fields
• Fast arithmetics in Artin-Schreier towers over finite fields
• Fast arithmetics in Artin-Schreier towers over finite fields
• Accelerated tower arithmetic
• Distorting the volcano
• Computing isomorphisms and embeddings of finite fields
• Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field
• Efficient Computation of p-Adic Heights
• Directed evaluation

This page was built for publication: Fast algorithms for \(\ell\)-adic towers over finite fields

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