module PrimeField
( PrimeField
, toInt
) where
import Protolude as P hiding (Semiring)
import Control.Monad.Random (Random(..))
import Data.Euclidean (Euclidean(..), GcdDomain(..))
import Data.Semiring (Ring(..), Semiring(..))
import GHC.Integer.GMP.Internals (powModInteger, recipModInteger)
import Test.Tasty.QuickCheck (Arbitrary(..), choose)
import Text.PrettyPrint.Leijen.Text (Pretty(..))
import GaloisField (Field(..), GaloisField(..))
newtype PrimeField (p :: Nat) = PF Integer
deriving (Bits, Eq, Generic, Ord, Show)
instance KnownNat p => GaloisField (PrimeField p) where
char = natVal
{-# INLINABLE char #-}
deg = const 1
{-# INLINABLE deg #-}
frob = identity
{-# INLINABLE frob #-}
pow (PF x) n = PF (powModInteger x n (natVal (witness :: PrimeField p)))
{-# INLINE pow #-}
{-# RULES "PrimeField/pow"
forall (k :: KnownNat p => PrimeField p) (n :: Integer) . (^) k n = pow k n
#-}
instance KnownNat p => Fractional (PrimeField p) where
recip (PF 0) = panic "no multiplicative inverse."
recip (PF x) = PF (recipModInteger x (natVal (witness :: PrimeField p)))
{-# INLINE recip #-}
fromRational (x:%y) = fromInteger x / fromInteger y
{-# INLINABLE fromRational #-}
instance KnownNat p => Num (PrimeField p) where
PF x + PF y = PF (if xyp >= 0 then xyp else xy)
where
xy = x + y
xyp = xy - natVal (witness :: PrimeField p)
{-# INLINE (+) #-}
PF x * PF y = PF (P.rem (x * y) (natVal (witness :: PrimeField p)))
{-# INLINE (*) #-}
PF x - PF y = PF (if xy >= 0 then xy else xy + natVal (witness :: PrimeField p))
where
xy = x - y
{-# INLINE (-) #-}
negate (PF 0) = PF 0
negate (PF x) = PF (natVal (witness :: PrimeField p) - x)
{-# INLINE negate #-}
fromInteger x = PF (if y >= 0 then y else y + p)
where
y = P.rem x p
p = natVal (witness :: PrimeField p)
{-# INLINABLE fromInteger #-}
abs = panic "not implemented."
signum = panic "not implemented."
instance KnownNat p => Euclidean (PrimeField p) where
quotRem = (flip (,) 0 .) . (/)
{-# INLINE quotRem #-}
degree = panic "not implemented."
instance KnownNat p => Field (PrimeField p) where
invert = recip
{-# INLINE invert #-}
minus = (-)
{-# INLINE minus #-}
instance KnownNat p => GcdDomain (PrimeField p)
instance KnownNat p => Ring (PrimeField p) where
negate = P.negate
{-# INLINE negate #-}
instance KnownNat p => Semiring (PrimeField p) where
zero = 0
{-# INLINE zero #-}
plus = (+)
{-# INLINE plus #-}
one = 1
{-# INLINE one #-}
times = (*)
{-# INLINE times #-}
fromNatural = fromIntegral
{-# INLINABLE fromNatural #-}
instance KnownNat p => Arbitrary (PrimeField p) where
arbitrary = PF <$> choose (0, natVal (witness :: PrimeField p) - 1)
{-# INLINABLE arbitrary #-}
instance KnownNat p => Pretty (PrimeField p) where
pretty (PF x) = pretty x
instance KnownNat p => Random (PrimeField p) where
random = first PF . randomR (0, natVal (witness :: PrimeField p) - 1)
{-# INLINABLE random #-}
randomR = panic "not implemented."
toInt :: PrimeField p -> Integer
toInt (PF x) = x
{-# INLINABLE toInt #-}