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

*Namhun Koo and 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.

**Category / Keywords: **applications / square root algorithm, finite field, Tonelli-Shanks algorithm, Cipolla-Lehmer algorithm

**Date: **received 20 Feb 2013

**Contact author: **shkwon7 at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20130220:102101 (All versions of this report)

**Short URL: **ia.cr/2013/087

[ Cryptology ePrint archive ]