Is there an efficient algorithm for finding a square root modulo a prime power?

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$.

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.