Fast algorithm of square rooting in some finite fields of odd characteristic

DOI10.3103/S0027132218050029MaRDI QIDQ1725540zbMATH OpenOpenAlexFDO

Authors I. B. Gashkov, S. B. Gashkov

Publication date 14 February 2019

Published in Moscow University Mathematics Bulletin (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3103/s0027132218050029

zbMATH Keywords

fast algorithmGalois fieldfinite fields of odd characteristiccomplexity of square root computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Finite fields and commutative rings (number-theoretic aspects) (11T99) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• A High-Speed Square Root Algorithm in Extension Fields
• A note on square roots in finite fields
• Efficient computation of roots in finite fields
• On the computation of square roots in finite fields
• On taking square roots without quadratic nonresidues over finite fields. With an Appendix by Lawrence C. Washington

Cites work

• A note on square roots in finite fields
• An application of the method of additive chains to inversion in finite fields
• Batch Binary Edwards
• Curve41417: Karatsuba revisited
• Explicit Bounds for Primality Testing and Related Problems
• Fast polynomial factorization and modular composition
• Faster integer multiplication
• Faster polynomial multiplication over finite fields
• Linear ternary quasiperfect codes correcting double errors
• On a quick multiplication in normal bases of finite fields
• On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic 2
• On the decoding of some exceptional ternary codes

Cited in

(9)

• A simple and fast probabilistic algorithm for computing square roots modulo a prime number (Corresp.)
• Improved generalized Atkin algorithm for computing square roots in finite fields
• On the computation of square roots in finite fields
• Fast algorithms for solving equations of degree \(\le 4\) in some finite fields
• Efficient \(p\)th root computations in finite fields of characteristic \(p\)
• scientific article; zbMATH DE number 7688194 (Why is no real title available?)
• A High-Speed Square Root Algorithm in Extension Fields
• Another Look at Square Roots (and Other Less Common Operations) in Fields of Even Characteristic
• scientific article; zbMATH DE number 1689040 (Why is no real title available?)

This page was built for publication: Fast algorithm of square rooting in some finite fields of odd characteristic

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