{-# LANGUAGE NoImplicitPrelude, FlexibleInstances, ViewPatterns #-} module Number.Modulo where import NumericPrelude import Algebra.Additive as Group import Algebra.Ring as Ring import Algebra.Field as Field import Algebra.IntegralDomain as Integral import Algebra.ToInteger as ToInteger import Algebra.PrincipalIdealDomain as PrincipalIdeal import Algebra.Algebraic as Algebraic import Algebra.ToInteger as ToInteger import qualified Number.ResidueClass as RC import qualified GHC.Num as N newtype Mod a = Mod (a -> a) instance Bounded Integer where maxBound = 10^64 minBound = - 10^64 instance (Show a, Bounded a) => Show (Mod a) where show = show . (`modulo` maxBound) instance (Integral.C a, PrincipalIdeal.C a, Eq a) => Integral.C (Mod a) where div (Mod x) (Mod y) = Mod \$ \n -> RC.divide n (x n) (y n) mod x y = x - (x `div` y) * y instance (Integral.C a, PrincipalIdeal.C a, Ring.C a) => Field.C (Mod a) where recip (Mod x) = Mod \$ \n -> RC.recip n (x n) instance (Integral.C a, Group.C a) => Group.C (Mod a) where zero = Mod \$ \_ -> zero Mod x + Mod y = Mod \$ \n -> RC.add n (x n) (y n) Mod x - Mod y = Mod \$ \n -> RC.sub n (x n) (y n) negate (Mod x) = Mod \$ \n -> RC.neg n (x n) instance (Integral.C a, Ring.C a) => Ring.C (Mod a) where one = Mod \$ \_ -> one Mod x * Mod y = Mod \$ \n -> RC.mul n (x n) (y n) fromInteger k = Mod (fromInteger k `mod`) Mod x ^ y = Mod \$ \n -> pow (RC.mul n) (sq n) (x n) y instance (Integral.C a, PrincipalIdeal.C a, Group.C a, Eq a, ToInteger.C a) => Algebraic.C (Mod a) where sqrt x = Mod \$ \p -> if (x ^ (toInteger p-1 `div` 2) `modulo` p) == one then if toInteger p `mod` 4 == 3 then x ^ (toInteger p+1 `div` 4) `modulo` p else undefined else error "Not a quadratic residue" root k x = Mod \$ \p -> if gcd k (toInteger p-1) == one then x ^ (RC.recip (toInteger p-1) k) `modulo` p else undefined instance (Integral.C a, Group.C a, Ring.C a) => N.Num (Mod a) where fromInteger = fromInteger (*) = (*) (+) = (+) (-) = (-) abs = undefined signum = undefined sq n x = RC.mul n x x pow mul sq x n = f x n one where f x n y | n == zero = one | n == one = x `mul` y | r == zero = f (sq x) q y | otherwise = f (sq x) q (x `mul` y) where (q,r) = n `quotRem` 2 -- | Calculate x modulo n Mod x `modulo` n = x n infixr 2 `modulo` x === y = \f -> f x == f y infixl 3 === -- |Examples n = 2 :: Mod Integer ex1 = n ^ 2^100 `modulo` 10^8 ex2 = n ^ 100 === n ^ 200 \$ (`modulo` 123)