An analysis of Shanks’s algorithm for computing square roots in finite fields
Scott Charles Lindhurst · CRM proceedings & lecture notes · 1999
Abstract We rigorously analyze Shanks's algorithm for computing square roots modulo a prime number. The initialization always requires two exponentiations. Averaged over all primes and possible inputs, the body of the algorithm requires 8/3 additional multiplications. We obtain exact values for the mean and variance of the number of additional multiplications for a fixed prime, and finally show that the distribution is asymptotically normal.