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