-- | Small Galois fields via a precomputed table of Conway polynomials.
--
-- This covers:
--
-- * all fields with order <= 2^30
--
-- * all fields with characteristic < 2^16 and order < 2^64 (?)
--
-- * higher powers for very small prime characteristic
--
-- * some more
--
-- To look up Conway polynomials, see the module "Math.FiniteField.Conway".
--

{-# LANGUAGE BangPatterns, DataKinds, KindSignatures, GADTs, TypeFamilies #-}
{-# LANGUAGE ScopedTypeVariables, ExistentialQuantification, StandaloneDeriving #-}

module Math.FiniteField.GaloisField.Small
  ( -- * Witness for the existence of the field
    WitnessGF(..)
  , SomeWitnessGF(..)
  , mkGaloisField
  , unsafeGaloisField
  , constructGaloisField
    -- * Field elements
  , GF
  )
  where

--------------------------------------------------------------------------------

import Prelude hiding (div)

import Data.Bits
import Data.Int
import Data.Word
import Data.List

import GHC.TypeNats (Nat)

import Data.Vector.Unboxed (Vector)
import qualified Data.Vector.Unboxed as Vec

import System.Random ( RandomGen , randomR )

import Math.FiniteField.Class 
import Math.FiniteField.TypeLevel
import Math.FiniteField.TypeLevel.Singleton
import Math.FiniteField.Conway
import Math.FiniteField.Conway.Internal
import Math.FiniteField.Primes
import Math.FiniteField.Misc

import qualified Math.FiniteField.PrimeField.Small.Raw       as Raw
import qualified Math.FiniteField.GaloisField.Small.Internal as Quo

--------------------------------------------------------------------------------  
-- * Witness for the existence of GF(q^m)

-- | We need either a Conway polynomial, or in the @m=1@ case, a proof that @p@ is prime
data WitnessGF (p :: Nat) (m :: Nat) where
  WitnessFp :: IsSmallPrime p   -> WitnessGF p 1
  WitnessFq :: ConwayPoly   p m -> WitnessGF p m

deriving instance Show (WitnessGF p m)

gfParams :: WitnessGF p m -> (Word64,Int)
gfParams :: forall (p :: Nat) (m :: Nat). WitnessGF p m -> (Word64, Int)
gfParams WitnessGF p m
w = case WitnessGF p m
w of
  WitnessFp IsSmallPrime p
p -> (forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
p, Int
1)
  WitnessFq ConwayPoly p m
c -> forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
c

data SomeWitnessGF 
  = forall p m. SomeWitnessGF (WitnessGF p m)

deriving instance Show SomeWitnessGF

-- | Usage:
--
-- > mkGaloisField p m
-- 
-- to construct the field with @q = p^m@ elements
--
-- Implementation note: For @m=1@ we may do a primality test, which is very 
-- slow at the moment. You can use 'unsafeGaloisField' below to avoid this.
--
mkGaloisField :: Int -> Int -> Maybe SomeWitnessGF
mkGaloisField :: Int -> Int -> Maybe SomeWitnessGF
mkGaloisField Int
p Int
m = case (Int64 -> SomeSNat64
someSNat64 (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
p), Int64 -> SomeSNat64
someSNat64 (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
m)) of 
  (SomeSNat64 SNat64 n
sp, SomeSNat64 SNat64 n
sm) -> forall (p :: Nat) (m :: Nat). WitnessGF p m -> SomeWitnessGF
SomeWitnessGF forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> Maybe (WitnessGF p m)
constructGaloisField SNat64 n
sp SNat64 n
sm)

-- | In the case of @m=1@ you are responsible for guaranteeing that @p@ is a prime
-- (for @m>1@ we have to look up a Conway polynomial anyway).
--
unsafeGaloisField :: Int -> Int -> SomeWitnessGF
unsafeGaloisField :: Int -> Int -> SomeWitnessGF
unsafeGaloisField Int
p Int
m = case Int
m of
  Int
1  -> case Int64 -> SomeSNat64
someSNat64 (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
p) of 
          SomeSNat64 SNat64 n
sp -> (forall (p :: Nat) (m :: Nat). WitnessGF p m -> SomeWitnessGF
SomeWitnessGF forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (p :: Nat). IsSmallPrime p -> WitnessGF p 1
WitnessFp) (forall (n :: Nat). SNat64 n -> IsSmallPrime n
believeMeItsASmallPrime SNat64 n
sp)
  Int
_  -> case Int -> Int -> Maybe SomeConwayPoly
lookupSomeConwayPoly Int
p Int
m of 
          Maybe SomeConwayPoly
Nothing -> forall a. HasCallStack => String -> a
error forall a b. (a -> b) -> a -> b
$ String
"unsafeGaloisField: cannot find Conway polynomial for GF(" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Int
p forall a. [a] -> [a] -> [a]
++ String
"^" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Int
m forall a. [a] -> [a] -> [a]
++ String
")"
          Just (SomeConwayPoly ConwayPoly p m
cw) -> forall (p :: Nat) (m :: Nat). WitnessGF p m -> SomeWitnessGF
SomeWitnessGF (forall (p :: Nat) (m :: Nat). ConwayPoly p m -> WitnessGF p m
WitnessFq ConwayPoly p m
cw)

-- workaround hack for GHC typechecker...
-- for some reason, "Maybe (WitnessGF p m)" is not valid otuput for "snat64IfOneThenElse"
data MaybeWitnessGF p m 
  = JustWitness (WitnessGF p m)
  | NoWitness

constructGaloisField :: forall p m. SNat64 p -> SNat64 m -> Maybe (WitnessGF p m)
constructGaloisField :: forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> Maybe (WitnessGF p m)
constructGaloisField SNat64 p
sp SNat64 m
sm = case forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> MaybeWitnessGF p m
constructGaloisField' SNat64 p
sp SNat64 m
sm of
  MaybeWitnessGF p m
NoWitness     -> forall a. Maybe a
Nothing
  JustWitness WitnessGF p m
w -> forall a. a -> Maybe a
Just WitnessGF p m
w

constructGaloisField' :: forall p m. SNat64 p -> SNat64 m -> MaybeWitnessGF p m
constructGaloisField' :: forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> MaybeWitnessGF p m
constructGaloisField' SNat64 p
sp SNat64 m
snatm = forall (n :: Nat) (f :: Nat -> *).
SNat64 n -> (SNat64 1 -> f 1) -> (SNat64 n -> f n) -> f n
snat64IfOneThenElse SNat64 m
snatm SNat64 1 -> MaybeWitnessGF p 1
primeBranch SNat64 m -> MaybeWitnessGF p m
powerBranch where

  primeBranch :: SNat64 1 -> MaybeWitnessGF p 1
  primeBranch :: SNat64 1 -> MaybeWitnessGF p 1
primeBranch SNat64 1
s1 = case forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> Maybe (ConwayPoly p m)
lookupConwayPoly SNat64 p
sp SNat64 1
s1 of
    Just ConwayPoly p 1
_  -> forall (p :: Nat) (m :: Nat). WitnessGF p m -> MaybeWitnessGF p m
JustWitness (forall (p :: Nat). IsSmallPrime p -> WitnessGF p 1
WitnessFp forall a b. (a -> b) -> a -> b
$ forall (n :: Nat). SNat64 n -> IsSmallPrime n
believeMeItsASmallPrime SNat64 p
sp)
    Maybe (ConwayPoly p 1)
Nothing -> case forall (n :: Nat). SNat64 n -> Maybe (IsSmallPrime n)
isSmallPrime SNat64 p
sp of
      Just IsSmallPrime p
w  -> forall (p :: Nat) (m :: Nat). WitnessGF p m -> MaybeWitnessGF p m
JustWitness (forall (p :: Nat). IsSmallPrime p -> WitnessGF p 1
WitnessFp IsSmallPrime p
w)
      Maybe (IsSmallPrime p)
Nothing -> forall (p :: Nat) (m :: Nat). MaybeWitnessGF p m
NoWitness

  powerBranch :: SNat64 m -> MaybeWitnessGF p m
  powerBranch :: SNat64 m -> MaybeWitnessGF p m
powerBranch SNat64 m
sm = case forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> Maybe (ConwayPoly p m)
lookupConwayPoly SNat64 p
sp SNat64 m
sm of 
    Maybe (ConwayPoly p m)
Nothing -> forall (p :: Nat) (m :: Nat). MaybeWitnessGF p m
NoWitness
    Just ConwayPoly p m
cw -> forall (p :: Nat) (m :: Nat). WitnessGF p m -> MaybeWitnessGF p m
JustWitness (forall (p :: Nat) (m :: Nat). ConwayPoly p m -> WitnessGF p m
WitnessFq ConwayPoly p m
cw)

-- instance FieldWitness (WitnessGF p m) where
--   type FieldElem    (WitnessGF p m) = GF p m
--   type WitnessPrime (WitnessGF p m) = p
--   type WitnessDim   (WitnessGF p m) = m

--------------------------------------------------------------------------------  

-- | An element of the Galois field of order @q = p^m@
data GF (p :: Nat) (m :: Nat) where
  Fp :: {-# UNPACK #-} !(IsSmallPrime p  ) -> {-# UNPACK #-} !Word64          -> GF p 1
  Fq :: {-# UNPACK #-} !(ConwayPoly   p m) ->                !(Vector Word32) -> GF p m

-- | An alias for @GF p m@, that is, the elements of the Galois field of order @q = p^m@
type Fq p m = GF p m

gfWitness :: GF p m -> WitnessGF p m
gfWitness :: forall (p :: Nat) (m :: Nat). GF p m -> WitnessGF p m
gfWitness GF p m
element = case GF p m
element of
  Fp IsSmallPrime p
p Word64
_ -> forall (p :: Nat). IsSmallPrime p -> WitnessGF p 1
WitnessFp IsSmallPrime p
p
  Fq ConwayPoly p m
c Vector Word32
_ -> forall (p :: Nat) (m :: Nat). ConwayPoly p m -> WitnessGF p m
WitnessFq ConwayPoly p m
c

-- | An element of the prime field
fp :: WitnessGF p m -> Word64 -> GF p m
fp :: forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp WitnessGF p m
witness Word64
x = 
  case WitnessGF p m
witness of
    WitnessFp IsSmallPrime p
p -> forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
fp1 IsSmallPrime p
p Word64
x 
    WitnessFq ConwayPoly p m
c -> forall (p :: Nat) (m :: Nat). ConwayPoly p m -> Word64 -> GF p m
fpM ConwayPoly p m
c Word64
x

  where
    fpM :: ConwayPoly p m -> Word64 -> GF p m
    fpM :: forall (p :: Nat) (m :: Nat). ConwayPoly p m -> Word64 -> GF p m
fpM ConwayPoly p m
conway Word64
x = forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
conway (forall a. Unbox a => Int -> [a] -> Vector a
Vec.fromListN Int
m (Word32
y forall a. a -> [a] -> [a]
: forall a. Int -> a -> [a]
replicate (Int
mforall a. Num a => a -> a -> a
-Int
1) Word32
0)) where
      (Word64
p,Int
m) = forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
conway
      y :: Word32
y = if Word64
x forall a. Ord a => a -> a -> Bool
>= Word64
0 Bool -> Bool -> Bool
&& Word64
x forall a. Ord a => a -> a -> Bool
< Word64
p then forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
x else forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a. Integral a => a -> a -> a
mod Word64
x Word64
p) :: Word32
    
    fp1 :: IsSmallPrime p -> Word64 -> GF p 1
    fp1 :: forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
fp1 IsSmallPrime p
prime Word64
x = forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
prime Word64
y where
      p :: Word64
p = forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
prime 
      y :: Word64
y = if Word64
x forall a. Ord a => a -> a -> Bool
>= Word64
0 Bool -> Bool -> Bool
&& Word64
x forall a. Ord a => a -> a -> Bool
< Word64
p then Word64
x else forall a. Integral a => a -> a -> a
mod Word64
x Word64
p

fpIsZero :: GF p m -> Bool
fpIsZero :: forall (p :: Nat) (m :: Nat). GF p m -> Bool
fpIsZero (Fp IsSmallPrime p
_ Word64
x) = Word64
x forall a. Eq a => a -> a -> Bool
== Word64
0
fpIsZero (Fq ConwayPoly p m
_ Vector Word32
v) = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (forall a. Eq a => a -> a -> Bool
==Word32
0) (forall a. Unbox a => Vector a -> [a]
Vec.toList Vector Word32
v)

fpIsOne :: GF p m -> Bool
fpIsOne :: forall (p :: Nat) (m :: Nat). GF p m -> Bool
fpIsOne (Fp IsSmallPrime p
_ Word64
x) = Word64
x forall a. Eq a => a -> a -> Bool
== Word64
1
fpIsOne (Fq ConwayPoly p m
_ Vector Word32
v) = case forall a. Unbox a => Vector a -> [a]
Vec.toList Vector Word32
v of { (Word32
x:[Word32]
xs) -> Word32
xforall a. Eq a => a -> a -> Bool
==Word32
1 Bool -> Bool -> Bool
&& forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (forall a. Eq a => a -> a -> Bool
==Word32
0) [Word32]
xs }

randomFq :: RandomGen gen => WitnessGF p m -> gen -> (GF p m, gen) 
randomFq :: forall gen (p :: Nat) (m :: Nat).
RandomGen gen =>
WitnessGF p m -> gen -> (GF p m, gen)
randomFq WitnessGF p m
witness gen
gen = case WitnessGF p m
witness of
  WitnessFp IsSmallPrime p
p -> 
    let !q :: Word64
q = forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
p 
    in  case forall a g. (Random a, RandomGen g) => (a, a) -> g -> (a, g)
randomR (Word64
0,Word64
qforall a. Num a => a -> a -> a
-Word64
1) gen
gen of { (Word64
x, gen
gen') -> (forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p Word64
x, gen
gen') } 
  WitnessFq ConwayPoly p m
c -> 
    let !(Word64
p,Int
m) = forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
c
    in  case forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL (\ !gen
g Int
_ -> forall a b. (a, b) -> (b, a)
swap (forall a g. (Random a, RandomGen g) => (a, a) -> g -> (a, g)
randomR (Word64
0,Word64
pforall a. Num a => a -> a -> a
-Word64
1) gen
g) ) gen
gen [Int
1..Int
m] of
          (gen
gen' , [Word64]
xs) -> ( forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
c (forall a. Unbox a => [a] -> Vector a
Vec.fromList (forall a b. (a -> b) -> [a] -> [b]
map forall a b. (Integral a, Num b) => a -> b
fromIntegral [Word64]
xs)) , gen
gen' )

-- | The field element corresponding to the polynomial @X@ (which is a primitive generator)
gen :: ConwayPoly p m -> GF p m
gen :: forall (p :: Nat) (m :: Nat). ConwayPoly p m -> GF p m
gen ConwayPoly p m
conway = forall (p :: Nat) (m :: Nat). ConwayPoly p m -> Word64 -> GF p m
gen' ConwayPoly p m
conway Word64
1

-- | The field element corresponding to the polynomial @c*X@
gen' :: ConwayPoly p m -> Word64 -> GF p m
gen' :: forall (p :: Nat) (m :: Nat). ConwayPoly p m -> Word64 -> GF p m
gen' ConwayPoly p m
conway Word64
x = forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
conway (forall a. Unbox a => Int -> [a] -> Vector a
Vec.fromListN Int
m (Word32
0 forall a. a -> [a] -> [a]
: Word32
y forall a. a -> [a] -> [a]
: forall a. Int -> a -> [a]
replicate (Int
mforall a. Num a => a -> a -> a
-Int
2) Word32
0)) where
  (Word64
p,Int
m) = forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
conway
  y :: Word32
y = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a. Integral a => a -> a -> a
mod Word64
x Word64
p) :: Word32

primGenFq :: WitnessGF p m -> GF p m 
primGenFq :: forall (p :: Nat) (m :: Nat). WitnessGF p m -> GF p m
primGenFq !WitnessGF p m
w = case WitnessGF p m
w of
  WitnessFq ConwayPoly p m
cw -> forall (p :: Nat) (m :: Nat). ConwayPoly p m -> GF p m
gen ConwayPoly p m
cw
  WitnessFp IsSmallPrime p
pw -> GF p m
prim where
    !p :: Word64
p   = forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
pw
    prim :: GF p m
prim = case Int -> Maybe Word64
lookupConwayPrimRoot_ (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
p) of
      Just Word64
g       -> forall f. Field f => Witness f -> Int -> f
embedSmall WitnessGF p m
w (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
g)
      Maybe Word64
Nothing      -> forall a. HasCallStack => String -> a
error String
"GaloisField/Fp/primGen: primitive root not found in the Conway polynomial table"

--------------------------------------------------------------------------------  

instance Eq (GF p m) where
  == :: GF p m -> GF p m -> Bool
(==) (Fp IsSmallPrime p
_ Word64
x ) (Fp IsSmallPrime p
_ Word64
y ) = Word64
x forall a. Eq a => a -> a -> Bool
== Word64
y
  (==) (Fq ConwayPoly p m
_ Vector Word32
xs) (Fq ConwayPoly p m
_ Vector Word32
ys) = Vector Word32
xs forall a. Eq a => a -> a -> Bool
== Vector Word32
ys

-- | Note: the @Ord@ instance is present only so that you can use 'GF' as key
-- in @Maps@ - the ordering is kind of arbitrary! 
instance Ord (GF p m) where
  compare :: GF p m -> GF p m -> Ordering
compare (Fp IsSmallPrime p
_ Word64
x ) (Fp IsSmallPrime p
_ Word64
y ) = forall a. Ord a => a -> a -> Ordering
compare Word64
x  Word64
y
  compare (Fq ConwayPoly p m
_ Vector Word32
xs) (Fq ConwayPoly p m
_ Vector Word32
ys) = forall a. Ord a => a -> a -> Ordering
compare Vector Word32
xs Vector Word32
ys

instance Show (GF p m) where
  show :: GF p m -> String
show (Fp IsSmallPrime p
prime   Word64
x  ) = String
"<" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Word64
x forall a. [a] -> [a] -> [a]
++ String
" mod " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show (forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
prime) forall a. [a] -> [a] -> [a]
++ String
">"
  show (Fq ConwayPoly p m
witness Vector Word32
vec) = String
"<" forall a. [a] -> [a] -> [a]
++ forall a. [a] -> [[a]] -> [a]
intercalate String
"+" [String]
list forall a. [a] -> [a] -> [a]
++ String
" mod " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Word64
p forall a. [a] -> [a] -> [a]
++ String
">" where
    (Word64
p,Int
m) = forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
witness
    list :: [String]
list = forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith forall {a} {a}. (Eq a, Num a, Show a, Show a) => a -> a -> String
f [Integer
0..] (forall a. Unbox a => Vector a -> [a]
Vec.toList Vector Word32
vec) 
    f :: a -> a -> String
f  a
0 !a
v = forall a. Show a => a -> String
show a
v
    f  a
1 !a
v = forall a. Show a => a -> String
show a
v forall a. [a] -> [a] -> [a]
++ String
"*g"
    f !a
e !a
v = forall a. Show a => a -> String
show a
v forall a. [a] -> [a] -> [a]
++ String
"*g^" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show a
e

instance Num (GF p m) where
  fromInteger :: Integer -> GF p m
fromInteger = forall a. HasCallStack => String -> a
error String
"GF/fromInteger: cannot be defined; use `embed` instead" 
  negate :: GF p m -> GF p m
negate = forall (p :: Nat) (m :: Nat). GF p m -> GF p m
neg
  + :: GF p m -> GF p m -> GF p m
(+) = forall (p :: Nat) (m :: Nat). GF p m -> GF p m -> GF p m
add
  (-) = forall (p :: Nat) (m :: Nat). GF p m -> GF p m -> GF p m
sub
  * :: GF p m -> GF p m -> GF p m
(*) = forall (p :: Nat) (m :: Nat). GF p m -> GF p m -> GF p m
mul
  abs :: GF p m -> GF p m
abs = forall a. a -> a
id
  signum :: GF p m -> GF p m
signum = forall (p :: Nat) (m :: Nat). GF p m -> GF p m
kst1

instance Fractional (GF p m) where
  fromRational :: Rational -> GF p m
fromRational = forall a. HasCallStack => String -> a
error String
"GF/fromRational: cannot be defined; use `embed` instead" 
  recip :: GF p m -> GF p m
recip = forall (p :: Nat) (m :: Nat). GF p m -> GF p m
inv 
  / :: GF p m -> GF p m -> GF p m
(/)   = forall (p :: Nat) (m :: Nat). GF p m -> GF p m -> GF p m
div 

instance Field (GF p m) where
  type Witness (GF p m) = WitnessGF p m
  type Prime   (GF p m) = p
  type Dim     (GF p m) = m
  characteristic :: Witness (GF p m) -> Integer
characteristic   !Witness (GF p m)
w = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a b. (a, b) -> a
fst (forall (p :: Nat) (m :: Nat). WitnessGF p m -> (Word64, Int)
gfParams Witness (GF p m)
w))
  dimension :: Witness (GF p m) -> Integer
dimension        !Witness (GF p m)
w = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a b. (a, b) -> b
snd (forall (p :: Nat) (m :: Nat). WitnessGF p m -> (Word64, Int)
gfParams Witness (GF p m)
w))
  fieldSize :: Witness (GF p m) -> Integer
fieldSize        !Witness (GF p m)
w = case forall (p :: Nat) (m :: Nat). WitnessGF p m -> (Word64, Int)
gfParams Witness (GF p m)
w of (Word64
p,Int
m) -> (forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
p :: Integer) forall a b. (Num a, Integral b) => a -> b -> a
^ Int
m
  enumerate :: Witness (GF p m) -> [GF p m]
enumerate        !Witness (GF p m)
w = forall (p :: Nat) (m :: Nat). WitnessGF p m -> [GF p m]
enumerateFq Witness (GF p m)
w
  witnessOf :: GF p m -> Witness (GF p m)
witnessOf        !GF p m
x = forall (p :: Nat) (m :: Nat). GF p m -> WitnessGF p m
gfWitness GF p m
x
  embed :: Witness (GF p m) -> Integer -> GF p m
embed         !Witness (GF p m)
w !Integer
x = forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp Witness (GF p m)
w (forall a. Num a => Integer -> a
fromInteger  Integer
x)
  embedSmall :: Witness (GF p m) -> Int -> GF p m
embedSmall    !Witness (GF p m)
w !Int
x = forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp Witness (GF p m)
w (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x)
  randomFieldElem :: forall gen.
RandomGen gen =>
Witness (GF p m) -> gen -> (GF p m, gen)
randomFieldElem  !Witness (GF p m)
w = forall gen (p :: Nat) (m :: Nat).
RandomGen gen =>
WitnessGF p m -> gen -> (GF p m, gen)
randomFq Witness (GF p m)
w
  primGen :: Witness (GF p m) -> GF p m
primGen          !Witness (GF p m)
w = forall (p :: Nat) (m :: Nat). WitnessGF p m -> GF p m
primGenFq Witness (GF p m)
w

  zero :: Witness (GF p m) -> GF p m
zero Witness (GF p m)
w = forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp Witness (GF p m)
w Word64
0
  one :: Witness (GF p m) -> GF p m
one  Witness (GF p m)
w = forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp Witness (GF p m)
w Word64
1
  isZero :: GF p m -> Bool
isZero = forall (p :: Nat) (m :: Nat). GF p m -> Bool
fpIsZero
  isOne :: GF p m -> Bool
isOne  = forall (p :: Nat) (m :: Nat). GF p m -> Bool
fpIsOne

--------------------------------------------------------------------------------  
-- * Enumerations

-- | Enumerate all field elements (in a lexicographic order)
enumerateFq :: WitnessGF p m -> [GF p m]
enumerateFq :: forall (p :: Nat) (m :: Nat). WitnessGF p m -> [GF p m]
enumerateFq WitnessGF p m
witness = 
  case WitnessGF p m
witness of
    WitnessFp IsSmallPrime p
p -> forall (p :: Nat). IsSmallPrime p -> [GF p 1]
enumerateFp1 IsSmallPrime p
p
    WitnessFq ConwayPoly p m
c -> forall (p :: Nat) (m :: Nat). ConwayPoly p m -> [GF p m]
enumerateFpM ConwayPoly p m
c

  where
    enumerateFpM :: ConwayPoly p m -> [GF p m]
    enumerateFpM :: forall (p :: Nat) (m :: Nat). ConwayPoly p m -> [GF p m]
enumerateFpM ConwayPoly p m
conway = [ forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
conway Vector Word32
vec | Vector Word32
vec <- [Vector Word32]
vecs ] where
      (Word64
p,Int
m) = forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
conway
      shape :: [Word32]
shape = forall a. Int -> a -> [a]
replicate Int
m (forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64
pforall a. Num a => a -> a -> a
-Word64
1) :: Word32)
      vecs :: [Vector Word32]
vecs = forall a b. (a -> b) -> [a] -> [b]
map (forall a. Unbox a => Int -> [a] -> Vector a
Vec.fromListN Int
m) ([Word32] -> [[Word32]]
word32Tuples' [Word32]
shape)
    
    enumerateFp1 :: IsSmallPrime p -> [GF p 1]
    enumerateFp1 :: forall (p :: Nat). IsSmallPrime p -> [GF p 1]
enumerateFp1 IsSmallPrime p
prime = [ forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
prime Word64
k | Word64
k <- [Word64
0..forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
primeforall a. Num a => a -> a -> a
-Word64
1] ]

--------------------------------------------------------------------------------  
-- * Field operations

kst0 :: GF p m -> GF p m
kst0 :: forall (p :: Nat) (m :: Nat). GF p m -> GF p m
kst0 GF p m
what = case GF p m
what of
  Fp IsSmallPrime p
p Word64
_ -> forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp (forall (p :: Nat). IsSmallPrime p -> WitnessGF p 1
WitnessFp IsSmallPrime p
p) Word64
0
  Fq ConwayPoly p m
c Vector Word32
_ -> forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp (forall (p :: Nat) (m :: Nat). ConwayPoly p m -> WitnessGF p m
WitnessFq ConwayPoly p m
c) Word64
0

kst1 :: GF p m -> GF p m
kst1 :: forall (p :: Nat) (m :: Nat). GF p m -> GF p m
kst1 GF p m
what = case GF p m
what of
  Fp IsSmallPrime p
p Word64
_ -> forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp (forall (p :: Nat). IsSmallPrime p -> WitnessGF p 1
WitnessFp IsSmallPrime p
p) Word64
1
  Fq ConwayPoly p m
c Vector Word32
_ -> forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp (forall (p :: Nat) (m :: Nat). ConwayPoly p m -> WitnessGF p m
WitnessFq ConwayPoly p m
c) Word64
1

neg :: GF p m -> GF p m 
neg :: forall (p :: Nat) (m :: Nat). GF p m -> GF p m
neg (Fp IsSmallPrime p
p Word64
x ) = forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p (Word64 -> Word64 -> Word64
Raw.neg (forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
p) Word64
x ) 
neg (Fq ConwayPoly p m
c Vector Word32
xs) = forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
c (Word64 -> Vector Word32 -> Vector Word32
Quo.neg (forall (p :: Nat) (m :: Nat). ConwayPoly p m -> Word64
conwayPrime_   ConwayPoly p m
c) Vector Word32
xs)

add :: GF p m -> GF p m -> GF p m
add :: forall (p :: Nat) (m :: Nat). GF p m -> GF p m -> GF p m
add (Fp IsSmallPrime p
p Word64
x ) (Fp IsSmallPrime p
_ Word64
y ) = forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p (Word64 -> Word64 -> Word64 -> Word64
Raw.add (forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
p) Word64
x  Word64
y )
add (Fq ConwayPoly p m
c Vector Word32
xs) (Fq ConwayPoly p m
_ Vector Word32
ys) = forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
c (Word64 -> Vector Word32 -> Vector Word32 -> Vector Word32
Quo.add (forall (p :: Nat) (m :: Nat). ConwayPoly p m -> Word64
conwayPrime_   ConwayPoly p m
c) Vector Word32
xs Vector Word32
ys)

sub :: GF p m -> GF p m -> GF p m
sub :: forall (p :: Nat) (m :: Nat). GF p m -> GF p m -> GF p m
sub (Fp IsSmallPrime p
p Word64
x ) (Fp IsSmallPrime p
_ Word64
y ) = forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p (Word64 -> Word64 -> Word64 -> Word64
Raw.sub (forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
p) Word64
x  Word64
y ) 
sub (Fq ConwayPoly p m
c Vector Word32
xs) (Fq ConwayPoly p m
_ Vector Word32
ys) = forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
c (Word64 -> Vector Word32 -> Vector Word32 -> Vector Word32
Quo.sub (forall (p :: Nat) (m :: Nat). ConwayPoly p m -> Word64
conwayPrime_   ConwayPoly p m
c) Vector Word32
xs Vector Word32
ys)

mul :: GF p m -> GF p m -> GF p m
mul :: forall (p :: Nat) (m :: Nat). GF p m -> GF p m -> GF p m
mul (Fp IsSmallPrime p
p Word64
x ) (Fp IsSmallPrime p
_ Word64
y ) = forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p (Word64 -> Word64 -> Word64 -> Word64
Raw.mul (forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
p) Word64
x  Word64
y ) 
mul (Fq ConwayPoly p m
c Vector Word32
xs) (Fq ConwayPoly p m
_ Vector Word32
ys) = forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
c (C -> Vector Word32 -> Vector Word32 -> Vector Word32
Quo.mul (forall (p :: Nat) (m :: Nat). ConwayPoly p m -> C
fromConwayPoly ConwayPoly p m
c) Vector Word32
xs Vector Word32
ys)

inv :: GF p m -> GF p m 
inv :: forall (p :: Nat) (m :: Nat). GF p m -> GF p m
inv (Fp IsSmallPrime p
p Word64
x ) = forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p (Word64 -> Word64 -> Word64
Raw.inv                  (forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
p) Word64
x ) 
inv (Fq ConwayPoly p m
c Vector Word32
xs) = forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
c (Word64 -> C -> Vector Word32 -> Vector Word32
Quo.inv (forall (p :: Nat) (m :: Nat). ConwayPoly p m -> Word64
conwayPrime_ ConwayPoly p m
c) (forall (p :: Nat) (m :: Nat). ConwayPoly p m -> C
fromConwayPoly ConwayPoly p m
c) Vector Word32
xs)

div :: GF p m -> GF p m -> GF p m
div :: forall (p :: Nat) (m :: Nat). GF p m -> GF p m -> GF p m
div (Fp IsSmallPrime p
p Word64
x ) (Fp IsSmallPrime p
_ Word64
y ) = forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p (Word64 -> Word64 -> Word64 -> Word64
Raw.div                  (forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
p) Word64
x  Word64
y ) 
div (Fq ConwayPoly p m
c Vector Word32
xs) (Fq ConwayPoly p m
_ Vector Word32
ys) = forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
c (Word64 -> C -> Vector Word32 -> Vector Word32 -> Vector Word32
Quo.div (forall (p :: Nat) (m :: Nat). ConwayPoly p m -> Word64
conwayPrime_ ConwayPoly p m
c) (forall (p :: Nat) (m :: Nat). ConwayPoly p m -> C
fromConwayPoly ConwayPoly p m
c) Vector Word32
xs Vector Word32
ys)

--------------------------------------------------------------------------------