{-# LANGUAGE  NoImplicitPrelude, FlexibleInstances, ViewPatterns #-}

module Number.Modulo where

import NumericPrelude

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)