Taking roots over high extensions of finite fields

DOI10.1090/S0025-5718-2013-02715-9MaRDI QIDQ2862538zbMATH OpenOpenAlexFDO

Authors Javad Doliskani, Éric Schost

Publication date 15 November 2013

Published in Mathematics of Computation (Search for Journal in Brave)

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

zbMATH Keywords

finite field arithmeticroot extractionsquare roots

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Finite fields (field-theoretic aspects) (12E20) Symbolic computation and algebraic computation (68W30)

Abstract: We present a new algorithm for computing $m$-th roots over the finite field $F_q$, where $q=p^n$, with $p$ a prime, and $m$ any positive integer. In the particular case $m=2$, the cost of the new algorithm is an expected $O(M(n)log(p)+CC(n)log(n))$ operations in $F_p$, where $M(n)$ and $CC(n)$ are bounds for the cost of polynomial multiplication and modular polynomial composition. Known results give $M(n)=O(nlog(n)loglog(n))$ and $CC(n)=O(n^{1.67})$, so our algorithm is subquadratic in $n$.

Recommendations

• Taking pth roots modulo polynomials over finite fields
• Roots of certain polynomials over finite fields
• Roots and coefficients of polynomials over finite fields
• Roots and coefficients of multivariate polynomials over finite fields
• Root systems in number fields
• scientific article; zbMATH DE number 4152521
• Roots of polynomials in p-adic fields
• On finding primitive roots in finite fields
• A note on square roots in finite fields
• Roots of sparse polynomials over a finite field

Cites work

• A fast algorithm for computing multiplicative inverses in \(\text{GF}(2^ m)\) using normal bases
• A Refinement of H. C. Williams' qth Root Algorithm
• An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
• Computing Frobenius maps and factoring polynomials
• Efficient computation of roots in finite fields
• Fast Algorithms for Manipulating Formal Power Series
• Fast construction of irreducible polynomials over finite fields
• Fast multiplication of large numbers
• Fast polynomial factorization and modular composition
• Fast rectangular matrix multiplication and applications
• Genus 2 point counting over prime fields
• scientific article; zbMATH DE number 2086246 (Why is no real title available?)
• scientific article; zbMATH DE number 1253982 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 1942431 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• scientific article; zbMATH DE number 5485560 (Why is no real title available?)
• Improved Computation of Square Roots in Specific Finite Fields
• Improved generalized Atkin algorithm for computing square roots in finite fields
• Matrix multiplication via arithmetic progressions
• On fast multiplication of polynomials over arbitrary algebras
• On the computation of square roots in finite fields
• Taking cube roots in \(\mathbb Z_{m}\)

Cited in

(23)

• Efficient \(p\)th root computations in finite fields of characteristic \(p\)
• Taking pth roots modulo polynomials over finite fields
• An efficient algorithm for deciding quadratic residuosity in finite fields \(GF(p^ m)\)
• Computing in degree \(2^k\)-extensions of finite fields of odd characteristic
• Efficient computation of roots in finite fields
• On the Cipolla-Lehmer type algorithms in finite fields
• Fast algorithms for solving equations of degree \(\le 4\) in some finite fields
• Randomized root finding over finite FFT-fields using tangent Graeffe transforms
• On taking square roots without quadratic nonresidues over finite fields. With an Appendix by Lawrence C. Washington
• Order dividing extension fields and the root computation problem
• Extension of computing primitive roots of a finite field \(\mathbb F_{p^2}\)
• Subgroup Refinement Algorithms for Root Finding in GF(q)
• Computing isomorphisms and embeddings of finite fields
• Effective black-box constructive recognition of classical groups.
• A geometric approach to root finding in GT(q/sup m/)
• Adleman-Manders-Miller root extraction method revisited
• Trace expression of \(r\)-th root over finite field
• A generalized successive resultants algorithm
• A High-Speed Square Root Algorithm in Extension Fields
• Multiradical isogenies
• On the computation of r-th roots in finite fields
• Modular composition via factorization
• Using Tschirnhaus transformations to find roots in quintic polynomials over \(\mathbb{F}_{2^{m}}\)

Describes a project that uses

Uses Software

• NTL

This page was built for publication: Taking roots over high extensions of finite fields

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