Haskell modular equations

Question

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

Answer 1

The solution of modular quadratic equations includes the union of:

• Tonelli-Shanks algorithm
• China Conservation Theorem
• and quadratic formula (i.e. completion of the square)

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

Here you can find some examples:

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