I have a situation: They give me a c and a p with conditions below:

  • c ≡ $m^2$ mod $p^2$
  • p is a prime and p ≡ 1 mod 4
  • 1 < m < $p^2$

Find m.
I tried use extended Euclidean algorithm to find it but I couldn't found anything for this situation. Please help me!

  • $\begingroup$ You can use nearly arbitrary values for that for example: c=4, m=2, p=5 or c=9, m=3, p=5 or c=16, m=4, p=13 $\endgroup$ – Etoplay Aug 17 '16 at 10:43
  • $\begingroup$ @Etoplay I dont get your point. $\endgroup$ – BeGood Aug 17 '16 at 11:05
  • $\begingroup$ There are infinite many solutions. Just take a prime p with $p = 1 \mod 4$, a $m$ with $m<p$ and $c=m^2$ $\endgroup$ – Etoplay Aug 17 '16 at 11:35
  • $\begingroup$ @Etoplay I can't do it with brute force because my p length is 2048 bits $\endgroup$ – BeGood Aug 17 '16 at 11:58

(For the original version, where $m \lt p$ was imposed, then $m^2 < p^2$ thus for $c$ to be congruent to $m^2$ modulo $p^2$ they need to be equal as integers.

Thus, you compute the square-root of $c$ as an integer and are done.)

Now, for the general problem of finding roots modulo primes and powers of primes, "Tonelli-Shanks" and "Cippola" are standard algorithms for the prime case. Then "lift" using "Hensel."

See "Is there an efficient algorithm for finding a square root modulo a prime power?" on MathOverflow for further details.

  • $\begingroup$ I'm so sorry I made a mistake. m < $p^2$ $\endgroup$ – BeGood Aug 17 '16 at 12:23
  • $\begingroup$ I added a little more info to my answer. $\endgroup$ – quid Aug 17 '16 at 12:27

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.