Given integers m, c and n. Find m such that m^2 \equiv c \pmod n
I used Tonelli-Shanks algorithm to caculate the square root, but in my case n is not a prime number, n = p^2,\ p is a prime number.
I read this page. It is said that:
In this article we will consider the case when the modulus is prime.
Otherwise we can compute the square roots modulo the prime factors of
p and then generate a solution using the Chinese Remainder Theorem.
Using Tonelli-Shanks algorithm again, I found m_p such that m_p^2 \equiv {c} \ (\mod p).
I'm stuck with finding m from m_p. That page above does not tell me clearly about how to solve that case. Please help me !
No comments:
Post a Comment