Taking square roots modulo $2^N$ I was trying to solve $y^2 - y \equiv 16 \pmod{512}$ by completing the square.
Here is my solution.
\begin{align}
   y^2 - y &\equiv 16 \pmod{512} \\
   4y^2 - 4y + 1 &\equiv 65 \pmod{512} \\
  (2y-1)^2 &\equiv 65 \pmod{512} \\
   2y - 1 &\equiv \pm 33 \pmod{512} &\text{Found by pointwise search.}\\
   2y &\equiv 34, -32 \pmod{512} \\
   y &\equiv 17, -16 \pmod{256} \\
   y &\in \{17, 273, 240, 496\} \pmod{512} &\text{These values need to be verified.}\\
   y &\in \{240, 273\}\pmod{512}
\end{align}
I had to solve $x^2 \equiv 65 \pmod{2^9}$ by a pointwise search. Is there any systematic method for solving equivalences of the form $x^2 \equiv a \pmod{2^N}$, or more generally $x^2 \equiv a \pmod{p^N}$ for a prime number $p$.

This isn't a general method, but here's a neat trick if $2^k|a-1$ for some large enough $k$.
Claim. If $x^2\equiv a\bmod 2^n$ and $a\equiv 1\bmod 2^k$, with $n\leq 2k$, then
$$x\equiv \pm \frac{a+1}{2}\bmod 2^{n-1}.$$
Proof. As there are only two residue classes $\bmod 2^{n-1}$ that will satisfy this, it suffices to show that these both do. Setting $b=(a+1)/2$ we need to show that
$$b^2\equiv a=2b-1\bmod 2^n.$$
Indeed, this is equivalent to
$$2^n|(b-1)^2 \Leftrightarrow b\equiv 1\bmod 2^{\left\lceil\frac{n}{2}\right\rceil},$$
which is itself equivalent to
$$a\equiv 1\bmod 2^{\left\lceil\frac{n}{2}\right\rceil},$$
which is true as $\left\lceil\frac{n}{2}\right\rceil \leq k$.
So, since we have $x^2\equiv a\bmod 2^9$ and $a\equiv 1\bmod 2^6$, we have that $x\equiv \pm \frac{a+1}{2} = \pm 33\bmod 2^8.$
A similar result holds in general:

If $p$ is an odd prime with $x^2\equiv a\bmod p^n$ and $a\equiv 1\bmod 2^k$ with $n\leq 2k$, then
$$x\equiv \pm \frac{a+1}{2}\bmod p^n.$$

This can be proven in nearly identical fashion.
