Vtyjkyuk

I was trying to solve $y^2 - y equiv 16 pmod512$ by completing the square.
Here is my solution.

beginalign
y^2 - y &equiv 16 pmod512 \
4y^2 - 4y + 1 &equiv 65 pmod512 \
(2y-1)^2 &equiv 65 pmod512 \
2y - 1 &equiv pm 33 pmod512 &textFound by pointwise search.\
2y &equiv 34, -32 pmod512 \
y &equiv 17, -16 pmod256 \
y &in 17, 273, 240, 496 pmod512 &textThese values need to be verified.\
y &in 240, 273pmod512
endalign

I had to solve $x^2 equiv 65 pmod2^9$ by a pointwise search. Is there any systematic method for solving equivalences of the form $x^2 equiv a pmod2^N$, or more generally $x^2 equiv a pmodp^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 $sqrt1+8n$:

$sqrt1+8n=1+(1/2)(8n)-...$

All omitted terms vanish $bmod 512$ When $n$ is a multiple of $8$, thus with $n=8$

$sqrt65equiv 1+(1/2)(8×8) bmod 512$

$sqrt65equiv 1+32equiv 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:

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

Thus 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. $sqrt9=-3$).

A basic refinement would be to use the fact that if $x^2equiv y pmodp^N$, then for every $N'<N$ we also have $x^2equiv ypmodp^N'$. You might as well assume $y$ is coprime to $p$, since otherwise you can easily pull out its factors of $p$.

You can then proceed as follows: Find every solution $x$ to this mod $p$. Then, each of these solutions could lift to $p$ things mod $p^2$ - so you can find the solutions mod $p^2$ checking those. Then you can lift again to $p^3$ and so on - and, since there will be at most four* square roots mod $p^N$ (and only two if $p$ is odd). Thus, you'll only have to check about $4pN$ values for this method to work - a lot better than checking $p^N$ values - but wait, we can do even better!

Note that the actual lifting step can be further simplified: If we know that $x^2equiv ypmodp^N$, then we can try looking for some $z=x+p^Nc$ such that $z^2equiv ypmodp^N+1$. Working this out gives $x^2+2p^Ncequiv ypmodp^N+1$, which is easy to solve for $c$ (or, if $p=2$, we find that $c$ doesn't even matter - half of our previous square roots lift to two new square roots, and the other half don't lift at all!). Doing this, once you figure out the square root mod $p$, it's basically clean sailing from there.

As for actually solving $x^2equiv ypmodp$, there are some ways - for instance, if $p=4k+3$, you can find one using Fermat's little theorem, but it seems you're interesting in small primes (e.g. $2$) where it's not hard to check every possible $x$.

(*I also should explicitly point out that, for $kgeq 3$, there are four solutions to $x^2=1pmod2^k$ - and consequently, any number with a square root actually has four square roots - the ones you missed for $65$ mod $512$ were $pm 223$, which can be found by adding $256$ to your existing roots, since adding $256$ doesn't change the square mod $512$.)

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^2equiv abmod 2^n$ and $aequiv 1bmod 2^k$, with $nleq 2k$, then

$$xequiv pm fraca+12bmod 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^2equiv a=2b-1bmod 2^n.$$

Indeed, this is equivalent to

$$2^n|(b-1)^2 Leftrightarrow bequiv 1bmod 2^leftlceilfracn2rightrceil,$$

which is itself equivalent to

$$aequiv 1bmod 2^leftlceilfracn2rightrceil,$$

which is true as $leftlceilfracn2rightrceil leq k$.

So, since we have $x^2equiv abmod 2^9$ and $aequiv 1bmod 2^6$, we have that $xequiv pm fraca+12 = pm 33bmod 2^8.$

A similar result holds in general:

If $p$ is an odd prime with $x^2equiv abmod p^n$ and $aequiv 1bmod 2^k$ with $nleq 2k$, then

$$xequiv pm fraca+12bmod p^n.$$

This can be proven in nearly identical fashion.