{-# LANGUAGE AllowAmbiguousTypes  #-}
{-# LANGUAGE DerivingStrategies   #-}
{-# LANGUAGE OverloadedLists      #-}
{-# LANGUAGE TypeApplications     #-}
{-# LANGUAGE TypeOperators        #-}
{-# LANGUAGE UndecidableInstances #-}

module ZkFold.Base.Algebra.Basic.Field (
    IrreduciblePoly(..),
    Zp,
    toZp,
    fromZp,
    inv,
    Ext2(..),
    Ext3(..)
    ) where

import           Control.Applicative                        ((<|>))
import           Control.DeepSeq                            (NFData (..))
import           Data.Aeson                                 (FromJSON (..), ToJSON (..))
import           Data.Bifunctor                             (first)
import           Data.Bool                                  (bool)
import qualified Data.Vector                                as V
import           GHC.Generics                               (Generic)
import           GHC.Real                                   ((%))
import           GHC.TypeLits                               (Symbol)
import           Prelude                                    hiding (Fractional (..), Num (..), div, length, (^))
import qualified Prelude                                    as Haskell
import           System.Random                              (Random (..), RandomGen, mkStdGen, uniformR)
import           Test.QuickCheck                            hiding (scale)

import           ZkFold.Base.Algebra.Basic.Class            hiding (Euclidean (..))
import           ZkFold.Base.Algebra.Basic.Number
import           ZkFold.Base.Algebra.Polynomials.Univariate
import           ZkFold.Base.Data.ByteString
import           ZkFold.Prelude                             (log2ceiling)

------------------------------ Prime Fields -----------------------------------

newtype Zp (p :: Natural) = Zp Integer
    deriving ((forall x. Zp p -> Rep (Zp p) x)
-> (forall x. Rep (Zp p) x -> Zp p) -> Generic (Zp p)
forall (p :: Natural) x. Rep (Zp p) x -> Zp p
forall (p :: Natural) x. Zp p -> Rep (Zp p) x
forall x. Rep (Zp p) x -> Zp p
forall x. Zp p -> Rep (Zp p) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cfrom :: forall (p :: Natural) x. Zp p -> Rep (Zp p) x
from :: forall x. Zp p -> Rep (Zp p) x
$cto :: forall (p :: Natural) x. Rep (Zp p) x -> Zp p
to :: forall x. Rep (Zp p) x -> Zp p
Generic, Zp p -> ()
(Zp p -> ()) -> NFData (Zp p)
forall (p :: Natural). Zp p -> ()
forall a. (a -> ()) -> NFData a
$crnf :: forall (p :: Natural). Zp p -> ()
rnf :: Zp p -> ()
NFData)

{-# INLINE fromZp #-}
fromZp :: Zp p -> Natural
fromZp :: forall (p :: Natural). Zp p -> Natural
fromZp (Zp Integer
a) = Integer -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral Integer
a

{-# INLINE residue #-}
residue :: forall p . KnownNat p => Integer -> Integer
residue :: forall (p :: Natural). KnownNat p => Integer -> Integer
residue = (Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`Haskell.mod` Natural -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall (n :: Natural). KnownNat n => Natural
value @p))

{-# INLINE toZp #-}
toZp :: forall p . KnownNat p => Integer -> Zp p
toZp :: forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp = Integer -> Zp p
forall (p :: Natural). Integer -> Zp p
Zp (Integer -> Zp p) -> (Integer -> Integer) -> Integer -> Zp p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (p :: Natural). KnownNat p => Integer -> Integer
residue @p

instance ToConstant (Zp p) where
    type Const (Zp p) = Natural
    toConstant :: Zp p -> Const (Zp p)
toConstant = Zp p -> Natural
Zp p -> Const (Zp p)
forall (p :: Natural). Zp p -> Natural
fromZp

instance (KnownNat p, KnownNat (NumberOfBits (Zp p))) => Finite (Zp p) where
    type Order (Zp p) = p

instance KnownNat p => Eq (Zp p) where
    Zp Integer
a == :: Zp p -> Zp p -> Bool
== Zp Integer
b = forall (p :: Natural). KnownNat p => Integer -> Integer
residue @p (Integer
a Integer -> Integer -> Integer
forall a. AdditiveGroup a => a -> a -> a
- Integer
b) Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0

instance KnownNat p => Ord (Zp p) where
    Zp Integer
a <= :: Zp p -> Zp p -> Bool
<= Zp Integer
b = forall (p :: Natural). KnownNat p => Integer -> Integer
residue @p Integer
a Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= forall (p :: Natural). KnownNat p => Integer -> Integer
residue @p Integer
b

instance KnownNat p => AdditiveSemigroup (Zp p) where
    Zp Integer
a + :: Zp p -> Zp p -> Zp p
+ Zp Integer
b = Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp (Integer
a Integer -> Integer -> Integer
forall a. AdditiveSemigroup a => a -> a -> a
+ Integer
b)

instance KnownNat p => Scale Natural (Zp p) where
    scale :: Natural -> Zp p -> Zp p
scale Natural
c (Zp Integer
a) = Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp (Natural -> Integer -> Integer
forall b a. Scale b a => b -> a -> a
scale Natural
c Integer
a)

instance KnownNat p => AdditiveMonoid (Zp p) where
    zero :: Zp p
zero = Integer -> Zp p
forall (p :: Natural). Integer -> Zp p
Zp Integer
0

instance KnownNat p => Scale Integer (Zp p) where
    scale :: Integer -> Zp p -> Zp p
scale Integer
c (Zp Integer
a) = Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp (Integer -> Integer -> Integer
forall b a. Scale b a => b -> a -> a
scale Integer
c Integer
a)

instance KnownNat p => AdditiveGroup (Zp p) where
    negate :: Zp p -> Zp p
negate (Zp Integer
a) = Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp (Integer -> Integer
forall a. AdditiveGroup a => a -> a
negate Integer
a)
    Zp Integer
a - :: Zp p -> Zp p -> Zp p
- Zp Integer
b   = Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp (Integer
a Integer -> Integer -> Integer
forall a. AdditiveGroup a => a -> a -> a
- Integer
b)

instance KnownNat p => MultiplicativeSemigroup (Zp p) where
    Zp Integer
a * :: Zp p -> Zp p -> Zp p
* Zp Integer
b = Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp (Integer
a Integer -> Integer -> Integer
forall a. MultiplicativeSemigroup a => a -> a -> a
* Integer
b)

instance KnownNat p => Exponent (Zp p) Natural where
    ^ :: Zp p -> Natural -> Zp p
(^) = Zp p -> Natural -> Zp p
forall a. MultiplicativeMonoid a => a -> Natural -> a
natPow

instance KnownNat p => MultiplicativeMonoid (Zp p) where
    one :: Zp p
one = Integer -> Zp p
forall (p :: Natural). Integer -> Zp p
Zp Integer
1

instance KnownNat p => FromConstant Natural (Zp p) where
    fromConstant :: Natural -> Zp p
fromConstant = Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp (Integer -> Zp p) -> (Natural -> Integer) -> Natural -> Zp p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> Integer
forall a b. FromConstant a b => a -> b
fromConstant

instance KnownNat p => Semiring (Zp p)

instance KnownNat p => SemiEuclidean (Zp p) where
    divMod :: Zp p -> Zp p -> (Zp p, Zp p)
divMod Zp p
a Zp p
b = let (Natural
q, Natural
r) = Natural -> Natural -> (Natural, Natural)
forall a. Integral a => a -> a -> (a, a)
Haskell.divMod (Zp p -> Natural
forall (p :: Natural). Zp p -> Natural
fromZp Zp p
a) (Zp p -> Natural
forall (p :: Natural). Zp p -> Natural
fromZp Zp p
b)
                  in (Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp (Integer -> Zp p) -> (Natural -> Integer) -> Natural -> Zp p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Natural -> Zp p) -> Natural -> Zp p
forall a b. (a -> b) -> a -> b
$ Natural
q, Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp (Integer -> Zp p) -> (Natural -> Integer) -> Natural -> Zp p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Natural -> Zp p) -> Natural -> Zp p
forall a b. (a -> b) -> a -> b
$ Natural
r)

instance KnownNat p => FromConstant Integer (Zp p) where
    fromConstant :: Integer -> Zp p
fromConstant = Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp

instance KnownNat p => Ring (Zp p)

instance Prime p => Exponent (Zp p) Integer where
    -- | By Fermat's little theorem
    Zp p
a ^ :: Zp p -> Integer -> Zp p
^ Integer
n = Zp p -> Integer -> Zp p
forall a. Field a => a -> Integer -> a
intPowF Zp p
a (Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`Haskell.mod` (Natural -> Integer
forall a b. FromConstant a b => a -> b
fromConstant (forall (n :: Natural). KnownNat n => Natural
value @p) Integer -> Integer -> Integer
forall a. AdditiveGroup a => a -> a -> a
- Integer
1))

instance Prime p => Field (Zp p) where
    finv :: Zp p -> Zp p
finv (Zp Integer
a) = Natural -> Zp p
forall a b. FromConstant a b => a -> b
fromConstant (Natural -> Zp p) -> Natural -> Zp p
forall a b. (a -> b) -> a -> b
$ Integer -> Natural -> Natural
inv Integer
a (forall (n :: Natural). KnownNat n => Natural
value @p)

    rootOfUnity :: Natural -> Maybe (Zp p)
rootOfUnity Natural
l
      | Natural
l Natural -> Natural -> Bool
forall a. Eq a => a -> a -> Bool
== Natural
0                       = Maybe (Zp p)
forall a. Maybe a
Nothing
      | (forall (n :: Natural). KnownNat n => Natural
value @p Natural -> Natural -> Natural
-! Natural
1) Natural -> Natural -> Natural
forall a. Integral a => a -> a -> a
`Haskell.mod` Natural
n Natural -> Natural -> Bool
forall a. Eq a => a -> a -> Bool
/= Natural
0 = Maybe (Zp p)
forall a. Maybe a
Nothing
      | Bool
otherwise = Zp p -> Maybe (Zp p)
forall a. a -> Maybe a
Just (Zp p -> Maybe (Zp p)) -> Zp p -> Maybe (Zp p)
forall a b. (a -> b) -> a -> b
$ StdGen -> Zp p
forall g. RandomGen g => g -> Zp p
rootOfUnity' (Int -> StdGen
mkStdGen Int
0)
        where
          n :: Natural
n = Natural
2 Natural -> Natural -> Natural
forall a b. Exponent a b => a -> b -> a
^ Natural
l
          rootOfUnity' :: RandomGen g => g -> Zp p
          rootOfUnity' :: forall g. RandomGen g => g -> Zp p
rootOfUnity' g
g =
              let (Zp p
x, g
g') = (Natural -> Zp p) -> (Natural, g) -> (Zp p, g)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: Type -> Type -> Type) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first Natural -> Zp p
forall a b. FromConstant a b => a -> b
fromConstant ((Natural, g) -> (Zp p, g)) -> (Natural, g) -> (Zp p, g)
forall a b. (a -> b) -> a -> b
$ (Natural, Natural) -> g -> (Natural, g)
forall g a. (RandomGen g, UniformRange a) => (a, a) -> g -> (a, g)
uniformR (Natural
1, forall (n :: Natural). KnownNat n => Natural
value @p Natural -> Natural -> Natural
-! Natural
1) g
g
                  x' :: Zp p
x' = Zp p
x Zp p -> Natural -> Zp p
forall a b. Exponent a b => a -> b -> a
^ ((forall (n :: Natural). KnownNat n => Natural
value @p Natural -> Natural -> Natural
-! Natural
1) Natural -> Natural -> Natural
forall a. Integral a => a -> a -> a
`Haskell.div` Natural
n)
              in Zp p -> Zp p -> Bool -> Zp p
forall a. a -> a -> Bool -> a
bool (g -> Zp p
forall g. RandomGen g => g -> Zp p
rootOfUnity' g
g') Zp p
x' (Zp p
x' Zp p -> Natural -> Zp p
forall a b. Exponent a b => a -> b -> a
^ (Natural
n Natural -> Natural -> Natural
forall a. Integral a => a -> a -> a
`Haskell.div` Natural
2) Zp p -> Zp p -> Bool
forall a. Eq a => a -> a -> Bool
/= Zp p
forall a. MultiplicativeMonoid a => a
one)

inv :: Integer -> Natural -> Natural
inv :: Integer -> Natural -> Natural
inv Integer
a Natural
p = Integer -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Integer -> Natural) -> Integer -> Natural
forall a b. (a -> b) -> a -> b
$ (Integer, Integer) -> Integer
forall a b. (a, b) -> b
snd ((Integer, Integer) -> (Integer, Integer) -> (Integer, Integer)
forall {b}.
(Eq b, Num b, SemiEuclidean b, AdditiveGroup b) =>
(b, b) -> (b, b) -> (b, b)
egcd (Integer
a, Integer
1) (Natural -> Integer
forall a b. FromConstant a b => a -> b
fromConstant Natural
p, Integer
0)) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`Haskell.mod` Natural -> Integer
forall a b. FromConstant a b => a -> b
fromConstant Natural
p
  where
    egcd :: (b, b) -> (b, b) -> (b, b)
egcd (b
x, b
y) (b
0, b
_) = (b
x, b
y)
    egcd (b
x, b
y) (b
x', b
y') = (b, b) -> (b, b) -> (b, b)
egcd (b
x', b
y') (b
x b -> b -> b
forall a. AdditiveGroup a => a -> a -> a
- b
q b -> b -> b
forall a. MultiplicativeSemigroup a => a -> a -> a
* b
x', b
y b -> b -> b
forall a. AdditiveGroup a => a -> a -> a
- b
q b -> b -> b
forall a. MultiplicativeSemigroup a => a -> a -> a
* b
y')
      where q :: b
q = b
x b -> b -> b
forall a. SemiEuclidean a => a -> a -> a
`div` b
x'

instance Prime p => BinaryExpansion (Zp p) where
    type Bits (Zp p) = [Zp p]
    binaryExpansion :: Zp p -> Bits (Zp p)
binaryExpansion = (Natural -> Zp p) -> [Natural] -> [Zp p]
forall a b. (a -> b) -> [a] -> [b]
map (Integer -> Zp p
forall (p :: Natural). Integer -> Zp p
Zp (Integer -> Zp p) -> (Natural -> Integer) -> Natural -> Zp p
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> Integer
forall a b. FromConstant a b => a -> b
fromConstant) ([Natural] -> [Zp p]) -> (Zp p -> [Natural]) -> Zp p -> [Zp p]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Natural -> [Natural]
Natural -> Bits Natural
forall a. BinaryExpansion a => a -> Bits a
binaryExpansion (Natural -> [Natural]) -> (Zp p -> Natural) -> Zp p -> [Natural]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Zp p -> Natural
forall (p :: Natural). Zp p -> Natural
fromZp

instance Prime p => DiscreteField' (Zp p)

instance Prime p => TrichotomyField (Zp p)

instance KnownNat p => Haskell.Num (Zp p) where
    fromInteger :: Integer -> Zp p
fromInteger = Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp
    + :: Zp p -> Zp p -> Zp p
(+)         = Zp p -> Zp p -> Zp p
forall a. AdditiveSemigroup a => a -> a -> a
(+)
    (-)         = (-)
    * :: Zp p -> Zp p -> Zp p
(*)         = Zp p -> Zp p -> Zp p
forall a. MultiplicativeSemigroup a => a -> a -> a
(*)
    negate :: Zp p -> Zp p
negate      = Zp p -> Zp p
forall a. AdditiveGroup a => a -> a
negate
    abs :: Zp p -> Zp p
abs         = Zp p -> Zp p
forall a. a -> a
id
    signum :: Zp p -> Zp p
signum      = Zp p -> Zp p -> Zp p
forall a b. a -> b -> a
const Zp p
1

instance Prime p => Haskell.Fractional (Zp p) where
    fromRational :: Rational -> Zp p
fromRational = [Char] -> Rational -> Zp p
forall a. HasCallStack => [Char] -> a
error [Char]
"`fromRational` is not implemented for `Zp p`"
    recip :: Zp p -> Zp p
recip        = Zp p -> Zp p
forall a. Field a => a -> a
finv
    / :: Zp p -> Zp p -> Zp p
(/)          = Zp p -> Zp p -> Zp p
forall a. Field a => a -> a -> a
(//)

instance Show (Zp p) where
    show :: Zp p -> [Char]
show (Zp Integer
a) = Integer -> [Char]
forall a. Show a => a -> [Char]
show Integer
a

instance ToJSON (Zp p) where
    toJSON :: Zp p -> Value
toJSON (Zp Integer
a) = Integer -> Value
forall a. ToJSON a => a -> Value
toJSON Integer
a

instance FromJSON (Zp p) where
    parseJSON :: Value -> Parser (Zp p)
parseJSON = (Integer -> Zp p) -> Parser Integer -> Parser (Zp p)
forall a b. (a -> b) -> Parser a -> Parser b
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap Integer -> Zp p
forall (p :: Natural). Integer -> Zp p
Zp (Parser Integer -> Parser (Zp p))
-> (Value -> Parser Integer) -> Value -> Parser (Zp p)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Value -> Parser Integer
forall a. FromJSON a => Value -> Parser a
parseJSON

instance KnownNat p => Binary (Zp p) where
    put :: Zp p -> Put
put (Zp Integer
x) = Integer -> Natural -> Put
forall {t}. Integral t => t -> Natural -> Put
go Integer
x (forall (n :: Natural). KnownNat n => Natural
wordCount @p)
      where
        go :: t -> Natural -> Put
go t
_ Natural
0      = () -> Put
forall a. a -> PutM a
forall (f :: Type -> Type) a. Applicative f => a -> f a
pure ()
        go t
n Natural
count =
            let (t
n', t
r) = t
n t -> t -> (t, t)
forall a. Integral a => a -> a -> (a, a)
`Haskell.divMod` t
256
            in Word8 -> Put
putWord8 (t -> Word8
forall a b. (Integral a, Num b) => a -> b
fromIntegral t
r) Put -> Put -> Put
forall a. Semigroup a => a -> a -> a
<> t -> Natural -> Put
go t
n' (Natural
count Natural -> Natural -> Natural
-! Natural
1)
    get :: Get (Zp p)
get = Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp (Integer -> Zp p) -> Get Integer -> Get (Zp p)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> Natural -> Get Integer
forall {a}.
(AdditiveMonoid a, MultiplicativeSemigroup a, Num a) =>
Natural -> Get a
go (forall (n :: Natural). KnownNat n => Natural
wordCount @p)
      where
        go :: Natural -> Get a
go Natural
0 = a -> Get a
forall a. a -> Get a
forall (f :: Type -> Type) a. Applicative f => a -> f a
pure a
forall a. AdditiveMonoid a => a
zero
        go Natural
n = (Word8 -> a -> a) -> Get Word8 -> Get a -> Get a
forall a b c. (a -> b -> c) -> Get a -> Get b -> Get c
forall (f :: Type -> Type) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Word8 -> a -> a
forall {a} {a}.
(AdditiveSemigroup a, Integral a, MultiplicativeSemigroup a,
 Num a) =>
a -> a -> a
combine Get Word8
getWord8 (Natural -> Get a
go (Natural -> Get a) -> Natural -> Get a
forall a b. (a -> b) -> a -> b
$ Natural
n Natural -> Natural -> Natural
-! Natural
1) Get a -> Get a -> Get a
forall a. Get a -> Get a -> Get a
forall (f :: Type -> Type) a. Alternative f => f a -> f a -> f a
<|> a -> Get a
forall a. a -> Get a
forall (f :: Type -> Type) a. Applicative f => a -> f a
pure a
forall a. AdditiveMonoid a => a
zero
        combine :: a -> a -> a
combine a
r a
d = a -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
r a -> a -> a
forall a. AdditiveSemigroup a => a -> a -> a
+ a
256 a -> a -> a
forall a. MultiplicativeSemigroup a => a -> a -> a
* a
d

wordCount :: forall p. KnownNat p => Natural
wordCount :: forall (n :: Natural). KnownNat n => Natural
wordCount = Ratio Natural -> Natural
forall b. Integral b => Ratio Natural -> b
forall a b. (RealFrac a, Integral b) => a -> b
ceiling (Ratio Natural -> Natural) -> Ratio Natural -> Natural
forall a b. (a -> b) -> a -> b
$ Natural -> Natural
forall a b. (Integral a, Integral b) => a -> b
log2ceiling (forall (n :: Natural). KnownNat n => Natural
value @p) Natural -> Natural -> Ratio Natural
forall a. Integral a => a -> a -> Ratio a
% (Natural
8 :: Natural)

instance KnownNat p => Arbitrary (Zp p) where
    arbitrary :: Gen (Zp p)
arbitrary = Integer -> Zp p
forall (p :: Natural). KnownNat p => Integer -> Zp p
toZp (Integer -> Zp p) -> Gen Integer -> Gen (Zp p)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> (Integer, Integer) -> Gen Integer
chooseInteger (Integer
0, Natural -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall (n :: Natural). KnownNat n => Natural
value @p) Integer -> Integer -> Integer
forall a. AdditiveGroup a => a -> a -> a
- Integer
1)

instance KnownNat p => Random (Zp p) where
    randomR :: forall g. RandomGen g => (Zp p, Zp p) -> g -> (Zp p, g)
randomR (Zp Integer
a, Zp Integer
b) g
g = (Integer -> Zp p
forall (p :: Natural). Integer -> Zp p
Zp Integer
r, g
g')
      where
        (Integer
r, g
g') = (Integer, Integer) -> g -> (Integer, g)
forall g. RandomGen g => (Integer, Integer) -> g -> (Integer, g)
forall a g. (Random a, RandomGen g) => (a, a) -> g -> (a, g)
randomR (Integer
a, Integer
b) g
g

    random :: forall g. RandomGen g => g -> (Zp p, g)
random g
g = (Integer -> Zp p
forall (p :: Natural). Integer -> Zp p
Zp Integer
r, g
g')
      where
        (Integer
r, g
g') = (Integer, Integer) -> g -> (Integer, g)
forall g. RandomGen g => (Integer, Integer) -> g -> (Integer, g)
forall a g. (Random a, RandomGen g) => (a, a) -> g -> (a, g)
randomR (Integer
0, Natural -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall (n :: Natural). KnownNat n => Natural
value @p) Integer -> Integer -> Integer
forall a. AdditiveGroup a => a -> a -> a
- Integer
1) g
g

-- | Exponentiation by an element of a finite field is well-defined (and lawful)
-- if and only if the base is a finite multiplicative group of a matching order.
--
-- Note that left distributivity is satisfied, meaning
-- @a ^ (m + n) = (a ^ m) * (a ^ n)@.
instance (MultiplicativeGroup a, Order a ~ p) => Exponent a (Zp p) where
    a
a ^ :: a -> Zp p -> a
^ Zp p
n = a
a a -> Natural -> a
forall a b. Exponent a b => a -> b -> a
^ Zp p -> Natural
forall (p :: Natural). Zp p -> Natural
fromZp Zp p
n

----------------------------- Field Extensions --------------------------------

class IrreduciblePoly f (e :: Symbol) | e -> f where
    irreduciblePoly :: Poly f

data Ext2 f (e :: Symbol) = Ext2 f f
    deriving (Ext2 f e -> Ext2 f e -> Bool
(Ext2 f e -> Ext2 f e -> Bool)
-> (Ext2 f e -> Ext2 f e -> Bool) -> Eq (Ext2 f e)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall f (e :: Symbol). Eq f => Ext2 f e -> Ext2 f e -> Bool
$c== :: forall f (e :: Symbol). Eq f => Ext2 f e -> Ext2 f e -> Bool
== :: Ext2 f e -> Ext2 f e -> Bool
$c/= :: forall f (e :: Symbol). Eq f => Ext2 f e -> Ext2 f e -> Bool
/= :: Ext2 f e -> Ext2 f e -> Bool
Eq, Int -> Ext2 f e -> ShowS
[Ext2 f e] -> ShowS
Ext2 f e -> [Char]
(Int -> Ext2 f e -> ShowS)
-> (Ext2 f e -> [Char]) -> ([Ext2 f e] -> ShowS) -> Show (Ext2 f e)
forall a.
(Int -> a -> ShowS) -> (a -> [Char]) -> ([a] -> ShowS) -> Show a
forall f (e :: Symbol). Show f => Int -> Ext2 f e -> ShowS
forall f (e :: Symbol). Show f => [Ext2 f e] -> ShowS
forall f (e :: Symbol). Show f => Ext2 f e -> [Char]
$cshowsPrec :: forall f (e :: Symbol). Show f => Int -> Ext2 f e -> ShowS
showsPrec :: Int -> Ext2 f e -> ShowS
$cshow :: forall f (e :: Symbol). Show f => Ext2 f e -> [Char]
show :: Ext2 f e -> [Char]
$cshowList :: forall f (e :: Symbol). Show f => [Ext2 f e] -> ShowS
showList :: [Ext2 f e] -> ShowS
Show, (forall x. Ext2 f e -> Rep (Ext2 f e) x)
-> (forall x. Rep (Ext2 f e) x -> Ext2 f e) -> Generic (Ext2 f e)
forall x. Rep (Ext2 f e) x -> Ext2 f e
forall x. Ext2 f e -> Rep (Ext2 f e) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall f (e :: Symbol) x. Rep (Ext2 f e) x -> Ext2 f e
forall f (e :: Symbol) x. Ext2 f e -> Rep (Ext2 f e) x
$cfrom :: forall f (e :: Symbol) x. Ext2 f e -> Rep (Ext2 f e) x
from :: forall x. Ext2 f e -> Rep (Ext2 f e) x
$cto :: forall f (e :: Symbol) x. Rep (Ext2 f e) x -> Ext2 f e
to :: forall x. Rep (Ext2 f e) x -> Ext2 f e
Generic)

instance Ord f => Ord (Ext2 f e) where
    Ext2 f
a f
b <= :: Ext2 f e -> Ext2 f e -> Bool
<= Ext2 f
c f
d = [f
Item [f]
b, f
Item [f]
a] [f] -> [f] -> Bool
forall a. Ord a => a -> a -> Bool
<= ([f
Item [f]
d, f
Item [f]
c] :: [f])

instance (KnownNat (Order (Ext2 f e)), KnownNat (NumberOfBits (Ext2 f e))) => Finite (Ext2 f e) where
    type Order (Ext2 f e) = Order f ^ 2

instance {-# OVERLAPPING #-} FromConstant (Ext2 f e) (Ext2 f e)

instance Field f => AdditiveSemigroup (Ext2 f e) where
    Ext2 f
a f
b + :: Ext2 f e -> Ext2 f e -> Ext2 f e
+ Ext2 f
c f
d = f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 (f
a f -> f -> f
forall a. AdditiveSemigroup a => a -> a -> a
+ f
c) (f
b f -> f -> f
forall a. AdditiveSemigroup a => a -> a -> a
+ f
d)

instance Scale c f => Scale c (Ext2 f e) where
    scale :: c -> Ext2 f e -> Ext2 f e
scale c
c (Ext2 f
a f
b) = f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 (c -> f -> f
forall b a. Scale b a => b -> a -> a
scale c
c f
a) (c -> f -> f
forall b a. Scale b a => b -> a -> a
scale c
c f
b)

instance Field f => AdditiveMonoid (Ext2 f e) where
    zero :: Ext2 f e
zero = f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 f
forall a. AdditiveMonoid a => a
zero f
forall a. AdditiveMonoid a => a
zero

instance Field f => AdditiveGroup (Ext2 f e) where
    negate :: Ext2 f e -> Ext2 f e
negate (Ext2 f
a f
b) = f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 (f -> f
forall a. AdditiveGroup a => a -> a
negate f
a) (f -> f
forall a. AdditiveGroup a => a -> a
negate f
b)
    Ext2 f
a f
b - :: Ext2 f e -> Ext2 f e -> Ext2 f e
- Ext2 f
c f
d = f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 (f
a f -> f -> f
forall a. AdditiveGroup a => a -> a -> a
- f
c) (f
b f -> f -> f
forall a. AdditiveGroup a => a -> a -> a
- f
d)

instance {-# OVERLAPPING #-} (Field f, Eq f, IrreduciblePoly f e) => Scale (Ext2 f e) (Ext2 f e)

instance (Field f, Eq f, IrreduciblePoly f e) => MultiplicativeSemigroup (Ext2 f e) where
    Ext2 f
a f
b * :: Ext2 f e -> Ext2 f e -> Ext2 f e
* Ext2 f
c f
d = Poly f -> Ext2 f e
forall a b. FromConstant a b => a -> b
fromConstant (Vector f -> Poly f
forall c. (Ring c, Eq c) => Vector c -> Poly c
toPoly [f
Item (Vector f)
a, f
Item (Vector f)
b] Poly f -> Poly f -> Poly f
forall a. MultiplicativeSemigroup a => a -> a -> a
* Vector f -> Poly f
forall c. (Ring c, Eq c) => Vector c -> Poly c
toPoly [f
Item (Vector f)
c, f
Item (Vector f)
d])

instance MultiplicativeMonoid (Ext2 f e) => Exponent (Ext2 f e) Natural where
    ^ :: Ext2 f e -> Natural -> Ext2 f e
(^) = Ext2 f e -> Natural -> Ext2 f e
forall a. MultiplicativeMonoid a => a -> Natural -> a
natPow

instance (Field f, Eq f, IrreduciblePoly f e) => MultiplicativeMonoid (Ext2 f e) where
    one :: Ext2 f e
one = f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 f
forall a. MultiplicativeMonoid a => a
one f
forall a. AdditiveMonoid a => a
zero

instance Field (Ext2 f e) => Exponent (Ext2 f e) Integer where
    ^ :: Ext2 f e -> Integer -> Ext2 f e
(^) = Ext2 f e -> Integer -> Ext2 f e
forall a. Field a => a -> Integer -> a
intPowF

instance (Field f, Eq f, IrreduciblePoly f e) => Field (Ext2 f e) where
    finv :: Ext2 f e -> Ext2 f e
finv (Ext2 f
a f
b) =
        let (Poly f
g, Poly f
s) = Poly f -> Poly f -> (Poly f, Poly f)
forall c. (Field c, Eq c) => Poly c -> Poly c -> (Poly c, Poly c)
eea (Vector f -> Poly f
forall c. (Ring c, Eq c) => Vector c -> Poly c
toPoly [f
Item (Vector f)
a, f
Item (Vector f)
b]) (forall f (e :: Symbol). IrreduciblePoly f e => Poly f
irreduciblePoly @f @e)
        in case Poly f -> Vector f
forall c. Poly c -> Vector c
fromPoly (Poly f -> Vector f) -> Poly f -> Vector f
forall a b. (a -> b) -> a -> b
$ f -> Natural -> Poly f -> Poly f
forall c. Ring c => c -> Natural -> Poly c -> Poly c
scaleP (f
forall a. MultiplicativeMonoid a => a
one f -> f -> f
forall a. Field a => a -> a -> a
// Poly f -> f
forall c. Poly c -> c
lt Poly f
g) Natural
0 Poly f
s of
            []  -> f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 f
forall a. AdditiveMonoid a => a
zero f
forall a. AdditiveMonoid a => a
zero
            [Item (Vector f)
x] -> f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 f
Item (Vector f)
x f
forall a. AdditiveMonoid a => a
zero
            Vector f
v   -> f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 (Vector f
v Vector f -> Int -> f
forall a. Vector a -> Int -> a
V.! Int
0) (Vector f
v Vector f -> Int -> f
forall a. Vector a -> Int -> a
V.! Int
1)

    rootOfUnity :: Natural -> Maybe (Ext2 f e)
rootOfUnity Natural
n = (\f
r -> f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 f
r f
forall a. AdditiveMonoid a => a
zero) (f -> Ext2 f e) -> Maybe f -> Maybe (Ext2 f e)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> Natural -> Maybe f
forall a. Field a => Natural -> Maybe a
rootOfUnity Natural
n

instance (FromConstant f f', Field f') => FromConstant f (Ext2 f' e) where
    fromConstant :: f -> Ext2 f' e
fromConstant f
e = f' -> f' -> Ext2 f' e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 (f -> f'
forall a b. FromConstant a b => a -> b
fromConstant f
e) f'
forall a. AdditiveMonoid a => a
zero

instance {-# OVERLAPPING #-} (Field f, Eq f, IrreduciblePoly f e) => FromConstant (Poly f) (Ext2 f e) where
    fromConstant :: Poly f -> Ext2 f e
fromConstant Poly f
p = case Poly f -> Vector f
forall c. Poly c -> Vector c
fromPoly (Poly f -> Vector f)
-> ((Poly f, Poly f) -> Poly f) -> (Poly f, Poly f) -> Vector f
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Poly f, Poly f) -> Poly f
forall a b. (a, b) -> b
snd ((Poly f, Poly f) -> Vector f) -> (Poly f, Poly f) -> Vector f
forall a b. (a -> b) -> a -> b
$ Poly f -> Poly f -> (Poly f, Poly f)
forall c. (Field c, Eq c) => Poly c -> Poly c -> (Poly c, Poly c)
qr Poly f
p (forall f (e :: Symbol). IrreduciblePoly f e => Poly f
irreduciblePoly @f @e) of
      []  -> Ext2 f e
forall a. AdditiveMonoid a => a
zero
      [Item (Vector f)
x] -> f -> Ext2 f e
forall a b. FromConstant a b => a -> b
fromConstant f
Item (Vector f)
x
      Vector f
v   -> f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 (Vector f
v Vector f -> Int -> f
forall a. Vector a -> Int -> a
V.! Int
0) (Vector f
v Vector f -> Int -> f
forall a. Vector a -> Int -> a
V.! Int
1)

instance (Field f, Eq f, IrreduciblePoly f e) => Semiring (Ext2 f e)

instance (Field f, Eq f, IrreduciblePoly f e) => Ring (Ext2 f e)

instance Binary f => Binary (Ext2 f e) where
    put :: Ext2 f e -> Put
put (Ext2 f
a f
b) = f -> Put
forall t. Binary t => t -> Put
put f
a Put -> Put -> Put
forall a. Semigroup a => a -> a -> a
<> f -> Put
forall t. Binary t => t -> Put
put f
b
    get :: Get (Ext2 f e)
get = f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 (f -> f -> Ext2 f e) -> Get f -> Get (f -> Ext2 f e)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> Get f
forall t. Binary t => Get t
get Get (f -> Ext2 f e) -> Get f -> Get (Ext2 f e)
forall a b. Get (a -> b) -> Get a -> Get b
forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> Get f
forall t. Binary t => Get t
get

instance (Field f, Eq f, IrreduciblePoly f e, Arbitrary f) => Arbitrary (Ext2 f e) where
    arbitrary :: Gen (Ext2 f e)
arbitrary = f -> f -> Ext2 f e
forall f (e :: Symbol). f -> f -> Ext2 f e
Ext2 (f -> f -> Ext2 f e) -> Gen f -> Gen (f -> Ext2 f e)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> Gen f
forall a. Arbitrary a => Gen a
arbitrary Gen (f -> Ext2 f e) -> Gen f -> Gen (Ext2 f e)
forall a b. Gen (a -> b) -> Gen a -> Gen b
forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> Gen f
forall a. Arbitrary a => Gen a
arbitrary

data Ext3 f (e :: Symbol) = Ext3 f f f
    deriving (Ext3 f e -> Ext3 f e -> Bool
(Ext3 f e -> Ext3 f e -> Bool)
-> (Ext3 f e -> Ext3 f e -> Bool) -> Eq (Ext3 f e)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall f (e :: Symbol). Eq f => Ext3 f e -> Ext3 f e -> Bool
$c== :: forall f (e :: Symbol). Eq f => Ext3 f e -> Ext3 f e -> Bool
== :: Ext3 f e -> Ext3 f e -> Bool
$c/= :: forall f (e :: Symbol). Eq f => Ext3 f e -> Ext3 f e -> Bool
/= :: Ext3 f e -> Ext3 f e -> Bool
Eq, Int -> Ext3 f e -> ShowS
[Ext3 f e] -> ShowS
Ext3 f e -> [Char]
(Int -> Ext3 f e -> ShowS)
-> (Ext3 f e -> [Char]) -> ([Ext3 f e] -> ShowS) -> Show (Ext3 f e)
forall a.
(Int -> a -> ShowS) -> (a -> [Char]) -> ([a] -> ShowS) -> Show a
forall f (e :: Symbol). Show f => Int -> Ext3 f e -> ShowS
forall f (e :: Symbol). Show f => [Ext3 f e] -> ShowS
forall f (e :: Symbol). Show f => Ext3 f e -> [Char]
$cshowsPrec :: forall f (e :: Symbol). Show f => Int -> Ext3 f e -> ShowS
showsPrec :: Int -> Ext3 f e -> ShowS
$cshow :: forall f (e :: Symbol). Show f => Ext3 f e -> [Char]
show :: Ext3 f e -> [Char]
$cshowList :: forall f (e :: Symbol). Show f => [Ext3 f e] -> ShowS
showList :: [Ext3 f e] -> ShowS
Show, (forall x. Ext3 f e -> Rep (Ext3 f e) x)
-> (forall x. Rep (Ext3 f e) x -> Ext3 f e) -> Generic (Ext3 f e)
forall x. Rep (Ext3 f e) x -> Ext3 f e
forall x. Ext3 f e -> Rep (Ext3 f e) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall f (e :: Symbol) x. Rep (Ext3 f e) x -> Ext3 f e
forall f (e :: Symbol) x. Ext3 f e -> Rep (Ext3 f e) x
$cfrom :: forall f (e :: Symbol) x. Ext3 f e -> Rep (Ext3 f e) x
from :: forall x. Ext3 f e -> Rep (Ext3 f e) x
$cto :: forall f (e :: Symbol) x. Rep (Ext3 f e) x -> Ext3 f e
to :: forall x. Rep (Ext3 f e) x -> Ext3 f e
Generic)

instance Ord f => Ord (Ext3 f e) where
    Ext3 f
a f
b f
c <= :: Ext3 f e -> Ext3 f e -> Bool
<= Ext3 f
d f
e f
f = [f
Item [f]
c, f
Item [f]
b, f
Item [f]
a] [f] -> [f] -> Bool
forall a. Ord a => a -> a -> Bool
<= ([f
Item [f]
f, f
Item [f]
e, f
Item [f]
d] :: [f])

instance (KnownNat (Order (Ext3 f e)), KnownNat (NumberOfBits (Ext3 f e))) => Finite (Ext3 f e) where
    type Order (Ext3 f e) = Order f ^ 3

instance {-# OVERLAPPING #-} FromConstant (Ext3 f e) (Ext3 f e)

instance Field f => AdditiveSemigroup (Ext3 f e) where
    Ext3 f
a f
b f
c + :: Ext3 f e -> Ext3 f e -> Ext3 f e
+ Ext3 f
d f
e f
f = f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 (f
a f -> f -> f
forall a. AdditiveSemigroup a => a -> a -> a
+ f
d) (f
b f -> f -> f
forall a. AdditiveSemigroup a => a -> a -> a
+ f
e) (f
c f -> f -> f
forall a. AdditiveSemigroup a => a -> a -> a
+ f
f)

instance Scale c f => Scale c (Ext3 f e) where
    scale :: c -> Ext3 f e -> Ext3 f e
scale c
c (Ext3 f
d f
e f
f) = f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 (c -> f -> f
forall b a. Scale b a => b -> a -> a
scale c
c f
d) (c -> f -> f
forall b a. Scale b a => b -> a -> a
scale c
c f
e) (c -> f -> f
forall b a. Scale b a => b -> a -> a
scale c
c f
f)

instance Field f => AdditiveMonoid (Ext3 f e) where
    zero :: Ext3 f e
zero = f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 f
forall a. AdditiveMonoid a => a
zero f
forall a. AdditiveMonoid a => a
zero f
forall a. AdditiveMonoid a => a
zero

instance Field f => AdditiveGroup (Ext3 f e) where
    negate :: Ext3 f e -> Ext3 f e
negate (Ext3 f
a f
b f
c) = f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 (f -> f
forall a. AdditiveGroup a => a -> a
negate f
a) (f -> f
forall a. AdditiveGroup a => a -> a
negate f
b) (f -> f
forall a. AdditiveGroup a => a -> a
negate f
c)
    Ext3 f
a f
b f
c - :: Ext3 f e -> Ext3 f e -> Ext3 f e
- Ext3 f
d f
e f
f = f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 (f
a f -> f -> f
forall a. AdditiveGroup a => a -> a -> a
- f
d) (f
b f -> f -> f
forall a. AdditiveGroup a => a -> a -> a
- f
e) (f
c f -> f -> f
forall a. AdditiveGroup a => a -> a -> a
- f
f)

instance {-# OVERLAPPING #-} (Field f, Eq f, IrreduciblePoly f e) => Scale (Ext3 f e) (Ext3 f e)

instance (Field f, Eq f, IrreduciblePoly f e) => MultiplicativeSemigroup (Ext3 f e) where
    Ext3 f
a f
b f
c * :: Ext3 f e -> Ext3 f e -> Ext3 f e
* Ext3 f
d f
e f
f = Poly f -> Ext3 f e
forall a b. FromConstant a b => a -> b
fromConstant (Vector f -> Poly f
forall c. (Ring c, Eq c) => Vector c -> Poly c
toPoly [f
Item (Vector f)
a, f
Item (Vector f)
b, f
Item (Vector f)
c] Poly f -> Poly f -> Poly f
forall a. MultiplicativeSemigroup a => a -> a -> a
* Vector f -> Poly f
forall c. (Ring c, Eq c) => Vector c -> Poly c
toPoly [f
Item (Vector f)
d, f
Item (Vector f)
e, f
Item (Vector f)
f])

instance MultiplicativeMonoid (Ext3 f e) => Exponent (Ext3 f e) Natural where
    ^ :: Ext3 f e -> Natural -> Ext3 f e
(^) = Ext3 f e -> Natural -> Ext3 f e
forall a. MultiplicativeMonoid a => a -> Natural -> a
natPow

instance (Field f, Eq f, IrreduciblePoly f e) => MultiplicativeMonoid (Ext3 f e) where
    one :: Ext3 f e
one = f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 f
forall a. MultiplicativeMonoid a => a
one f
forall a. AdditiveMonoid a => a
zero f
forall a. AdditiveMonoid a => a
zero

instance Field (Ext3 f e) => Exponent (Ext3 f e) Integer where
    ^ :: Ext3 f e -> Integer -> Ext3 f e
(^) = Ext3 f e -> Integer -> Ext3 f e
forall a. Field a => a -> Integer -> a
intPowF

instance (Field f, Eq f, IrreduciblePoly f e) => Field (Ext3 f e) where
    finv :: Ext3 f e -> Ext3 f e
finv (Ext3 f
a f
b f
c) =
        let (Poly f
g, Poly f
s) = Poly f -> Poly f -> (Poly f, Poly f)
forall c. (Field c, Eq c) => Poly c -> Poly c -> (Poly c, Poly c)
eea (Vector f -> Poly f
forall c. (Ring c, Eq c) => Vector c -> Poly c
toPoly [f
Item (Vector f)
a, f
Item (Vector f)
b, f
Item (Vector f)
c]) (forall f (e :: Symbol). IrreduciblePoly f e => Poly f
irreduciblePoly @f @e)
        in case Poly f -> Vector f
forall c. Poly c -> Vector c
fromPoly (Poly f -> Vector f) -> Poly f -> Vector f
forall a b. (a -> b) -> a -> b
$ f -> Natural -> Poly f -> Poly f
forall c. Ring c => c -> Natural -> Poly c -> Poly c
scaleP (f
forall a. MultiplicativeMonoid a => a
one f -> f -> f
forall a. Field a => a -> a -> a
// Poly f -> f
forall c. Poly c -> c
lt Poly f
g) Natural
0 Poly f
s of
            []     -> f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 f
forall a. AdditiveMonoid a => a
zero f
forall a. AdditiveMonoid a => a
zero f
forall a. AdditiveMonoid a => a
zero
            [Item (Vector f)
x]    -> f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 f
Item (Vector f)
x f
forall a. AdditiveMonoid a => a
zero f
forall a. AdditiveMonoid a => a
zero
            [Item (Vector f)
x, Item (Vector f)
y] -> f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 f
Item (Vector f)
x f
Item (Vector f)
y f
forall a. AdditiveMonoid a => a
zero
            Vector f
v      -> f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 (Vector f
v Vector f -> Int -> f
forall a. Vector a -> Int -> a
V.! Int
0) (Vector f
v Vector f -> Int -> f
forall a. Vector a -> Int -> a
V.! Int
1) (Vector f
v Vector f -> Int -> f
forall a. Vector a -> Int -> a
V.! Int
2)

    rootOfUnity :: Natural -> Maybe (Ext3 f e)
rootOfUnity Natural
n = (\f
r -> f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 f
r f
forall a. AdditiveMonoid a => a
zero f
forall a. AdditiveMonoid a => a
zero) (f -> Ext3 f e) -> Maybe f -> Maybe (Ext3 f e)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> Natural -> Maybe f
forall a. Field a => Natural -> Maybe a
rootOfUnity Natural
n

instance (FromConstant f f', Field f') => FromConstant f (Ext3 f' ip) where
    fromConstant :: f -> Ext3 f' ip
fromConstant f
e = f' -> f' -> f' -> Ext3 f' ip
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 (f -> f'
forall a b. FromConstant a b => a -> b
fromConstant f
e) f'
forall a. AdditiveMonoid a => a
zero f'
forall a. AdditiveMonoid a => a
zero

instance {-# OVERLAPPING #-} (Field f, Eq f, IrreduciblePoly f e) => FromConstant (Poly f) (Ext3 f e) where
    fromConstant :: Poly f -> Ext3 f e
fromConstant Poly f
p = case Poly f -> Vector f
forall c. Poly c -> Vector c
fromPoly (Poly f -> Vector f)
-> ((Poly f, Poly f) -> Poly f) -> (Poly f, Poly f) -> Vector f
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Poly f, Poly f) -> Poly f
forall a b. (a, b) -> b
snd ((Poly f, Poly f) -> Vector f) -> (Poly f, Poly f) -> Vector f
forall a b. (a -> b) -> a -> b
$ Poly f -> Poly f -> (Poly f, Poly f)
forall c. (Field c, Eq c) => Poly c -> Poly c -> (Poly c, Poly c)
qr Poly f
p (forall f (e :: Symbol). IrreduciblePoly f e => Poly f
irreduciblePoly @f @e) of
      []     -> Ext3 f e
forall a. AdditiveMonoid a => a
zero
      [Item (Vector f)
x]    -> f -> Ext3 f e
forall a b. FromConstant a b => a -> b
fromConstant f
Item (Vector f)
x
      [Item (Vector f)
x, Item (Vector f)
y] -> f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 f
Item (Vector f)
x f
Item (Vector f)
y f
forall a. AdditiveMonoid a => a
zero
      Vector f
v      -> f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 (Vector f
v Vector f -> Int -> f
forall a. Vector a -> Int -> a
V.! Int
0) (Vector f
v Vector f -> Int -> f
forall a. Vector a -> Int -> a
V.! Int
1) (Vector f
v Vector f -> Int -> f
forall a. Vector a -> Int -> a
V.! Int
2)

instance (Field f, Eq f, IrreduciblePoly f e) => Semiring (Ext3 f e)

instance (Field f, Eq f, IrreduciblePoly f e) => Ring (Ext3 f e)

instance Binary f => Binary (Ext3 f e) where
    put :: Ext3 f e -> Put
put (Ext3 f
a f
b f
c) = f -> Put
forall t. Binary t => t -> Put
put f
a Put -> Put -> Put
forall a. Semigroup a => a -> a -> a
<> f -> Put
forall t. Binary t => t -> Put
put f
b Put -> Put -> Put
forall a. Semigroup a => a -> a -> a
<> f -> Put
forall t. Binary t => t -> Put
put f
c
    get :: Get (Ext3 f e)
get = f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 (f -> f -> f -> Ext3 f e) -> Get f -> Get (f -> f -> Ext3 f e)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> Get f
forall t. Binary t => Get t
get Get (f -> f -> Ext3 f e) -> Get f -> Get (f -> Ext3 f e)
forall a b. Get (a -> b) -> Get a -> Get b
forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> Get f
forall t. Binary t => Get t
get Get (f -> Ext3 f e) -> Get f -> Get (Ext3 f e)
forall a b. Get (a -> b) -> Get a -> Get b
forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> Get f
forall t. Binary t => Get t
get

instance (Field f, Eq f, IrreduciblePoly f e, Arbitrary f) => Arbitrary (Ext3 f e) where
    arbitrary :: Gen (Ext3 f e)
arbitrary = f -> f -> f -> Ext3 f e
forall f (e :: Symbol). f -> f -> f -> Ext3 f e
Ext3 (f -> f -> f -> Ext3 f e) -> Gen f -> Gen (f -> f -> Ext3 f e)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
<$> Gen f
forall a. Arbitrary a => Gen a
arbitrary Gen (f -> f -> Ext3 f e) -> Gen f -> Gen (f -> Ext3 f e)
forall a b. Gen (a -> b) -> Gen a -> Gen b
forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> Gen f
forall a. Arbitrary a => Gen a
arbitrary Gen (f -> Ext3 f e) -> Gen f -> Gen (Ext3 f e)
forall a b. Gen (a -> b) -> Gen a -> Gen b
forall (f :: Type -> Type) a b.
Applicative f =>
f (a -> b) -> f a -> f b
<*> Gen f
forall a. Arbitrary a => Gen a
arbitrary