Given $a^2 \equiv n\pmod q$ find $b$ such that $b^2 \equiv n\pmod {q^2}$

Question

Given $a^2 \equiv n\pmod q$ find $b$ such that $b^2 \equiv n\pmod {q^2}$

$a,n,q$ are given. How to find $b$?

I know I am supposed to use Hensel's lemma and "lifting" $q$, I just don't know how to do it.

Answer 1

You're looking for something of the form $b=a+kq\bmod q^2$. You want $$(a+kq)^2\equiv n\pmod{q^2}\Leftrightarrow a^2+2akq\equiv n\pmod{q^2}.$$ So, you're going to want to choose $k$ so that $$k\equiv \frac{n-a^2}{2aq}\bmod q.$$ You may notice that we're given that $q|n-a^2$, but there's not necessarily an extra factor of $2$ or a factor of $a$. For $a$, Hensel's lemma will fail for $b\equiv 0\bmod q$ if it's not a multiple of $q^2$, and for $2$, Hensel's lemma in fact fails for this polynomial when $q=2$, so dividing by $2$ modulo $q$ is not an issue.

Answer 2

You know that $a^2\equiv n+sq \mod q^2$, for some integer $s$.

Thus for any integer $r$ we have $$(a+rq)^2\equiv n+sq+2arq \mod q^2.$$

To find $r$ such that $(a+rq)^2 \equiv n \mod q^2$ you must solve $2ar\equiv-s \mod q$.

This will have a solution precisely if $\gcd(2a,q)|s$. In particular if $q$ is a prime not equal to $2$ and $q\not\!|a$ this will have a solution.