# Quadratic residue modulo with prime p exponent of two

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!

• 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 – Etoplay Aug 17 '16 at 10:43
• @Etoplay I dont get your point. – BeGood Aug 17 '16 at 11:05
• There are infinite many solutions. Just take a prime p with $p = 1 \mod 4$, a $m$ with $m<p$ and $c=m^2$ – Etoplay Aug 17 '16 at 11:35
• @Etoplay I can't do it with brute force because my p length is 2048 bits – 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.

• I'm so sorry I made a mistake. m < $p^2$ – BeGood Aug 17 '16 at 12:23