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

Namhun Koo; Gook Hwa Cho; Soonhak Kwon

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 algorithm finite field Tonelli-Shanks algorithm Cipolla-Lehmer algorithm
Contact author(s): shkwon7 @ gmail com
History: 2013-02-20: received
Short URL: https://ia.cr/2013/087
License: 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}
}