A Complete Generalization of Atkin's Square Root Algorithm

Atkin's algorithm [2] for computing square roots in $Z^*_p$ , where p is a prime such that p ≡ 5 mod 8, has been extended by Müller [15] for the case p ≡ 9 mod 16. In this paper we extend Atkin's algorithm to the general case p ≡ 2^s + 1 mod 2^s + 1, for any s ≥ 2, thus providing a complete solution for the case p ≡ 1 mod 4. Complexity analysis and comparisons with other methods are also provided.