Saturday 17 January 2015

number theory - How to find modulus square root?


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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...