Improved generalized Atkin algorithm for computing square roots in finite fields

摘要

Recently, S. Mueller developed a generalized Atkin algorithm for computing square roots, which requires two exponentiations in finite fields GF(q) when q≡ 9 (mod 16). In this paper, we present a simple improvement to it and the improved algorithm requires only one exponentiation for half of squares in finite fields GF(q) when q ≡ 9 (mod 16). Furthermore, in finite fields GF(p~m), where p ≡ 9 (mod 16) and m is odd, we reduce the complexity of the algorithm from O(m~3 log~3 p) to O(m~2log~2p(log m+log p)) using the Frobenius map and normal basis representation.