{-# LANGUAGE DerivingStrategies, GeneralizedNewtypeDeriving #-}
{-# LANGUAGE StandaloneDeriving                             #-}
-- | Prime fields
{-# LANGUAGE DataKinds, FlexibleContexts, FlexibleInstances          #-}
{-# LANGUAGE MultiParamTypeClasses, PolyKinds, RankNTypes            #-}
{-# LANGUAGE ScopedTypeVariables, TypeFamilies, UndecidableInstances #-}
module Algebra.Field.Prime
       ( F(), naturalRepr, reifyPrimeField, withPrimeField
       , modNat, modNat', modRat, modRat'
       , FiniteField(..), order
       ) where
import Algebra.Arithmetic            (modPow)
import Algebra.Field.Finite
import Algebra.Normed
import Algebra.Ring.Polynomial.Class (PrettyCoeff (..), ShowSCoeff (..))

import           AlgebraicPrelude
import           Control.DeepSeq              (NFData (..))
import           Control.Monad.Random         (getRandomR)
import           Control.Monad.Random         (runRand)
import           Control.Monad.Random         (Random (..))
import qualified Data.Coerce                  as C
import           Data.Maybe                   (fromMaybe)
import           Data.Proxy                   (Proxy (..), asProxyTypeOf)
import qualified Data.Ratio                   as R
import           Data.Reflection              (Reifies (reflect), reifyNat)
import           GHC.Read
import           GHC.TypeLits                 (KnownNat)
import           Numeric.Algebra              (char)
import           Numeric.Algebra              (Natural)
import qualified Numeric.Algebra              as NA
import           Numeric.Semiring.ZeroProduct (ZeroProductSemiring)
import qualified Prelude                      as P

-- | Prime field of characteristic @p@.
--   @p@ should be prime, and not statically checked.
newtype F (p :: k) = F { F p -> Integer
runF :: Integer }
  deriving (F p -> ()
(F p -> ()) -> NFData (F p)
forall a. (a -> ()) -> NFData a
forall k (p :: k). F p -> ()
rnf :: F p -> ()
$crnf :: forall k (p :: k). F p -> ()
NFData, Int -> F p -> Int
F p -> Int
(Int -> F p -> Int) -> (F p -> Int) -> Hashable (F p)
forall a. (Int -> a -> Int) -> (a -> Int) -> Hashable a
forall k (p :: k). Int -> F p -> Int
forall k (p :: k). F p -> Int
hash :: F p -> Int
$chash :: forall k (p :: k). F p -> Int
hashWithSalt :: Int -> F p -> Int
$chashWithSalt :: forall k (p :: k). Int -> F p -> Int
Hashable)

-- | Caution: just for use with Map or Sets;
--   no guarantee for the compatibility with
--   field structure and normal forms!
deriving newtype instance Ord (F p)


instance Reifies p Integer => Read (F p) where
  readPrec :: ReadPrec (F p)
readPrec = Integer -> F p
forall r. Num r => Integer -> r
fromInteger (Integer -> F p) -> ReadPrec Integer -> ReadPrec (F p)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ReadPrec Integer
forall a. Read a => ReadPrec a
readPrec

modNat :: Reifies (p :: k) Integer => Integer -> F p
modNat :: Integer -> F p
modNat = Proxy (F p) -> Integer -> F p
forall k (proxy :: * -> *) (p :: k).
Reifies p Integer =>
proxy (F p) -> Integer -> F p
modNat' Proxy (F p)
forall k (t :: k). Proxy t
Proxy
{-# INLINE modNat #-}

modNat' :: forall proxy p. Reifies p Integer => proxy (F p) -> Integer -> F p
modNat' :: proxy (F p) -> Integer -> F p
modNat' proxy (F p)
_ Integer
i =
  let p :: Integer
p = Proxy p -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect (Proxy p
forall k (t :: k). Proxy t
Proxy :: Proxy p)
  in Integer -> F p
forall k (p :: k). Integer -> F p
F (Integer
i Integer -> Integer -> Integer
forall d. Euclidean d => d -> d -> d
`rem` Integer
p)
{-# INLINE modNat' #-}

reifyPrimeField :: Integer -> (forall p. KnownNat p => Proxy (F p) -> a) -> a
reifyPrimeField :: Integer -> (forall (p :: Nat). KnownNat p => Proxy (F p) -> a) -> a
reifyPrimeField Integer
p forall (p :: Nat). KnownNat p => Proxy (F p) -> a
f = Integer -> (forall (n :: Nat). KnownNat n => Proxy n -> a) -> a
forall r.
Integer -> (forall (n :: Nat). KnownNat n => Proxy n -> r) -> r
reifyNat Integer
p (Proxy (F n) -> a
forall (p :: Nat). KnownNat p => Proxy (F p) -> a
f (Proxy (F n) -> a) -> (Proxy n -> Proxy (F n)) -> Proxy n -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Proxy n -> Proxy (F n)
forall k (a :: k). Proxy a -> Proxy (F a)
proxyF)

withPrimeField :: Integer -> (forall p. KnownNat p => F p) -> Integer
withPrimeField :: Integer -> (forall (p :: Nat). KnownNat p => F p) -> Integer
withPrimeField Integer
p forall (p :: Nat). KnownNat p => F p
f = Integer
-> (forall (p :: Nat). KnownNat p => Proxy (F p) -> Integer)
-> Integer
forall a.
Integer -> (forall (p :: Nat). KnownNat p => Proxy (F p) -> a) -> a
reifyPrimeField Integer
p ((forall (p :: Nat). KnownNat p => Proxy (F p) -> Integer)
 -> Integer)
-> (forall (p :: Nat). KnownNat p => Proxy (F p) -> Integer)
-> Integer
forall a b. (a -> b) -> a -> b
$ F p -> Integer
forall k (p :: k). F p -> Integer
runF (F p -> Integer) -> (Proxy (F p) -> F p) -> Proxy (F p) -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. F p -> Proxy (F p) -> F p
forall a (proxy :: * -> *). a -> proxy a -> a
asProxyTypeOf F p
forall (p :: Nat). KnownNat p => F p
f

naturalRepr :: F p -> Integer
naturalRepr :: F p -> Integer
naturalRepr = F p -> Integer
forall k (p :: k). F p -> Integer
runF

proxyF :: Proxy (a :: k) -> Proxy (F a)
proxyF :: Proxy a -> Proxy (F a)
proxyF Proxy a
Proxy = Proxy (F a)
forall k (t :: k). Proxy t
Proxy

instance Eq (F p) where
  F Integer
n == :: F p -> F p -> Bool
== F Integer
m = Integer
n Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
m

instance Reifies p Integer => Normed (F p) where
  type Norm (F p) = Integer
  norm :: F p -> Norm (F p)
norm fp :: F p
fp@(F Integer
p) = Integer
Norm (F p)
p where Integer
_ = F p -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect F p
fp
  liftNorm :: Norm (F p) -> F p
liftNorm = Norm (F p) -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat

instance Reifies p Integer => P.Num (F p) where
  fromInteger :: Integer -> F p
fromInteger = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat
  {-# INLINE fromInteger #-}

  + :: F p -> F p -> F p
(+) = (WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p))
-> F p -> F p -> F p
C.coerce (WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p)
forall a. Num a => a -> a -> a
(P.+) :: WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p))
  {-# INLINE (+) #-}

  (-) = (WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p))
-> F p -> F p -> F p
C.coerce (WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p)
forall a. Num a => a -> a -> a
(P.-) :: WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p))
  {-# INLINE (-) #-}

  negate :: F p -> F p
negate = (WrapAlgebra (F p) -> WrapAlgebra (F p)) -> F p -> F p
C.coerce (WrapAlgebra (F p) -> WrapAlgebra (F p)
forall a. Num a => a -> a
P.negate :: WrapAlgebra (F p) -> WrapAlgebra (F p))
  {-# INLINE negate #-}

  * :: F p -> F p -> F p
(*) = (WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p))
-> F p -> F p -> F p
C.coerce (WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p)
forall a. Num a => a -> a -> a
(P.*) :: WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p))
  {-# INLINE (*) #-}

  abs :: F p -> F p
abs = F p -> F p
forall a. a -> a
id
  signum :: F p -> F p
signum (F Integer
0) = Integer -> F p
forall k (p :: k). Integer -> F p
F Integer
0
  signum (F Integer
_) = Integer -> F p
forall k (p :: k). Integer -> F p
F Integer
1

pows :: (P.Integral a1, Reifies p Integer) => F p -> a1 -> F p
pows :: F p -> a1 -> F p
pows F p
a a1
n = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer -> F p) -> Integer -> F p
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Integer -> Integer
forall a r. (Integral a, Euclidean r) => r -> r -> a -> r
modPow (F p -> Integer
forall k (p :: k). F p -> Integer
runF F p
a) (F p -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect F p
a) (a1 -> Integer
forall a. Integral a => a -> Integer
toInteger a1
n)

instance Reifies p Integer => NA.Additive (F p) where
  F Integer
a + :: F p -> F p -> F p
+ F Integer
b = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer -> F p) -> Integer -> F p
forall a b. (a -> b) -> a -> b
$ Integer
a Integer -> Integer -> Integer
forall r. Additive r => r -> r -> r
+ Integer
b
  {-# INLINE (+) #-}
  sinnum1p :: Natural -> F p -> F p
sinnum1p Natural
n (F Integer
k) = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer -> F p) -> Integer -> F p
forall a b. (a -> b) -> a -> b
$ (Integer
1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
P.+ Natural -> Integer
forall a b. (Integral a, Num b) => a -> b
P.fromIntegral Natural
n) Integer -> Integer -> Integer
forall r. Multiplicative r => r -> r -> r
* Integer
k
  {-# INLINE sinnum1p #-}

instance Reifies p Integer => NA.Multiplicative (F p) where
  F Integer
a * :: F p -> F p -> F p
* F Integer
b = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer -> F p) -> Integer -> F p
forall a b. (a -> b) -> a -> b
$ Integer
a Integer -> Integer -> Integer
forall r. Multiplicative r => r -> r -> r
* Integer
b
  {-# INLINE (*) #-}

  pow1p :: F p -> Natural -> F p
pow1p F p
n Natural
p = F p -> Natural -> F p
forall k a1 (p :: k).
(Integral a1, Reifies p Integer) =>
F p -> a1 -> F p
pows F p
n (Natural
p Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
P.+ Natural
1)
  {-# INLINE pow1p #-}

instance Reifies p Integer => NA.Monoidal (F p) where
  zero :: F p
zero = Integer -> F p
forall k (p :: k). Integer -> F p
F Integer
0
  {-# INLINE zero #-}
  sinnum :: Natural -> F p -> F p
sinnum Natural
n (F Integer
k) = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer -> F p) -> Integer -> F p
forall a b. (a -> b) -> a -> b
$ Natural -> Integer
forall a b. (Integral a, Num b) => a -> b
P.fromIntegral Natural
n Integer -> Integer -> Integer
forall r. Multiplicative r => r -> r -> r
* Integer
k
  {-# INLINE sinnum #-}

instance Reifies p Integer => NA.LeftModule Natural (F p) where
  Natural
n .* :: Natural -> F p -> F p
.* F Integer
p = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Natural
n Natural -> Integer -> Integer
forall r m. LeftModule r m => r -> m -> m
.* Integer
p)
  {-# INLINE (.*) #-}

instance Reifies p Integer => NA.RightModule Natural (F p) where
  F Integer
p *. :: F p -> Natural -> F p
*. Natural
n = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer
p Integer -> Natural -> Integer
forall r m. RightModule r m => m -> r -> m
*. Natural
n)
  {-# INLINE (*.) #-}

instance Reifies p Integer => NA.LeftModule Integer (F p) where
  Integer
n .* :: Integer -> F p -> F p
.* F Integer
p = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer
n Integer -> Integer -> Integer
forall r. Multiplicative r => r -> r -> r
* Integer
p)
  {-# INLINE (.*) #-}

instance Reifies p Integer => NA.RightModule Integer (F p) where
  F Integer
p *. :: F p -> Integer -> F p
*. Integer
n = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer
p Integer -> Integer -> Integer
forall r. Multiplicative r => r -> r -> r
* Integer
n)
  {-# INLINE (*.) #-}

instance Reifies p Integer => NA.Group (F p) where
  F Integer
a - :: F p -> F p -> F p
- F Integer
b    = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer -> F p) -> Integer -> F p
forall a b. (a -> b) -> a -> b
$ Integer
a Integer -> Integer -> Integer
forall r. Group r => r -> r -> r
- Integer
b
  {-# INLINE (-) #-}

  negate :: F p -> F p
negate (F Integer
a) = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer -> F p) -> Integer -> F p
forall a b. (a -> b) -> a -> b
$ Integer -> Integer
forall r. Group r => r -> r
negate Integer
a
  {-# INLINE negate #-}

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 :: Natural -> F p
fromNatural = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer -> F p) -> (Natural -> Integer) -> Natural -> F p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> Integer
forall a b. (Integral a, Num b) => a -> b
P.fromIntegral
  {-# INLINE fromNatural #-}

instance Reifies p Integer => NA.Ring (F p) where
  fromInteger :: Integer -> F p
fromInteger = Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat
  {-# INLINE fromInteger #-}

instance Reifies p Integer => NA.DecidableZero (F p) where
  isZero :: F p -> Bool
isZero (F Integer
p) = Integer
p Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0

instance Reifies p Integer => NA.Unital (F p) where
  one :: F p
one = Integer -> F p
forall k (p :: k). Integer -> F p
F Integer
1
  {-# INLINE one #-}
  pow :: F p -> Natural -> F p
pow = F p -> Natural -> F p
forall k a1 (p :: k).
(Integral a1, Reifies p Integer) =>
F p -> a1 -> F p
pows
  {-# INLINE pow #-}

instance Reifies p Integer => DecidableUnits (F p) where
  isUnit :: F p -> Bool
isUnit (F Integer
n) = Integer
n Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
/= Integer
0
  {-# INLINE isUnit #-}

  recipUnit :: F p -> Maybe (F p)
recipUnit n :: F p
n@(F Integer
k) =
    let p :: Integer
p = Integer -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$ F p -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect F p
n
        (Integer
u,Integer
_,Integer
r) = [(Integer, Integer, Integer)] -> (Integer, Integer, Integer)
forall a. [a] -> a
head ([(Integer, Integer, Integer)] -> (Integer, Integer, Integer))
-> [(Integer, Integer, Integer)] -> (Integer, Integer, Integer)
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> [(Integer, Integer, Integer)]
forall d. Euclidean d => d -> d -> [(d, d, d)]
euclid Integer
p Integer
k
    in if Integer
u Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 then F p -> Maybe (F p)
forall a. a -> Maybe a
Just (F p -> Maybe (F p)) -> F p -> Maybe (F p)
forall a b. (a -> b) -> a -> b
$ Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer -> F p) -> Integer -> F p
forall a b. (a -> b) -> a -> b
$ Integer -> Integer
forall r. Num r => Integer -> r
fromInteger (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$ Integer
r Integer -> Integer -> Integer
forall d. Euclidean d => d -> d -> d
`rem` Integer
p else Maybe (F p)
forall a. Maybe a
Nothing
  {-# INLINE recipUnit #-}

instance (Reifies p Integer) => DecidableAssociates (F p) where
  isAssociate :: F p -> F p -> Bool
isAssociate F p
p F p
n =
    (F p -> Bool
forall r. DecidableZero r => r -> Bool
isZero F p
p Bool -> Bool -> Bool
&& F p -> Bool
forall r. DecidableZero r => r -> Bool
isZero F p
n) Bool -> Bool -> Bool
|| (Bool -> Bool
not (F p -> Bool
forall r. DecidableZero r => r -> Bool
isZero F p
p) Bool -> Bool -> Bool
&& Bool -> Bool
not (F p -> Bool
forall r. DecidableZero r => r -> Bool
isZero F p
n))
  {-# INLINE isAssociate #-}

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 :: F p -> F p
recip = F p -> Maybe (F p) -> F p
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> F p
forall a. HasCallStack => [Char] -> a
error [Char]
"recip: not unit") (Maybe (F p) -> F p) -> (F p -> Maybe (F p)) -> F p -> F p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. F p -> Maybe (F p)
forall r. DecidableUnits r => r -> Maybe r
recipUnit
  {-# INLINE recip #-}
  F p
a / :: F p -> F p -> F p
/ F p
b =  F p
a F p -> F p -> F p
forall r. Multiplicative r => r -> r -> r
* F p -> F p
forall r. Division r => r -> r
recip F p
b
  {-# INLINE (/) #-}
  ^ :: F p -> n -> F p
(^)   = F p -> n -> F p
forall k a1 (p :: k).
(Integral a1, Reifies p Integer) =>
F p -> a1 -> F p
pows
  {-# INLINE (^) #-}

instance Reifies p Integer => P.Fractional (F p) where
  / :: F p -> F p -> F p
(/) = (WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p))
-> F p -> F p -> F p
C.coerce (WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p)
forall a. Fractional a => a -> a -> a
(P./) :: WrapAlgebra (F p) -> WrapAlgebra (F p) -> WrapAlgebra (F p))
  {-# INLINE (/) #-}

  fromRational :: Rational -> F p
fromRational Rational
r =
    Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Rational -> Integer
forall a. Ratio a -> a
R.numerator Rational
r) F p -> F p -> F p
forall r. Multiplicative r => r -> r -> r
* F p -> F p
forall r. Division r => r -> r
recip (Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer -> F p) -> Integer -> F p
forall a b. (a -> b) -> a -> b
$ Rational -> Integer
forall a. Ratio a -> a
R.denominator Rational
r)
  {-# INLINE fromRational #-}

  recip :: F p -> F p
recip = (WrapAlgebra (F p) -> WrapAlgebra (F p)) -> F p -> F p
C.coerce (WrapAlgebra (F p) -> WrapAlgebra (F p)
forall a. Fractional a => a -> a
P.recip :: WrapAlgebra (F p) -> WrapAlgebra (F p))
  {-# INLINE recip #-}

instance Reifies p Integer => NA.Commutative (F p)

instance Reifies p Integer => NA.Characteristic (F p) where
  char :: proxy (F p) -> Natural
char proxy (F p)
_ = Integer -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Integer -> Natural) -> Integer -> Natural
forall a b. (a -> b) -> a -> b
$ Proxy p -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect (Proxy p
forall k (t :: k). Proxy t
Proxy :: Proxy p)
  {-# INLINE char #-}


instance Reifies (p :: k) Integer => Show (F p) where
  showsPrec :: Int -> F p -> ShowS
showsPrec Int
d n :: F p
n@(F Integer
p) = Int -> Integer -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
d (Integer
p Integer -> Integer -> Integer
forall d. Euclidean d => d -> d -> d
`rem` F p -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect F p
n)

instance Reifies (p :: k) Integer => PrettyCoeff (F p) where
  showsCoeff :: Int -> F p -> ShowSCoeff
showsCoeff Int
d (F Integer
p)
    | Integer
p Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = ShowSCoeff
Vanished
    | Integer
p Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = ShowSCoeff
OneCoeff
    | Bool
otherwise = ShowS -> ShowSCoeff
Positive (ShowS -> ShowSCoeff) -> ShowS -> ShowSCoeff
forall a b. (a -> b) -> a -> b
$ Int -> Integer -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
d Integer
p

instance Reifies p P.Integer => FiniteField (F p) where
  power :: proxy (F p) -> Natural
power proxy (F p)
_ = Natural
1
  {-# INLINE power #-}

  elements :: proxy (F p) -> [F p]
elements proxy (F p)
p = (Integer -> F p) -> [Integer] -> [F p]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
map Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat [Integer
0.. Natural -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (proxy (F p) -> Natural
forall r (proxy :: * -> *). Characteristic r => proxy r -> Natural
char proxy (F p)
p) Integer -> Integer -> Integer
forall r. Group r => r -> r -> r
- Integer
1]
  {-# INLINE elements #-}

instance Reifies p Integer => Random (F p) where
  random :: g -> (F p, g)
random = Rand g (F p) -> g -> (F p, g)
forall g a. Rand g a -> g -> (a, g)
runRand (Rand g (F p) -> g -> (F p, g)) -> Rand g (F p) -> g -> (F p, g)
forall a b. (a -> b) -> a -> b
$ Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer -> F p) -> RandT g Identity Integer -> Rand g (F p)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>
    (Integer, Integer) -> RandT g Identity Integer
forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
getRandomR (Integer
0 :: Integer, Proxy p -> Integer
forall k (s :: k) a (proxy :: k -> *). Reifies s a => proxy s -> a
reflect (Proxy p
forall k (t :: k). Proxy t
Proxy :: Proxy p) Integer -> Integer -> Integer
forall r. Group r => r -> r -> r
- Integer
1)
  {-# INLINE random #-}
  randomR :: (F p, F p) -> g -> (F p, g)
randomR (F p
a, F p
b) = Rand g (F p) -> g -> (F p, g)
forall g a. Rand g a -> g -> (a, g)
runRand (Rand g (F p) -> g -> (F p, g)) -> Rand g (F p) -> g -> (F p, g)
forall a b. (a -> b) -> a -> b
$ Integer -> F p
forall k (p :: k). Reifies p Integer => Integer -> F p
modNat (Integer -> F p) -> RandT g Identity Integer -> Rand g (F p)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>
    (Integer, Integer) -> RandT g Identity Integer
forall (m :: * -> *) a. (MonadRandom m, Random a) => (a, a) -> m a
getRandomR (F p -> Integer
forall k (p :: k). F p -> Integer
naturalRepr F p
a, F p -> Integer
forall k (p :: k). F p -> Integer
naturalRepr F p
b)
  {-# INLINE randomR #-}

modRat :: FiniteField k => Proxy k -> Fraction Integer -> k
modRat :: Proxy k -> Fraction Integer -> k
modRat Proxy k
_ Fraction Integer
q = Integer -> k
forall r. Ring r => Integer -> r
NA.fromInteger (Fraction Integer -> Integer
forall t. Fraction t -> t
numerator Fraction Integer
q) k -> k -> k
forall r. Division r => r -> r -> r
NA./ Integer -> k
forall r. Ring r => Integer -> r
NA.fromInteger (Fraction Integer -> Integer
forall t. Fraction t -> t
denominator Fraction Integer
q)
{-# INLINE modRat #-}

modRat' :: FiniteField k => Fraction Integer -> k
modRat' :: Fraction Integer -> k
modRat' = Proxy k -> Fraction Integer -> k
forall k. FiniteField k => Proxy k -> Fraction Integer -> k
modRat Proxy k
forall k (t :: k). Proxy t
Proxy
{-# INLINE modRat' #-}