International Association
for Cryptologic Research

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.