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 equivalent to 5 mod 8, has been extended by Muller [15] for the case p equivalent to 9 mod 16. In this paper we extend Atkin's algorithm to the general case p equivalent to 2(s) + 1 mod 2(s+1), for any s >= 2, thus providing a complete solution for the case p equivalent to 1 mod 4. Complexity analysis and comparisons with other methods are also provided.
square roots complexity efficient computation