Fast algorithms for -adic towers over finite fields

DOI10.1145/2465506.2465956zbMATH Open1360.11142arXiv1301.6021OpenAlexW2160227782MaRDI QIDQ2963230FDOQ2963230

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)

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.

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

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

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)

Cited In (10)

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