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

Can you solve it in $p$-adics?
For any $2$-adic integer $n$ we have the familiar Taylor/binomial-power series for $\sqrt{1+8n}$:
$\sqrt{1+8n}=1+(1/2)(8n)-...$
All omitted terms vanish $\bmod 512$ when $n$ is a multiple of $8$, thus with $n=8$
$\sqrt{65}\equiv 1+(1/2)(8×8) \bmod 512$
$\sqrt{65}\equiv 1+32\equiv 33 \bmod 512$
So one square root (the root closer to $1$ in $2$-adics) is $33 \bmod 512$.
For reference here are more terms in the binomial expansion used above:
$\sqrt{1+8n}=1+(2^2)n-(2^3)n^2+(2^5)n^3-(5×2^5)n^4+(7×2^7)n^5-(21×2^8)n^6+(33×2^{10})n^7-(429×2^9)n^8+...$
This is sufficiently many terms to obtain at least eleven bits in the square root ($\bmod 2048$) for any integer $n$ (not just multiples of $8$ as above); the exponent on $2$ is at least $11$ in all subsequent terms.  The exponent on $2$ is always at least the number of terms rendered (e.g. $2^9$ in the ninth term), thus guaranteeing convergence in $2$-adics.  Note also that for a conventional integer square the obtained square root is one greater than a multiple of $4$, which in conventional algebra could be the negative root (e.g. $\sqrt{9}=-3$).
