Modular equations in Haskell

Question

I want to solve linear and quadratic modular equations in Haskell in one variable. The way I am doing it right now is by putting x = [1..] in the equation one by one and finding the remainder (expr `rem` p == 0, if the equation is modulo p (not necessarily a prime) where expr has the variable x). I believe this is a very inefficient process. So is there any better way to do it?

Answer 1

Solving modular quadratic equations involves combining:

• the Tonelli-Shanks algorithm
• the Chinese Remainder Theorem
• and the quadratic formula (i.e. completing the square)

For Haskell the arithmoi package has implementations of these algorithms. In particular, see the chineseRemainder, sqrtModP and sqrtModPP functions.

Here you can find some worked examples:

http://www.mersennewiki.org/index.php/Modular_Square_Root