If I know the solution for $\;x^2 \equiv n \mod p\;$ (where $p$ is prime and a quadratic residue of $n$), how can I find the solution of $\;x^2 \equiv n \mod p^2$, in an algorithmic way?
Asked
Active
Viewed 1,096 times
1 Answers
3
As you've mentioned using the Hensel's Lifting Lemma is the way to go here.
First define $f(x) = x^2 - n$ for some fixed $n$. As we have a zero for $f$ modulo $p$, let it be $x_1$. Now let $x_2 = x_1 + pt$. By Hensel's Lemma we have:
$$f(x_2) = f(x_1) + ptf'(x_1) \pmod {p^2}$$
Now equate the last equation to 0 and solve it.
Here's an example. Let $p=7, n = 2$, then can have $x_1=3$ and $f(x) = x^2 - 2$. Now we have:
$$f(x_1) + ptf'(x_1) \equiv 0 \pmod{p^2}$$
$$\frac{f(x_1)}{p} + tf'(x_1) \equiv 0 \pmod p$$
$$\frac 77 + 6t \equiv 0 \pmod p$$
$$6t \equiv 6 \pmod p \implies t \equiv 1 \pmod p$$
Therefore we can take $t=1$ and we have $x_2 = x_1 + pt = 3 + 1 \cdot 7 = 10$. And indeed $7^2 \mid 10^2 - 2 = 98$
Stefan4024
- 35,843