The efficient computation of square roots in finite fields is a matter of considerable importance in cryptography, especially in methods relying on elliptic curves. This paper presents an improved Atkin method, and an improved Cipolla-Lehmer method, for performing such computations. It contains both theoretical proofs, and computational examples comparing the running time using these methods with the running time using the Tonelli-Shanks method.
