-- | 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 :: WitnessGF p m -> (Word64, Int)
gfParams WitnessGF p m
w = case WitnessGF p m
w of
  WitnessFp IsSmallPrime p
p -> (IsSmallPrime p -> Word64
forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
p, Int
1)
  WitnessFq ConwayPoly p m
c -> ConwayPoly p m -> (Word64, Int)
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 (Int -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
p), Int64 -> SomeSNat64
someSNat64 (Int -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
m)) of 
  (SomeSNat64 SNat64 n
sp, SomeSNat64 SNat64 n
sm) -> WitnessGF n n -> SomeWitnessGF
forall (p :: Nat) (m :: Nat). WitnessGF p m -> SomeWitnessGF
SomeWitnessGF (WitnessGF n n -> SomeWitnessGF)
-> Maybe (WitnessGF n n) -> Maybe SomeWitnessGF
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (SNat64 n -> SNat64 n -> Maybe (WitnessGF n n)
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 (Int -> Int64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
p) of 
          SomeSNat64 SNat64 n
sp -> (WitnessGF n 1 -> SomeWitnessGF
forall (p :: Nat) (m :: Nat). WitnessGF p m -> SomeWitnessGF
SomeWitnessGF (WitnessGF n 1 -> SomeWitnessGF)
-> (IsSmallPrime n -> WitnessGF n 1)
-> IsSmallPrime n
-> SomeWitnessGF
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IsSmallPrime n -> WitnessGF n 1
forall (p :: Nat). IsSmallPrime p -> WitnessGF p 1
WitnessFp) (SNat64 n -> IsSmallPrime n
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 -> String -> SomeWitnessGF
forall a. HasCallStack => String -> a
error (String -> SomeWitnessGF) -> String -> SomeWitnessGF
forall a b. (a -> b) -> a -> b
$ String
"unsafeGaloisField: cannot find Conway polynomial for GF(" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
p String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"^" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int -> String
forall a. Show a => a -> String
show Int
m String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
")"
          Just (SomeConwayPoly ConwayPoly p m
cw) -> WitnessGF p m -> SomeWitnessGF
forall (p :: Nat) (m :: Nat). WitnessGF p m -> SomeWitnessGF
SomeWitnessGF (ConwayPoly p m -> WitnessGF p m
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 :: SNat64 p -> SNat64 m -> Maybe (WitnessGF p m)
constructGaloisField SNat64 p
sp SNat64 m
sm = case SNat64 p -> SNat64 m -> MaybeWitnessGF p m
forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> MaybeWitnessGF p m
constructGaloisField' SNat64 p
sp SNat64 m
sm of
  MaybeWitnessGF p m
NoWitness     -> Maybe (WitnessGF p m)
forall a. Maybe a
Nothing
  JustWitness WitnessGF p m
w -> WitnessGF p m -> Maybe (WitnessGF p m)
forall a. a -> Maybe a
Just WitnessGF p m
w

constructGaloisField' :: forall p m. SNat64 p -> SNat64 m -> MaybeWitnessGF p m
constructGaloisField' :: SNat64 p -> SNat64 m -> MaybeWitnessGF p m
constructGaloisField' SNat64 p
sp SNat64 m
snatm = SNat64 m
-> (SNat64 1 -> MaybeWitnessGF p 1)
-> (SNat64 m -> MaybeWitnessGF p m)
-> MaybeWitnessGF p m
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 SNat64 p -> SNat64 1 -> Maybe (ConwayPoly p 1)
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
_  -> WitnessGF p 1 -> MaybeWitnessGF p 1
forall (p :: Nat) (m :: Nat). WitnessGF p m -> MaybeWitnessGF p m
JustWitness (IsSmallPrime p -> WitnessGF p 1
forall (p :: Nat). IsSmallPrime p -> WitnessGF p 1
WitnessFp (IsSmallPrime p -> WitnessGF p 1)
-> IsSmallPrime p -> WitnessGF p 1
forall a b. (a -> b) -> a -> b
$ SNat64 p -> IsSmallPrime p
forall (n :: Nat). SNat64 n -> IsSmallPrime n
believeMeItsASmallPrime SNat64 p
sp)
    Maybe (ConwayPoly p 1)
Nothing -> case SNat64 p -> Maybe (IsSmallPrime p)
forall (n :: Nat). SNat64 n -> Maybe (IsSmallPrime n)
isSmallPrime SNat64 p
sp of
      Just IsSmallPrime p
w  -> WitnessGF p 1 -> MaybeWitnessGF p 1
forall (p :: Nat) (m :: Nat). WitnessGF p m -> MaybeWitnessGF p m
JustWitness (IsSmallPrime p -> WitnessGF p 1
forall (p :: Nat). IsSmallPrime p -> WitnessGF p 1
WitnessFp IsSmallPrime p
w)
      Maybe (IsSmallPrime p)
Nothing -> MaybeWitnessGF p 1
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 SNat64 p -> SNat64 m -> Maybe (ConwayPoly p m)
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 -> MaybeWitnessGF p m
forall (p :: Nat) (m :: Nat). MaybeWitnessGF p m
NoWitness
    Just ConwayPoly p m
cw -> WitnessGF p m -> MaybeWitnessGF p m
forall (p :: Nat) (m :: Nat). WitnessGF p m -> MaybeWitnessGF p m
JustWitness (ConwayPoly p m -> WitnessGF p m
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 :: GF p m -> WitnessGF p m
gfWitness GF p m
element = case GF p m
element of
  Fp IsSmallPrime p
p Word64
_ -> IsSmallPrime p -> WitnessGF p 1
forall (p :: Nat). IsSmallPrime p -> WitnessGF p 1
WitnessFp IsSmallPrime p
p
  Fq ConwayPoly p m
c Vector Word32
_ -> ConwayPoly p m -> WitnessGF p m
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 :: WitnessGF p m -> Word64 -> GF p m
fp WitnessGF p m
witness Word64
x = 
  case WitnessGF p m
witness of
    WitnessFp IsSmallPrime p
p -> IsSmallPrime p -> Word64 -> GF p 1
forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
fp1 IsSmallPrime p
p Word64
x 
    WitnessFq ConwayPoly p m
c -> ConwayPoly p m -> Word64 -> GF p m
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 :: ConwayPoly p m -> Word64 -> GF p m
fpM ConwayPoly p m
conway Word64
x = ConwayPoly p m -> Vector Word32 -> GF p m
forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
conway (Int -> [Word32] -> Vector Word32
forall a. Unbox a => Int -> [a] -> Vector a
Vec.fromListN Int
m (Word32
y Word32 -> [Word32] -> [Word32]
forall a. a -> [a] -> [a]
: Int -> Word32 -> [Word32]
forall a. Int -> a -> [a]
replicate (Int
mInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Word32
0)) where
      (Word64
p,Int
m) = ConwayPoly p m -> (Word64, Int)
forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
conway
      y :: Word32
y = if Word64
x Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
>= Word64
0 Bool -> Bool -> Bool
&& Word64
x Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< Word64
p then Word64 -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
x else Word64 -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
mod Word64
x Word64
p) :: Word32
    
    fp1 :: IsSmallPrime p -> Word64 -> GF p 1
    fp1 :: IsSmallPrime p -> Word64 -> GF p 1
fp1 IsSmallPrime p
prime Word64
x = IsSmallPrime p -> Word64 -> GF p 1
forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
prime Word64
y where
      p :: Word64
p = IsSmallPrime p -> Word64
forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
prime 
      y :: Word64
y = if Word64
x Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
>= Word64
0 Bool -> Bool -> Bool
&& Word64
x Word64 -> Word64 -> Bool
forall a. Ord a => a -> a -> Bool
< Word64
p then Word64
x else Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
mod Word64
x Word64
p

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

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

randomFq :: RandomGen gen => WitnessGF p m -> gen -> (GF p m, gen) 
randomFq :: 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 = IsSmallPrime p -> Word64
forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
p 
    in  case (Word64, Word64) -> gen -> (Word64, gen)
forall a g. (Random a, RandomGen g) => (a, a) -> g -> (a, g)
randomR (Word64
0,Word64
qWord64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
-Word64
1) gen
gen of { (Word64
x, gen
gen') -> (IsSmallPrime p -> Word64 -> GF p 1
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) = ConwayPoly p m -> (Word64, Int)
forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
c
    in  case (gen -> Int -> (gen, Word64)) -> gen -> [Int] -> (gen, [Word64])
forall (t :: * -> *) a b c.
Traversable t =>
(a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL (\ !gen
g Int
_ -> (Word64, gen) -> (gen, Word64)
forall a b. (a, b) -> (b, a)
swap ((Word64, Word64) -> gen -> (Word64, gen)
forall a g. (Random a, RandomGen g) => (a, a) -> g -> (a, g)
randomR (Word64
0,Word64
pWord64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
-Word64
1) gen
g) ) gen
gen [Int
1..Int
m] of
          (gen
gen' , [Word64]
xs) -> ( ConwayPoly p m -> Vector Word32 -> GF p m
forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
c ([Word32] -> Vector Word32
forall a. Unbox a => [a] -> Vector a
Vec.fromList ((Word64 -> Word32) -> [Word64] -> [Word32]
forall a b. (a -> b) -> [a] -> [b]
map Word64 -> Word32
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 :: ConwayPoly p m -> GF p m
gen ConwayPoly p m
conway = ConwayPoly p m -> Word64 -> GF p m
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' :: ConwayPoly p m -> Word64 -> GF p m
gen' ConwayPoly p m
conway Word64
x = ConwayPoly p m -> Vector Word32 -> GF p m
forall (p :: Nat) (m :: Nat).
ConwayPoly p m -> Vector Word32 -> GF p m
Fq ConwayPoly p m
conway (Int -> [Word32] -> Vector Word32
forall a. Unbox a => Int -> [a] -> Vector a
Vec.fromListN Int
m (Word32
0 Word32 -> [Word32] -> [Word32]
forall a. a -> [a] -> [a]
: Word32
y Word32 -> [Word32] -> [Word32]
forall a. a -> [a] -> [a]
: Int -> Word32 -> [Word32]
forall a. Int -> a -> [a]
replicate (Int
mInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
2) Word32
0)) where
  (Word64
p,Int
m) = ConwayPoly p m -> (Word64, Int)
forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
conway
  y :: Word32
y = Word64 -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64 -> Word64 -> Word64
forall a. Integral a => a -> a -> a
mod Word64
x Word64
p) :: Word32

primGenFq :: WitnessGF p m -> GF p m 
primGenFq :: WitnessGF p m -> GF p m
primGenFq !WitnessGF p m
w = case WitnessGF p m
w of
  WitnessFq ConwayPoly p m
cw -> ConwayPoly p m -> GF p m
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   = IsSmallPrime p -> Word64
forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
pw
    prim :: GF p m
prim = case Int -> Maybe Word64
lookupConwayPrimRoot_ (Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
p) of
      Just Word64
g       -> Witness (GF p m) -> Int -> GF p m
forall f. Field f => Witness f -> Int -> f
embedSmall Witness (GF p m)
WitnessGF p m
w (Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
g)
      Maybe Word64
Nothing      -> String -> GF p m
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 Word64 -> Word64 -> Bool
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 Vector Word32 -> Vector Word32 -> Bool
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 ) = Word64 -> Word64 -> Ordering
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) = Vector Word32 -> Vector Word32 -> Ordering
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
"<" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Word64 -> String
forall a. Show a => a -> String
show Word64
x String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" mod " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Word64 -> String
forall a. Show a => a -> String
show (IsSmallPrime p -> Word64
forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
prime) String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
">"
  show (Fq ConwayPoly p m
witness Vector Word32
vec) = String
"<" String -> ShowS
forall a. [a] -> [a] -> [a]
++ String -> [String] -> String
forall a. [a] -> [[a]] -> [a]
intercalate String
"+" [String]
list String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" mod " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Word64 -> String
forall a. Show a => a -> String
show Word64
p String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
">" where
    (Word64
p,Int
m) = ConwayPoly p m -> (Word64, Int)
forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
witness
    list :: [String]
list = (Integer -> Word32 -> String) -> [Integer] -> [Word32] -> [String]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Integer -> Word32 -> String
forall a a. (Eq a, Num a, Show a, Show a) => a -> a -> String
f [Integer
0..] (Vector Word32 -> [Word32]
forall a. Unbox a => Vector a -> [a]
Vec.toList Vector Word32
vec) 
    f :: a -> a -> String
f  a
0 !a
v = a -> String
forall a. Show a => a -> String
show a
v
    f  a
1 !a
v = a -> String
forall a. Show a => a -> String
show a
v String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"*g"
    f !a
e !a
v = a -> String
forall a. Show a => a -> String
show a
v String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"*g^" String -> ShowS
forall a. [a] -> [a] -> [a]
++ a -> String
forall a. Show a => a -> String
show a
e

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

instance Fractional (GF p m) where
  fromRational :: Rational -> GF p m
fromRational = String -> Rational -> GF p m
forall a. HasCallStack => String -> a
error String
"GF/fromRational: cannot be defined; use `embed` instead" 
  recip :: GF p m -> GF p m
recip = GF p m -> GF p m
forall (p :: Nat) (m :: Nat). GF p m -> GF p m
inv 
  / :: GF p m -> GF p m -> GF p m
(/)   = 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 = Word64 -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral ((Word64, Int) -> Word64
forall a b. (a, b) -> a
fst (WitnessGF p m -> (Word64, Int)
forall (p :: Nat) (m :: Nat). WitnessGF p m -> (Word64, Int)
gfParams Witness (GF p m)
WitnessGF p m
w))
  dimension :: Witness (GF p m) -> Integer
dimension        !Witness (GF p m)
w = Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral ((Word64, Int) -> Int
forall a b. (a, b) -> b
snd (WitnessGF p m -> (Word64, Int)
forall (p :: Nat) (m :: Nat). WitnessGF p m -> (Word64, Int)
gfParams Witness (GF p m)
WitnessGF p m
w))
  fieldSize :: Witness (GF p m) -> Integer
fieldSize        !Witness (GF p m)
w = case WitnessGF p m -> (Word64, Int)
forall (p :: Nat) (m :: Nat). WitnessGF p m -> (Word64, Int)
gfParams Witness (GF p m)
WitnessGF p m
w of (Word64
p,Int
m) -> (Word64 -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
p :: Integer) Integer -> Int -> 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 = WitnessGF p m -> [GF p m]
forall (p :: Nat) (m :: Nat). WitnessGF p m -> [GF p m]
enumerateFq Witness (GF p m)
WitnessGF p m
w
  witnessOf :: GF p m -> Witness (GF p m)
witnessOf        !GF p m
x = GF p m -> WitnessGF p m
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 = WitnessGF p m -> Word64 -> GF p m
forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp Witness (GF p m)
WitnessGF p m
w (Integer -> Word64
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 = WitnessGF p m -> Word64 -> GF p m
forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp Witness (GF p m)
WitnessGF p m
w (Int -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
x)
  randomFieldElem :: Witness (GF p m) -> gen -> (GF p m, gen)
randomFieldElem  !Witness (GF p m)
w = WitnessGF p m -> gen -> (GF p m, gen)
forall gen (p :: Nat) (m :: Nat).
RandomGen gen =>
WitnessGF p m -> gen -> (GF p m, gen)
randomFq Witness (GF p m)
WitnessGF p m
w
  primGen :: Witness (GF p m) -> GF p m
primGen          !Witness (GF p m)
w = WitnessGF p m -> GF p m
forall (p :: Nat) (m :: Nat). WitnessGF p m -> GF p m
primGenFq Witness (GF p m)
WitnessGF p m
w

  zero :: Witness (GF p m) -> GF p m
zero Witness (GF p m)
w = WitnessGF p m -> Word64 -> GF p m
forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp Witness (GF p m)
WitnessGF p m
w Word64
0
  one :: Witness (GF p m) -> GF p m
one  Witness (GF p m)
w = WitnessGF p m -> Word64 -> GF p m
forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp Witness (GF p m)
WitnessGF p m
w Word64
1
  isZero :: GF p m -> Bool
isZero = GF p m -> Bool
forall (p :: Nat) (m :: Nat). GF p m -> Bool
fpIsZero
  isOne :: GF p m -> Bool
isOne  = GF p m -> Bool
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 :: WitnessGF p m -> [GF p m]
enumerateFq WitnessGF p m
witness = 
  case WitnessGF p m
witness of
    WitnessFp IsSmallPrime p
p -> IsSmallPrime p -> [GF p 1]
forall (p :: Nat). IsSmallPrime p -> [GF p 1]
enumerateFp1 IsSmallPrime p
p
    WitnessFq ConwayPoly p m
c -> ConwayPoly p m -> [GF p m]
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 :: ConwayPoly p m -> [GF p m]
enumerateFpM ConwayPoly p m
conway = [ ConwayPoly p m -> Vector Word32 -> GF p m
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) = ConwayPoly p m -> (Word64, Int)
forall (p :: Nat) (m :: Nat). ConwayPoly p m -> (Word64, Int)
conwayParams_ ConwayPoly p m
conway
      shape :: [Word32]
shape = Int -> Word32 -> [Word32]
forall a. Int -> a -> [a]
replicate Int
m (Word64 -> Word32
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64
pWord64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
-Word64
1) :: Word32)
      vecs :: [Vector Word32]
vecs = ([Word32] -> Vector Word32) -> [[Word32]] -> [Vector Word32]
forall a b. (a -> b) -> [a] -> [b]
map (Int -> [Word32] -> Vector Word32
forall a. Unbox a => Int -> [a] -> Vector a
Vec.fromListN Int
m) ([Word32] -> [[Word32]]
word32Tuples' [Word32]
shape)
    
    enumerateFp1 :: IsSmallPrime p -> [GF p 1]
    enumerateFp1 :: IsSmallPrime p -> [GF p 1]
enumerateFp1 IsSmallPrime p
prime = [ IsSmallPrime p -> Word64 -> GF p 1
forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
prime Word64
k | Word64
k <- [Word64
0..IsSmallPrime p -> Word64
forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
primeWord64 -> Word64 -> Word64
forall a. Num a => a -> a -> a
-Word64
1] ]

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

kst0 :: GF p m -> GF p m
kst0 :: GF p m -> GF p m
kst0 GF p m
what = case GF p m
what of
  Fp IsSmallPrime p
p Word64
_ -> WitnessGF p 1 -> Word64 -> GF p 1
forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp (IsSmallPrime p -> WitnessGF p 1
forall (p :: Nat). IsSmallPrime p -> WitnessGF p 1
WitnessFp IsSmallPrime p
p) Word64
0
  Fq ConwayPoly p m
c Vector Word32
_ -> WitnessGF p m -> Word64 -> GF p m
forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp (ConwayPoly p m -> WitnessGF p m
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 :: GF p m -> GF p m
kst1 GF p m
what = case GF p m
what of
  Fp IsSmallPrime p
p Word64
_ -> WitnessGF p 1 -> Word64 -> GF p 1
forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp (IsSmallPrime p -> WitnessGF p 1
forall (p :: Nat). IsSmallPrime p -> WitnessGF p 1
WitnessFp IsSmallPrime p
p) Word64
1
  Fq ConwayPoly p m
c Vector Word32
_ -> WitnessGF p m -> Word64 -> GF p m
forall (p :: Nat) (m :: Nat). WitnessGF p m -> Word64 -> GF p m
fp (ConwayPoly p m -> WitnessGF p m
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 :: GF p m -> GF p m
neg (Fp IsSmallPrime p
p Word64
x ) = IsSmallPrime p -> Word64 -> GF p 1
forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p (Word64 -> Word64 -> Word64
Raw.neg (IsSmallPrime p -> Word64
forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
p) Word64
x ) 
neg (Fq ConwayPoly p m
c Vector Word32
xs) = ConwayPoly p m -> Vector Word32 -> GF p m
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 (ConwayPoly p m -> Word64
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 :: GF p m -> GF p m -> GF p m
add (Fp IsSmallPrime p
p Word64
x ) (Fp IsSmallPrime p
_ Word64
y ) = IsSmallPrime p -> Word64 -> GF p 1
forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p (Word64 -> Word64 -> Word64 -> Word64
Raw.add (IsSmallPrime p -> Word64
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) = ConwayPoly p m -> Vector Word32 -> GF p m
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 (ConwayPoly p m -> Word64
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 :: GF p m -> GF p m -> GF p m
sub (Fp IsSmallPrime p
p Word64
x ) (Fp IsSmallPrime p
_ Word64
y ) = IsSmallPrime p -> Word64 -> GF p 1
forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p (Word64 -> Word64 -> Word64 -> Word64
Raw.sub (IsSmallPrime p -> Word64
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) = ConwayPoly p m -> Vector Word32 -> GF p m
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 (ConwayPoly p m -> Word64
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 :: GF p m -> GF p m -> GF p m
mul (Fp IsSmallPrime p
p Word64
x ) (Fp IsSmallPrime p
_ Word64
y ) = IsSmallPrime p -> Word64 -> GF p 1
forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p (Word64 -> Word64 -> Word64 -> Word64
Raw.mul (IsSmallPrime p -> Word64
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) = ConwayPoly p m -> Vector Word32 -> GF p m
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 (ConwayPoly p m -> C
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 :: GF p m -> GF p m
inv (Fp IsSmallPrime p
p Word64
x ) = IsSmallPrime p -> Word64 -> GF p 1
forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p (Word64 -> Word64 -> Word64
Raw.inv                  (IsSmallPrime p -> Word64
forall (n :: Nat). IsSmallPrime n -> Word64
fromSmallPrime IsSmallPrime p
p) Word64
x ) 
inv (Fq ConwayPoly p m
c Vector Word32
xs) = ConwayPoly p m -> Vector Word32 -> GF p m
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 (ConwayPoly p m -> Word64
forall (p :: Nat) (m :: Nat). ConwayPoly p m -> Word64
conwayPrime_ ConwayPoly p m
c) (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 :: GF p m -> GF p m -> GF p m
div (Fp IsSmallPrime p
p Word64
x ) (Fp IsSmallPrime p
_ Word64
y ) = IsSmallPrime p -> Word64 -> GF p 1
forall (p :: Nat). IsSmallPrime p -> Word64 -> GF p 1
Fp IsSmallPrime p
p (Word64 -> Word64 -> Word64 -> Word64
Raw.div                  (IsSmallPrime p -> Word64
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) = ConwayPoly p m -> Vector Word32 -> GF p m
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 (ConwayPoly p m -> Word64
forall (p :: Nat) (m :: Nat). ConwayPoly p m -> Word64
conwayPrime_ ConwayPoly p m
c) (ConwayPoly p m -> C
forall (p :: Nat) (m :: Nat). ConwayPoly p m -> C
fromConwayPoly ConwayPoly p m
c) Vector Word32
xs Vector Word32
ys)

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