# 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?

-
Your link doesn't seem releveant; Cipolla's algorithm does have its own web page (maybe you meant to link to it?) You mean square root, I assume? "Finding a quadratic residue" makes it sound like you want something which is a square modulo $q$. – Sheikraisinrollbank Jan 14 '11 at 15:32
no need to pile on... – Sheikraisinrollbank Jan 14 '11 at 15:44
I changed "quadratic residue" to "square root". – Craig Feinstein Jan 14 '11 at 15:44
Cipolla + Hensel's Lemma should do it. – Franz Lemmermeyer Jan 14 '11 at 15:53
Once you find a square root of $A$ modulo $p$, Newton-Rapheson iteration applied to the polynomial $x^2 - A$ will double the number of $p$-adic digits of accuracy. (This is for $p\ge 3$. For $p=2$ you probably need to start with a square root modulo 8, and the convergence is slower.) The iteration is $x \to (x/2)+(A/2x)$. In other words, if $a^2 \equiv A \pmod{p^n}$ and you set $b=(a/2)+(A/2a)$, then $b^2\equiv A \pmod{p^{2n}}$. – Joe Silverman Jan 14 '11 at 21:20

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.

-

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

-

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.

-
The algorithm on that paper is not an algorithm for taking roots modulo prime powers, it's an algorithm for taking roots on finite fields whose order is a large power of a prime (which are different beasts). – Felipe Voloch Jan 14 '11 at 19:27