A Complete Generalization of Atkin's Square Root Algorithm

Article type: Research Article

Authors: Rotaru, Armand Stefan | Iftene, Sorin

Affiliations: Institute of Computer Science, Romanian Academy, Carol I no. 8, 700505 Iasi, Romania. [email protected] | Department of Computer Science, Alexandru Ioan Cuza University, General Berthelot no. 16, 700483 Iasi, Romania. [email protected]

Note: [] Address for correspondence: Institute of Computer Science, Romanian Academy, Carol I no. 8, 700505 Iasi, Romania

Abstract: 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 ≡ 2s + 1 mod 2s + 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.

Keywords: Square Roots, Efficient Computation, Complexity

DOI: 10.3233/FI-2013-853

Journal: Fundamenta Informaticae, vol. 125, no. 1, pp. 71-94, 2013