Square root algorithm in 𝔽 q for q ≡ 2 s + 1 (mod 2 s +1 )

Presented is a square root algorithm in q which generalises Atkins's square root algorithm [see reference 6] for q ≡ 5 (mod 8) and Müller's algorithm [see reference 7] for q ≡ 9 (mod 16). The presented 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 favourably compared with the algorithms of Atkin, Müuller and Kong et al.