Solving the quadratic congruence x2 ≡ a (mod m)

This works for m with up to say 20 digits, due to the limitations of the program used to factor m.
Using the Chinese remainder theorem, the problem is reduced to the case of a prime power pn:
See MP313 lectures notes.
Enter a:
Enter m (≥ 2):

Last modified 25th February 2012
Return to main page