Square root algorithm in Fq for q = 2s + 1(mod 2s+1)

Presented is a square root algorithm in Fq which generalises Atkins´s square root algorithm [see reference 6] for q ≡ 5 (mod 8) and Muller´s algorithm [see reference 7] for q ≡ 9 (mod 16). The presented algorithm precomputes a primitive 2s-th root of unity ξ where s is the largest positive integer satisfying 2s|q - 1, and is applicable for the cases when s is small. The proposed algorithm requires one exponentiation for square root computation and is favourably compared with the algorithms of Atkin, Müuller and Kong et al.