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.
Asked
Active
Viewed 51 times
1
-
you mean $\pmod {q^2}$ ? – J. W. Tanner Aug 04 '20 at 03:54
-
@J.W.Tanner yes! Fixing, tnx – Ilya Gazman Aug 04 '20 at 03:55
-
Let $b=kq+a$ and solve for $k$ in $(kq+a)^2\equiv n \pmod {q^2}$ – J. W. Tanner Aug 04 '20 at 04:01
2 Answers
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.
Carl Schildkraut
- 32,931
-
It's not working for me for some reason. For $n=643211,q=7,a=4$, I calculated $k$ to be $45942$ but $(kq+a)^2$ is not equal to $n$ mod $q^2$ – Ilya Gazman Aug 04 '20 at 04:23
-
-
@CarlSchildkraut continuing with my example, I am getting that $n-a^2$ is not divisible by $2aq$ $643211 mod 274 = 35$ – Ilya Gazman Aug 04 '20 at 04:50
-
@IlyaGazman You need to perform the division of $2a$ modulo $q$; so, in your example, $n-a^2=643195$, and $\frac{n-a^2}{q}=91885$, Now, you need to calculate $91885/8$ modulo $7$, which is the same as multiplying by the multiplicative inverse of $8$. This inverse is $1$, so you get $k=91885\equiv 3\bmod 7$. – Carl Schildkraut Aug 04 '20 at 05:40
-
1
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.
tkf
- 11,563