17
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 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$ Commented Jan 14, 2011 at 15:32
  • $\begingroup$ I changed "quadratic residue" to "square root". $\endgroup$ Commented Jan 14, 2011 at 15:44
  • 18
    $\begingroup$ Cipolla + Hensel's Lemma should do it. $\endgroup$ Commented Jan 14, 2011 at 15:53
  • $\begingroup$ If you are lucky, and your prime power $q$ satisfies $\phi(q)=2$ modulo $4$, then for any quadratic residue $n$ modulo $q$ that is prime to $q$ you can calculate a square root as follows: $\sqrt{n}=n^{(\phi(q)+2)/4$, where $\phi$ is the Euler phi function. $\endgroup$ Commented Jan 14, 2011 at 16:46
  • 6
    $\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$ Commented Jan 14, 2011 at 21:20

4 Answers 4

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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 case you have any easy first step... - what does it mean? Does having A mod p = 0 helps in any sense to find root modulo p^k? $\endgroup$ Commented Jul 16, 2022 at 18:27
  • $\begingroup$ See the comment above. Square B, see what happens $\endgroup$ Commented Jul 18, 2022 at 20:59
10
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Does this formula work always? For example if a mod p = 0 (and a != 0) does it still work? For example p = 3, k = 4, q = p^k = 3^4 = 81, a = 7, then roots of a modulo p = 3 are 1, 2. While x^r * a^((q - 2 * r + 1) / 2) mod q = 1^27 * 7^((81 - 2 * 27 + 1) / 2) mod q = 3, but 3^2 = 9 is not equal to a = 7, so 3 is not a square root of a = 7 modulo 81. $\endgroup$ Commented Jul 16, 2022 at 18:39
1
$\begingroup$

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

Improve this answer
$\endgroup$
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.