1
$\begingroup$

Find 2 integers $t < 419^5$ s.t. $t^2 ≡ 5\mod 419^5$

I'm pretty sure this has something to do with Hansel's lemma but I'm only finding examples with multi term polynomials that have been confusing to follow. If someone could point me in the direction of a similar example or explain how it works that would be awesome. Thanks!

$\endgroup$
1
$\begingroup$

To simplify the reasoning, let $p=419, k=5, a=5;\;$ i.e. you want to compute a root $ r^2\equiv a \bmod p^k$. For a solution with $k=2$ see my answer https://math.stackexchange.com/a/1895883/61216 where I compute a solution $\bmod p^2$.

In the table below I show the lifting steps for the root $r_0\equiv\sqrt{a}\equiv 41 \bmod p$

r = r0 = 41
z = (2r0)^(-1) mod p = 46

j=1
   p^j = 419
   x = (a-r^2)/p^j = -4
   x = x*(2r0)^(-1) mod p^j = 235
   r = r + x*p^j = 98506

j=2
   p^j = 175561
   x = (a-r^2)/p^j = -55271
   x = x*(2r0)^(-1) mod p^j  = 90949
   r = r + x*p^j = 15967195895

j=3
   p^j = 73560059
   x = (a-r^2)/p^j = -3465893695780
   x = x*(2r0)^(-1) mod p^j = 19468360
   r = r + x*p^j = 1432109677429135

j=4
   p^j = 30821664721
   x = (a-r^2)/p^j = -66542094554315137820
   x = x*(2r0)^(-1) mod p^j = 8060623011
   r = r + x*p^j = 248443251997096924066

p^k = p^5 = 12914277518099
r mod p^k = 8302875642540

Now check that $8302875642540^2 \equiv 5 \bmod{419^5}.$ Now repeat the corresponding steps for the other root $-41 \equiv 378 \bmod 419$ to get the solution $4611401875559.$

Note that for greater values of $k$ it is faster to compute the lifted solutions $\bmod p^{2^j}\;$ (quadratic Hensel lifting). For another references see also the section Powers of odd primes of John Cook's Solving quadratic congruences and the Wikipedia example section.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.