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


*

*$p\not\mid a$

*$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.
 A: Suppose we know the solutions modulo $p^k$ and we want to lift these to $p^{k+1}$. To that end, let $x$ be a solution mod $p^k$:
$$x^2=a\bmod p^k \tag 1$$
which means $x^2$ can be written as
$$x^2 = a + c_k p^k \tag2$$
with some integer $c_k$. The solutions mod $p^{k+1}$ can be expressed as
$$x+\beta p^k\tag 3$$
where $\beta$ is only determined modulo $p$.  Therefore it's enough to determine $\beta$ to know the solutions mod $p^{k+1}$.  Squaring (3) and using representation like (2), there must be an integer $c_{k+1}$ such that
$$(x+\beta p^k)^2 = a + c_{k+1}p^{k+1}\tag4$$
Squaring out, using (2) and then dividing by $p^k$ yields
$$c_k +2\beta x + \beta^2p^k = c_{k+1}p \tag 5$$
Taking this mod $p$ yields that $\beta \bmod p$ is
$$ \beta \in\begin{cases}
\Bbb Z/2\Bbb Z,   & \text{ if } p=2 \text{ and } c_k \text{ is even} \\
\emptyset, & \text{ if } p=2 \text{ and } c_k \text{ is odd} \\
\left\{-\dfrac{c_k}{2x}\right\},  & \text{ if } p\neq2 \text{ and } p \nmid x \\
\Bbb Z/p\Bbb Z,  & \text{ if } p\neq2 \text{ and } p \mid x \text{ and }  p \mid c_k\\
\emptyset,      & \text{ if } p\neq2 \text{ and } p \mid x \text{ and }   p \nmid c_k\\\end{cases} \tag 6$$
where the division in the 3rd case is in $\Bbb Z/p\Bbb Z$. Then plug these $\beta$'s in (3) to find the new $x$'s.
