module Algebra.Field.Finite (F(), naturalRepr, reifyPrimeField, withPrimeField,
modNat, modNat', modRat, modRat', FiniteField(..), order) where
import Algebra.Algorithms.PrimeTest
import Algebra.Prelude.Core hiding (pow)
import Algebra.Ring.Polynomial.Class (PrettyCoeff (..), ShowSCoeff (..))
import Control.DeepSeq (NFData (..))
import Control.Monad.Random (uniform)
import Control.Monad.Random (runRand)
import Control.Monad.Random (Random (..))
import qualified Data.Coerce as C
import Data.Maybe (fromMaybe)
import qualified Data.Ratio as R
import Data.Reflection (Reifies (reflect), reifyNat)
import GHC.TypeLits (KnownNat)
import Numeric.Algebra (Field)
import Numeric.Algebra (char)
import Numeric.Algebra (Natural)
import qualified Numeric.Algebra as NA
import Numeric.Rig.Characteristic (Characteristic)
import Numeric.Semiring.ZeroProduct (ZeroProductSemiring)
import qualified Prelude as P
newtype F (p :: k) = F { runF :: Integer }
deriving (NFData)
naturalRepr :: F p -> Integer
naturalRepr = runF
instance Reifies (p :: k) Integer => Show (F p) where
showsPrec d n@(F p) = showsPrec d (p `rem` reflect n)
instance Reifies (p :: k) Integer => PrettyCoeff (F p) where
showsCoeff d (F p) =
if p == 0
then Vanished
else if p == 1
then OneCoeff
else Positive $ showsPrec d p
modNat :: Reifies (p :: k) Integer => Integer -> F p
modNat = modNat' Proxy
modNat' :: forall proxy (p :: k). Reifies p Integer => proxy (F p) -> Integer -> F p
modNat' _ i =
let p = reflect (Proxy :: Proxy p)
in F (i `rem` p)
reifyPrimeField :: Integer -> (forall p. KnownNat p => Proxy (F p) -> a) -> a
reifyPrimeField p f = reifyNat p (\pxy -> f (proxyF pxy))
withPrimeField :: Integer -> (forall p. KnownNat p => F p) -> Integer
withPrimeField p f = reifyPrimeField p $ runF . asProxyTypeOf f
proxyF :: Proxy (a :: k) -> Proxy (F a)
proxyF Proxy = Proxy
instance Eq (F p) where
F n == F m = n == m
instance Reifies p Integer => Normed (F p) where
type Norm (F p) = Integer
norm fp@(F p) = p where _ = reflect fp
liftNorm = modNat
instance Reifies p Integer => P.Num (F p) where
fromInteger = fromInteger'
(+) = C.coerce ((P.+) :: WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p))
() = C.coerce ((P.-) :: WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p))
negate = C.coerce (P.negate :: WrapAlgebra (F p) -> WrapAlgebra (F p))
(*) = C.coerce ((P.*) :: WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p))
abs = id
signum (F 0) = F 0
signum (F _) = F 1
pows :: (P.Integral a1, Reifies p Integer) => F p -> a1 -> F p
pows a n = modNat $ modPow (runF a) (reflect a) n
instance Reifies p Integer => NA.Additive (F p) where
F a + F b = modNat $ a + b
sinnum1p n (F k) = modNat $ (1 P.+ P.fromIntegral n) * k
instance Reifies p Integer => NA.Multiplicative (F p) where
F a * F b = modNat $ a * b
pow1p n p = pows n (p P.+ 1)
instance Reifies p Integer => NA.Monoidal (F p) where
zero = F 0
sinnum n (F k) = modNat $ P.fromIntegral n * k
instance Reifies p Integer => NA.LeftModule Natural (F p) where
n .* F p = modNat (n .* p)
instance Reifies p Integer => NA.RightModule Natural (F p) where
F p *. n = modNat (p *. n)
instance Reifies p Integer => NA.LeftModule Integer (F p) where
n .* F p = modNat (n * p)
instance Reifies p Integer => NA.RightModule Integer (F p) where
F p *. n = modNat (p * n)
instance Reifies p Integer => NA.Group (F p) where
F a F b = modNat $ a b
negate (F a) = F (reflect (Proxy :: Proxy p) a)
instance Reifies p Integer => NA.Abelian (F p)
instance Reifies p Integer => NA.Semiring (F p)
instance Reifies p Integer => NA.Rig (F p) where
fromNatural = modNat . P.fromIntegral
instance Reifies p Integer => NA.Ring (F p) where
fromInteger = modNat
instance Reifies p Integer => NA.DecidableZero (F p) where
isZero (F p) = p == 0
instance Reifies p Integer => NA.Unital (F p) where
one = F 1
pow = pows
instance Reifies p Integer => DecidableUnits (F p) where
isUnit (F n) = n /= 0
recipUnit n@(F k) =
let p = fromIntegral $ reflect n
(u,_,r) = head $ euclid p k
in if u == 1 then Just $ modNat $ fromInteger $ r `rem` p else Nothing
instance (Reifies p Integer) => DecidableAssociates (F p) where
isAssociate p n =
(isZero p && isZero n) || (not (isZero p) && not (isZero n))
instance (Reifies p Integer) => UnitNormalForm (F p)
instance (Reifies p Integer) => IntegralDomain (F p)
instance (Reifies p Integer) => GCDDomain (F p)
instance (Reifies p Integer) => UFD (F p)
instance (Reifies p Integer) => PID (F p)
instance (Reifies p Integer) => ZeroProductSemiring (F p)
instance (Reifies p Integer) => Euclidean (F p)
instance Reifies p Integer => Division (F p) where
recip = fromMaybe (error "recip: not unit") . recipUnit
a / b = a * recip b
(^) = pows
instance Reifies p Integer => P.Fractional (F p) where
(/) = C.coerce ((P./) :: WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p))
fromRational r =
modNat (R.numerator r) * recip (modNat $ R.denominator r)
recip = C.coerce (P.recip :: WrapAlgebra (F p) -> WrapAlgebra (F p))
instance Reifies p Integer => NA.Commutative (F p)
instance Reifies p Integer => NA.Characteristic (F p) where
char _ = fromIntegral $ reflect (Proxy :: Proxy p)
class (Field k, Characteristic k) => FiniteField k where
power :: proxy k -> Natural
elements :: proxy k -> [k]
instance Reifies p Integer => FiniteField (F p) where
power _ = 1
elements p = map modNat [0.. fromIntegral (char p) 1]
order :: FiniteField k => proxy k -> Natural
order p = char p ^ power p
instance Reifies p Integer => Random (F p) where
random = runRand $ uniform (elements Proxy)
randomR (a, b) = runRand $ uniform $ map modNat [naturalRepr a..naturalRepr b]
modRat :: FiniteField k => Proxy k -> Fraction Integer -> k
modRat _ q = NA.fromInteger (numerator q) NA./ NA.fromInteger (denominator q)
modRat' :: FiniteField k => Fraction Integer -> k
modRat' = modRat Proxy