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?

Renny

This might help – Dittman

@BartekBanachewicz I am looking for a general method. Actually in the expression there are other constants as well which are determined using other means so I cannot manually solve it and then use those results. – Renny

is this a numerical method/algrotihm? if yes, you might want to add the respective tag. – Laveen

@ErikAllik Actually, I am not necessarily looking for the algorithm. Even if there is a package that does this, I am fine with it. It's just a subroutine in the implementation of Rademacher formula. Thanks for the edits btw! – Renny

To solve ax+b = c (mod n) you need x = (c-b)*a^-1 (mod n) where a^-1 is the modular inverse of a mod n. This will exist if and only if a and n are relatively prime, in which case the extended Euclidean algorithm can compute it: en.wikipedia.org/wiki/… – Nine

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

Allergen

Be very careful with the arithmoi package. It has at least one bug in its prime sieve code that causes intermittent segmentation faults. The code is extremely hairy and poorly documented, and despite the package having a new maintainer there are no signs that it will improve any time soon. – Azurite