Paper 2013/087

Square Root Algorithm in F_q for q=2^s+1 (mod 2^(s+1))

Namhun Koo, Gook Hwa Cho, and Soonhak Kwon

Abstract

We present a square root algorithm in F_q which generalizes Atkins's square root algorithm for q=5(mod 8) and Kong et al.'s algorithm for q=9(mod 16) Our algorithm precomputes a primitive 2^s-th root of unity where s is the largest positive integer satisfying 2^s| q-1, and is applicable for the cases when s is small. The proposed algorithm requires one exponentiation for square root computation and is favorably compared with the algorithms of Atkin, Muller and Kong et al.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. Unknown where it was published
Keywords
square root algorithmfinite fieldTonelli-Shanks algorithmCipolla-Lehmer algorithm
Contact author(s)
shkwon7 @ gmail com
History
2013-02-20: received
Short URL
https://ia.cr/2013/087
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/087,
      author = {Namhun Koo and Gook Hwa Cho and Soonhak Kwon},
      title = {Square Root Algorithm in F_q  for q=2^s+1 (mod 2^(s+1))},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/087},
      year = {2013},
      url = {https://eprint.iacr.org/2013/087}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.