Cipolla's algorithm http://en.wikipedia.org/wiki/Cipolla's_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?

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 TonelliShanks 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 $p1=Q2^S$ with $Q$ odd. Then it is asserted that Cipolla's method is better exactly when $S(S1)>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. 


An explicit formula is given in Tonelli's 1891 note referred to in the Wikipedia entry on the TonelliShanks algorithm: Given a prime $p>2$ and a quadratic residue $a \bmod p$, let $x$ be a square root of $a \bmod p$. Then for any power $q = p^k$ and $r:=q/p$, the square root of $a \bmod q$ is $x^r \cdot a^e$ where $e := (q  2r + 1)/2$. Tonelli's proof is straightforward: Square and apply the FermatEuler congruence with exponent $\varphi(q)=qr$ and the fact that $y \equiv z \bmod p$ implies $y^r \equiv z^r \bmod q$. 


Have you checked www.ma.utexas.edu/users/voloch/Preprints/roots.pdf, by Prof. Voloch and P Barreto? If I am not mistaken, in certain cases, their work improves on Cipolla's. 

