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?
$\begingroup$
$\endgroup$
8
asked Jan 14, 2011 at 15:28
-
1$\begingroup$ 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$. $\endgroup$– SheikraisinrollbankCommented Jan 14, 2011 at 15:32
-
1$\begingroup$ no need to pile on... $\endgroup$– SheikraisinrollbankCommented Jan 14, 2011 at 15:44
-
$\begingroup$ I changed "quadratic residue" to "square root". $\endgroup$– Craig FeinsteinCommented Jan 14, 2011 at 15:44
-
18$\begingroup$ Cipolla + Hensel's Lemma should do it. $\endgroup$– Franz LemmermeyerCommented Jan 14, 2011 at 15:53
-
5$\begingroup$ 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}}$. $\endgroup$– Joe SilvermanCommented Jan 14, 2011 at 21:20
|
Show 3 more comments
4 Answers
$\begingroup$
$\endgroup$
4
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.
answered Jan 15, 2011 at 11:03
-
$\begingroup$ Excuse me, let's suppose that $\mathrm{gcd}(A,p^{n})=p^{j}$ and $j$ is odd. Then $A$ is not a square modulo $p^{n}$, right? $\endgroup$ Commented Mar 28, 2016 at 9:47
-
$\begingroup$ Right. Suppose $B$ is a square root $\mod p^n$ and $B=p^iC \dots$ $\endgroup$ Commented Mar 28, 2016 at 20:53
-
$\begingroup$ Can you please explain, how do I find a root modulo p^k if
A mod p = 0? You said that in this caseyou have any easy first step...- what does it mean? Does havingA mod p = 0helps in any sense to find root modulo p^k? $\endgroup$– ArtyCommented Jul 16, 2022 at 18:27 -
$\begingroup$ See the comment above. Square B, see what happens $\endgroup$ Commented Jul 18, 2022 at 20:59
$\begingroup$
$\endgroup$
1
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$.
-
1$\begingroup$ Does this formula work always? For example if
a mod p = 0(anda != 0) does it still work? For examplep = 3, k = 4, q = p^k = 3^4 = 81, a = 7, then roots ofamodulop = 3are1, 2. Whilex^r * a^((q - 2 * r + 1) / 2) mod q = 1^27 * 7^((81 - 2 * 27 + 1) / 2) mod q = 3, but3^2 = 9is not equal toa = 7, so3is not a square root ofa = 7modulo81. $\endgroup$– ArtyCommented Jul 16, 2022 at 18:39
$\begingroup$
$\endgroup$
Dickson's History Of Numbers Vol 1 has formulas that find modular square roots for powers of prime modula. See p215 for Tonelli's algorithm and p218 for Cipolla's algorithm. Dickson's work can be found online at
https://ia800209.us.archive.org/12/items/historyoftheoryo01dick/historyoftheoryo01dick.pdf
$\begingroup$
$\endgroup$
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.
-
9$\begingroup$ 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). $\endgroup$ Commented Jan 14, 2011 at 19:27