{-# 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)