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}...