module Math.NumberTheory.Moduli.Chinese
( chineseRemainder
, chineseRemainder2
) where
import Control.Monad (foldM)
import GHC.Integer.GMP.Internals
import Math.NumberTheory.GCD (extendedGCD)
chineseRemainder :: [(Integer,Integer)] -> Maybe Integer
chineseRemainder remainders = foldM addRem 0 remainders
where
!modulus = product (map snd remainders)
addRem acc (_,1) = Just acc
addRem acc (r,m) = do
let cf = modulus `quot` m
inv <- recipMod cf m
Just $! (acc + inv*cf*r) `mod` modulus
chineseRemainder2 :: (Integer,Integer) -> (Integer,Integer) -> Integer
chineseRemainder2 (r1, md1) (r2,md2)
= case extendedGCD md1 md2 of
(_,u,v) -> ((1 u*md1)*r1 + (1 v*md2)*r2) `mod` (md1*md2)
recipMod :: Integer -> Integer -> Maybe Integer
recipMod x m = case recipModInteger x m of
0 -> Nothing
y -> Just y