Cipolla's algorithm [http://en.wikipedia.org/wiki/Cipolla's\_algorithm](http://en.wikipedia.org/wiki/Cipolla%27s_algorithm) is an efficient algorithm for finding a square root modulo a prime number. Is there an efficient algorithm for finding a square root modulo a prime power?



Is there an efficient algorithm for finding a square root modulo a prime power?
Joe Silverman's comment gives the method. (if the square root of A mod p is 0 you have any easy first step.... let $\gcd(A\ ,p^n)=p^j.$ If $j$ is odd, give up, otherwise let $A=p^{2k}B$ and find the $\mod p \ $ square root of $B$ (if it is a quadratic residue.)


I ascertained this by looking at the modular square root code in Maple (a bit tricky to see the subprocedures..). 


According to Wikipedia the [Tonelli-Shanks Algorithm](http://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm) is more efficient that Cipolla's for odd primes not of the form $64Q+1$: Let $m$ be the number of bits in the binary expansion of $p$ and $p-1=Q2^S$ with $Q$ odd. Then it is asserted that Cipolla's method is better exactly when $S(S-1)>8m+20$. Of course for even primes neither method is needed.


The designers of Maple seem to have determined or decided that trying $2,3,4,\cdots$ is best for primes under $80$ or so. I wasn't able to understand (in the limited time I put into it) which of the the modular square root methods Maple uses for the prime case for larger primes. 


