Is there an efficient algorithm for finding a square root modulo a prime power? 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?
 A: 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 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. 
A: An explicit formula is given in Tonelli's 1891 note referred to in the Wikipedia entry on the Tonelli-Shanks 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 Fermat-Euler congruence with exponent $\varphi(q)=q-r$ and the fact that $y \equiv z \bmod p$ implies $y^r \equiv z^r \bmod q$.
A: Dickson's History Of Numbers Vol 1 has formulas that find modular square roots for powers of prime modula.  See p215 for Tonelli's algorithm and p218 for Cipolla's algorithm.  Dickson's work can be found online at
https://ia800209.us.archive.org/12/items/historyoftheoryo01dick/historyoftheoryo01dick.pdf
A: 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. 
