module Number.ResidueClass where
import qualified Algebra.PrincipalIdealDomain as PID
import qualified Algebra.IntegralDomain as Integral
import qualified Algebra.Additive as Additive
import qualified Algebra.ZeroTestable as ZeroTestable
import Algebra.ZeroTestable(isZero)
import PreludeBase
import NumericPrelude hiding (recip)
import Data.Maybe.HT (toMaybe)
import Data.Maybe (fromMaybe)
add, sub :: (Integral.C a) => a -> a -> a -> a
add m x y = mod (x+y) m
sub m x y = mod (xy) m
neg :: (Integral.C a) => a -> a -> a
neg m x = mod (x) m
mul :: (Integral.C a) => a -> a -> a -> a
mul m x y = mod (x*y) m
divideMaybe :: (PID.C a) => a -> a -> a -> Maybe a
divideMaybe m x y =
let (d,(_,z)) = extendedGCD m y
(q,r) = divMod x d
in toMaybe (isZero r) (mod (q*z) m)
divide :: (PID.C a) => a -> a -> a -> a
divide m x y =
fromMaybe (error "ResidueClass.divide: indivisible")
(divideMaybe m x y)
recip :: (PID.C a) => a -> a -> a
recip m = divide m one