Is there an efficient algorithm for finding a square root modulo a prime power? - MathOverflow 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 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 Answer by RPC for Is there an efficient algorithm for finding a square root modulo a prime power? 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 Answer by Aaron Meyerowitz for Is there an efficient algorithm for finding a square root modulo a prime power? 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>