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 p1 `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 p1) == one then x ^ (RC.recip (toInteger p1) 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
Mod x `modulo` n = x n
infixr 2 `modulo`
x === y = \f -> f x == f y
infixl 3 ===
n = 2 :: Mod Integer
ex1 = n ^ 2^100 `modulo` 10^8
ex2 = n ^ 100 === n ^ 200 $ (`modulo` 123)