Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to implement an algorithm that can compute the square root of a quadratic residue mod a prime power. For integers $a$ such that

  1. $p\not\mid a$
  2. $p\neq 2$

it's relatively straightforward using Hensel's Lemma to lift the roots from $\mathbb{Z}/p\mathbb{Z}$ to $\mathbb{Z}/p^k\mathbb{Z}$. However, in the cases where either (or both) of the two conditions fail, I'm not certain what to do. I think the more general version of Hensel's lemma may be applicable, but I'm not sure how to use it. Wikipedia mentions "an algorithm of Gauss", but doesn't provide any links or details.

share|improve this question
Maybe this will help? mathforum.org/library/drmath/view/70474.html . Additionally, see: Cipolla's Algothim. Also see: Tonnelli-Shanks Algorithm. –  Amzoti Dec 16 '12 at 4:26
Ok, the last post on the mathforum page describes the procedure for $p=2$, so that should work fine. On the other link you gave me, the accepted answer says, "if $j$ is odd, give up". I assume that means there are no roots? –  Nick Dec 16 '12 at 4:47
Do you have access to the book A Course in Number Theory and Cryptography by Neil Koblitz? Look at p. 48, Square roots modulo $p$. –  Amzoti Dec 16 '12 at 4:54
That section doesn't mention anything about prime powers though. –  Nick Dec 16 '12 at 5:10
Nick, sorry for the bogus reference: Does this help see section called Square roots mod p prime –  Amzoti Dec 16 '12 at 5:18
show 2 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.