Improved generalized Atkin algorithm for computing square roots in finite fields

DOI10.1016/j.ipl.2005.11.015zbMath1195.11166OpenAlexW2016653549MaRDI QIDQ844143

Daxing Li, Zhun Cai, Fanyu Kong, Jia Yu

Publication date: 18 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.11.015

zbMATH Keywords

computational complexitycryptographysquare rootsfinite field arithmetic

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Finite fields and commutative rings (number-theoretic aspects) (11T99)

Related Items (6)

On the Cipolla-Lehmer type algorithms in finite fields ⋮ Time-varying square roots finding via Zhang dynamics versus gradient dynamics and the former's link and new explanation to Newton-Raphson iteration ⋮ Computing square roots faster than the Tonelli-Shanks/Bernstein algorithm ⋮ Unnamed Item ⋮ Taking roots over high extensions of finite fields ⋮ New cube root algorithm based on the third order linear recurrence relations in finite fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast algorithm for computing multiplicative inverses in \(\text{GF}(2^ m)\) using normal bases
• On the computation of square roots in finite fields
• Counting points on elliptic curves over finite fields
• A Survey of Fast Exponentiation Methods
• Computing special powers in finite fields
• A note on square roots in finite fields

This page was built for publication: Improved generalized Atkin algorithm for computing square roots in finite fields