7

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?

Iguana
  • 247
  • 1
  • 8
  • [This might help](http://math.stackexchange.com/a/261900/88047) – Bartek Banachewicz Oct 26 '15 at 10:06
  • @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. – Iguana Oct 26 '15 at 10:11
  • is this a numerical method/algrotihm? if yes, you might want to add the respective tag. – Erik Kaplun Oct 26 '15 at 10:18
  • @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! – Iguana Oct 26 '15 at 10:24
  • 5
    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: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Computing_multiplicative_inverses_in_modular_structures – John Coleman Oct 26 '15 at 11:18

1 Answers1

5

Solving modular quadratic equations involves combining:

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

ErikR
  • 51,541
  • 9
  • 73
  • 124
  • 2
    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. – dfeuer Oct 26 '15 at 14:57