Welcome to MathOverflow

Question

1

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?

edited Jan 15 2011 at 9:39

Aaron Meyerowitz
11.5k●1●10●31

asked Jan 14 2011 at 15:28

Craig Feinstein
715●2●14

1

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 2011 at 15:32

1

no need to pile on... – Sheikraisinrollbank Jan 14 2011 at 15:44

I changed "quadratic residue" to "square root". – Craig Feinstein Jan 14 2011 at 15:44

7

Cipolla + Hensel's Lemma should do it. – Franz Lemmermeyer Jan 14 2011 at 15:53

2

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 2011 at 21:20

show 2 more comments

Aaron Meyerowitz · Accepted Answer · 2011-01-15 11:03:55Z UTC

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

RPC · Answer 2 · 2011-01-14 17:27:06Z UTC

-1

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.

answered Jan 14 2011 at 17:27

RPC
253●1●1●5

1

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 2011 at 19:27

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.