most recent 30 from http://mathoverflow.net 2013-06-18T07:33:16Z http://mathoverflow.net/feeds/question/52081 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52081/is-there-an-efficient-algorithm-for-finding-a-square-root-modulo-a-prime-power Craig Feinstein 2011-01-14T15:28:45Z 2011-01-29T11:22:13Z

<p>Cipolla's algorithm <a href="http://en.wikipedia.org/wiki/Cipolla%27s_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Cipolla's_algorithm</a> 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?</p>

http://mathoverflow.net/questions/52081/is-there-an-efficient-algorithm-for-finding-a-square-root-modulo-a-prime-power/52094#52094 RPC 2011-01-14T17:27:06Z 2011-01-14T17:27:06Z

<p>Have you checked <a href="http://www.ma.utexas.edu/users/voloch/Preprints/roots.pdf" rel="nofollow">www.ma.utexas.edu/users/voloch/Preprints/roots.pdf</a>, by Prof. Voloch and P Barreto? If I am not mistaken, in certain cases, their work improves on Cipolla's. </p>

http://mathoverflow.net/questions/52081/is-there-an-efficient-algorithm-for-finding-a-square-root-modulo-a-prime-power/52159#52159 Aaron Meyerowitz 2011-01-15T11:03:55Z 2011-01-15T11:03:55Z

<p>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.)</p> <p>I ascertained this by looking at the modular square root code in Maple (a bit tricky to see the subprocedures..). </p> <p>According to Wikipedia the <a href="http://en.wikipedia.org/wiki/Tonelli%25E2%2580%2593Shanks_algorithm" rel="nofollow">Tonnelli-Shanks Algorithm</a> 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.</p> <p>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. </p>