# Computing square roots modulo prime powers

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.

-
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