-- | Small Galois fields via precomputed tables of Zech's logarithms.
--
-- <https://en.wikipedia.org/wiki/Zech%27s_logarithm>
--
-- When \"creating\" a field, we precompute the Zech logarithm table. 
-- After that, computations should be fast.
--
-- This is practical up to fields of size @10^5@-@10^6@.
--
-- This representation also supports handling of subfields.
--

{-# LANGUAGE BangPatterns, ScopedTypeVariables, TypeFamilies #-}
{-# LANGUAGE StandaloneDeriving, ExistentialQuantification #-}

module Math.FiniteField.GaloisField.Zech 
  ( -- * Tables of Zech logarithms
    ZechTable(..)
  , makeZechTable
    -- * Witness for the existence of the field
  , WitnessZech(..)
  , SomeWitnessZech(..)
  , mkZechField
  , unsafeZechField
  , constructZechField
    -- * Field elements
  , Zech
    -- * Subfields
    -- $subfield_doc
  , SubField , ambientWitness , subFieldWitness , subFieldProof , fiberSize
  , subFieldName
  , SomeSubField(..)
  , constructSubField , enumerateSubFields
  , embedSubField
  , projectSubField
  , isInSubField
    -- , subFieldCoordinates
  )
  where 

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

import Data.Int

import GHC.TypeNats (Nat)

import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map

import Data.Vector.Unboxed ( Vector , MVector )
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.GaloisField.Small ( GF , WitnessGF )
import qualified Math.FiniteField.GaloisField.Small as GF

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

-- | A table of Zech logarithms (and some more data required for the operations)
data ZechTable = ZechTable
  { ZechTable -> (Int32, Int32)
_zechParams :: !(Int32,Int32)     -- ^ the parameters @(p,m)@
  , ZechTable -> Int32
_qMinus1    :: !Int32             -- ^ order of the multiplicative group @q-1 = p^m - 1@ 
  , ZechTable -> Int32
_logMinus1  :: !Int32             -- ^ an integer @e@ such that @g^e = -1@
  , ZechTable -> Vector Int32
_embedding  :: !(Vector Int32)    -- ^ embedding of @F_p@ into @F_q@ (including 0)
  , ZechTable -> Vector Int32
_zechLogs   :: !(Vector Int32)    -- ^ Zech's logarithms (except for 0; so the length is @q-1@)
  }
  deriving Int -> ZechTable -> ShowS
[ZechTable] -> ShowS
ZechTable -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [ZechTable] -> ShowS
$cshowList :: [ZechTable] -> ShowS
show :: ZechTable -> String
$cshow :: ZechTable -> String
showsPrec :: Int -> ZechTable -> ShowS
$cshowsPrec :: Int -> ZechTable -> ShowS
Show

newtype WitnessZech (p :: Nat) (m :: Nat) 
  = WitnessZech { forall (p :: Nat) (m :: Nat). WitnessZech p m -> ZechTable
fromWitnessZech :: ZechTable }
  deriving Int -> WitnessZech p m -> ShowS
forall (p :: Nat) (m :: Nat). Int -> WitnessZech p m -> ShowS
forall (p :: Nat) (m :: Nat). [WitnessZech p m] -> ShowS
forall (p :: Nat) (m :: Nat). WitnessZech p m -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [WitnessZech p m] -> ShowS
$cshowList :: forall (p :: Nat) (m :: Nat). [WitnessZech p m] -> ShowS
show :: WitnessZech p m -> String
$cshow :: forall (p :: Nat) (m :: Nat). WitnessZech p m -> String
showsPrec :: Int -> WitnessZech p m -> ShowS
$cshowsPrec :: forall (p :: Nat) (m :: Nat). Int -> WitnessZech p m -> ShowS
Show

data SomeWitnessZech 
  = forall p m. SomeWitnessZech (WitnessZech p m)

deriving instance Show SomeWitnessZech

mkZechField :: Int -> Int -> Maybe SomeWitnessZech
mkZechField :: Int -> Int -> Maybe SomeWitnessZech
mkZechField Int
p Int
m = case Int -> Int -> Maybe SomeWitnessGF
GF.mkGaloisField Int
p Int
m of 
  Maybe SomeWitnessGF
Nothing   -> forall a. Maybe a
Nothing
  Just SomeWitnessGF
some -> case SomeWitnessGF
some of
    GF.SomeWitnessGF WitnessGF p m
wgf -> forall a. a -> Maybe a
Just (forall (p :: Nat) (m :: Nat). WitnessZech p m -> SomeWitnessZech
SomeWitnessZech (forall (p :: Nat) (m :: Nat). ZechTable -> WitnessZech p m
WitnessZech (forall (p :: Nat) (m :: Nat). WitnessGF p m -> ZechTable
makeZechTable WitnessGF p m
wgf)))

unsafeZechField :: Int -> Int -> SomeWitnessZech
unsafeZechField :: Int -> Int -> SomeWitnessZech
unsafeZechField Int
p Int
m = case Int -> Int -> Maybe SomeWitnessZech
mkZechField Int
p Int
m of 
  Maybe SomeWitnessZech
Nothing   -> forall a. HasCallStack => String -> a
error forall a b. (a -> b) -> a -> b
$ String
"unsafeZechField: 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 SomeWitnessZech
some -> SomeWitnessZech
some

constructZechField :: SNat64 p -> SNat64 m -> Maybe (WitnessZech p m)
constructZechField :: forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> Maybe (WitnessZech p m)
constructZechField SNat64 p
sp SNat64 m
sm = case forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> Maybe (WitnessGF p m)
GF.constructGaloisField SNat64 p
sp SNat64 m
sm of 
  Maybe (WitnessGF p m)
Nothing   -> forall a. Maybe a
Nothing
  Just WitnessGF p m
wgf  -> forall a. a -> Maybe a
Just (forall (p :: Nat) (m :: Nat). ZechTable -> WitnessZech p m
WitnessZech (forall (p :: Nat) (m :: Nat). WitnessGF p m -> ZechTable
makeZechTable WitnessGF p m
wgf))

-- instance FieldWitness (WitnessZech p m) where
--   type FieldElem    (WitnessZech p m) = Zech p m
--   type WitnessPrime (WitnessZech p m) = p
--   type WitnessDim   (WitnessZech p m) = m

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

-- $subfield_doc
--
-- A field of size @p^m@ has a unique subfield of size @p^k@ for all @k|m@.
-- The Conway polynomials are constructed so that the Conway polynomials of
-- the subfields are compatible with the Conway polynomial of the ambient
-- field, in the sense that the canonical primitive generators @g@ of the ambient field
-- and @h@ of the
--
-- > h = g ^ ((p^m-1)/(p^k-1))
--
-- This makes implementing subfields in the the discrete log representation 
-- particularly simple.
--

-- | A witness for the subfield @GF(p,k)@ of @GF(p,m)@
data SubField (p :: Nat) (m :: Nat) (k :: Nat) = SubField
  { forall (p :: Nat) (m :: Nat) (k :: Nat).
SubField p m k -> WitnessZech p m
ambientWitness  :: !(WitnessZech p m)  -- ^ witness for the ambient field
  , forall (p :: Nat) (m :: Nat) (k :: Nat).
SubField p m k -> WitnessZech p k
subFieldWitness :: !(WitnessZech p k)  -- ^ witness for the existence of the subfield
  , forall (p :: Nat) (m :: Nat) (k :: Nat).
SubField p m k -> Divides k m
subFieldProof   :: !(Divides k m)      -- ^ proof that @k@ divides @m@
  , forall (p :: Nat) (m :: Nat) (k :: Nat). SubField p m k -> Int32
fiberSize       :: !Int32              -- ^ the quotient @(p^m-1)/(p^k-1)@
  }
  deriving Int -> SubField p m k -> ShowS
forall (p :: Nat) (m :: Nat) (k :: Nat).
Int -> SubField p m k -> ShowS
forall (p :: Nat) (m :: Nat) (k :: Nat). [SubField p m k] -> ShowS
forall (p :: Nat) (m :: Nat) (k :: Nat). SubField p m k -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [SubField p m k] -> ShowS
$cshowList :: forall (p :: Nat) (m :: Nat) (k :: Nat). [SubField p m k] -> ShowS
show :: SubField p m k -> String
$cshow :: forall (p :: Nat) (m :: Nat) (k :: Nat). SubField p m k -> String
showsPrec :: Int -> SubField p m k -> ShowS
$cshowsPrec :: forall (p :: Nat) (m :: Nat) (k :: Nat).
Int -> SubField p m k -> ShowS
Show

-- | Returns something like @"GF(p^3) ⊆ GF(p^6)"@
subFieldName :: SubField p m k -> String
subFieldName :: forall (p :: Nat) (m :: Nat) (k :: Nat). SubField p m k -> String
subFieldName SubField p m k
w = forall f. Field f => Witness f -> String
fieldName (forall (p :: Nat) (m :: Nat) (k :: Nat).
SubField p m k -> WitnessZech p k
subFieldWitness SubField p m k
w) forall a. [a] -> [a] -> [a]
++ String
" ⊆ " forall a. [a] -> [a] -> [a]
++   forall f. Field f => Witness f -> String
fieldName (forall (p :: Nat) (m :: Nat) (k :: Nat).
SubField p m k -> WitnessZech p m
ambientWitness SubField p m k
w)

-- | Some subfield of @GF(p,m)@
data SomeSubField (p :: Nat) (m :: Nat) 
  = forall k. SomeSubField (SubField p m k)

deriving instance Show (SomeSubField p m)

constructSubField :: WitnessZech p m -> Divides k m -> SubField p m k
constructSubField :: forall (p :: Nat) (m :: Nat) (k :: Nat).
WitnessZech p m -> Divides k m -> SubField p m k
constructSubField WitnessZech p m
ambientw Divides k m
proof = 
  case forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> Maybe (WitnessZech p m)
constructZechField (forall f. Field f => Witness f -> SNat64 (Prime f)
fieldPrimeSNat64 WitnessZech p m
ambientw) (forall (k :: Nat) (n :: Nat). Divides k n -> SNat64 k
divisorSNat Divides k m
proof) of
    Maybe (WitnessZech p k)
Nothing    -> forall a. HasCallStack => String -> a
error String
"GaloisField/Zech/constructSubField': fatal error: no Conway polynomial for the subfield (this should not happen)" 
    Just WitnessZech p k
subw  -> (forall (p :: Nat) (m :: Nat) (k :: Nat).
WitnessZech p m
-> WitnessZech p k -> Divides k m -> Int32 -> SubField p m k
SubField WitnessZech p m
ambientw WitnessZech p k
subw Divides k m
proof Int32
d) where
      p :: Integer
p = forall f. Field f => Witness f -> Integer
characteristic WitnessZech p m
ambientw
      m :: Integer
m = forall f. Field f => Witness f -> Integer
dimension      WitnessZech p m
ambientw
      k :: Word64
k = forall (k :: Nat) (n :: Nat). Divides k n -> Word64
_divisor       Divides k m
proof
      d :: Int32
d = forall a. Integral a => a -> a -> a
div (forall a. Num a => Integer -> a
fromInteger Integer
p forall a b. (Num a, Integral b) => a -> b -> a
^ Integer
m forall a. Num a => a -> a -> a
- Int32
1) (forall a. Num a => Integer -> a
fromInteger Integer
p forall a b. (Num a, Integral b) => a -> b -> a
^ Word64
k forall a. Num a => a -> a -> a
- Int32
1)

constructSubField_ :: WitnessZech p m -> SNat64 k -> Maybe (SubField p m k)
constructSubField_ :: forall (p :: Nat) (m :: Nat) (k :: Nat).
WitnessZech p m -> SNat64 k -> Maybe (SubField p m k)
constructSubField_ WitnessZech p m
ambientw sk :: SNat64 k
sk@(SNat64 Word64
k) =
  case forall (k :: Nat) (n :: Nat).
SNat64 k -> SNat64 n -> Maybe (Divides k n)
divides SNat64 k
sk (forall f. Field f => Witness f -> SNat64 (Dim f)
fieldDimSNat64 WitnessZech p m
ambientw) of
    Maybe (Divides k m)
Nothing    -> forall a. Maybe a
Nothing
    Just Divides k m
proof -> forall a. a -> Maybe a
Just (forall (p :: Nat) (m :: Nat) (k :: Nat).
WitnessZech p m -> Divides k m -> SubField p m k
constructSubField WitnessZech p m
ambientw Divides k m
proof)

enumerateSubFields :: forall p m. WitnessZech p m -> [SomeSubField p m]
enumerateSubFields :: forall (p :: Nat) (m :: Nat). WitnessZech p m -> [SomeSubField p m]
enumerateSubFields WitnessZech p m
ambientw = forall a b. (a -> b) -> [a] -> [b]
map Divisor (Dim (Zech p m)) -> SomeSubField p m
construct (forall (n :: Nat). SNat64 n -> [Divisor n]
divisors (forall f. Field f => Witness f -> SNat64 (Dim f)
fieldDimSNat64 WitnessZech p m
ambientw)) where
  construct :: Divisor (Dim (Zech p m)) -> SomeSubField p m
construct (Divisor Divides k (Dim (Zech p m))
proof) = forall (p :: Nat) (m :: Nat) (k :: Nat).
SubField p m k -> SomeSubField p m
SomeSubField (forall (p :: Nat) (m :: Nat) (k :: Nat).
WitnessZech p m -> Divides k m -> SubField p m k
constructSubField WitnessZech p m
ambientw Divides k (Dim (Zech p m))
proof)

embedSubField :: SubField p m k -> Zech p k -> Zech p m
embedSubField :: forall (p :: Nat) (m :: Nat) (k :: Nat).
SubField p m k -> Zech p k -> Zech p m
embedSubField (SubField WitnessZech p m
aw WitnessZech p k
_ Divides k m
_ Int32
d) (Zech ZechTable
_ Int32
a) 
  | Int32
a forall a. Ord a => a -> a -> Bool
< Int32
0      = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech (forall (p :: Nat) (m :: Nat). WitnessZech p m -> ZechTable
fromWitnessZech WitnessZech p m
aw)  Int32
a
  | Bool
otherwise  = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech (forall (p :: Nat) (m :: Nat). WitnessZech p m -> ZechTable
fromWitnessZech WitnessZech p m
aw) (Int32
aforall a. Num a => a -> a -> a
*Int32
d)

projectSubField :: SubField p m k -> Zech p m -> Maybe (Zech p k)
projectSubField :: forall (p :: Nat) (m :: Nat) (k :: Nat).
SubField p m k -> Zech p m -> Maybe (Zech p k)
projectSubField (SubField WitnessZech p m
_ WitnessZech p k
sw Divides k m
_ Int32
d) (Zech ZechTable
_ Int32
a) 
  | Int32
a forall a. Ord a => a -> a -> Bool
< Int32
0      = forall a. a -> Maybe a
Just (forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech (forall (p :: Nat) (m :: Nat). WitnessZech p m -> ZechTable
fromWitnessZech WitnessZech p k
sw) Int32
a)
  | Bool
otherwise  = case forall a. Integral a => a -> a -> (a, a)
divMod Int32
a Int32
d of
                   (Int32
b,Int32
r) -> if Int32
r forall a. Eq a => a -> a -> Bool
== Int32
0 then forall a. a -> Maybe a
Just (forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech (forall (p :: Nat) (m :: Nat). WitnessZech p m -> ZechTable
fromWitnessZech WitnessZech p k
sw) Int32
b) else forall a. Maybe a
Nothing

isInSubField :: SubField p m k -> Zech p m -> Bool
isInSubField :: forall (p :: Nat) (m :: Nat) (k :: Nat).
SubField p m k -> Zech p m -> Bool
isInSubField (SubField WitnessZech p m
_ WitnessZech p k
sw Divides k m
_ Int32
d) (Zech ZechTable
_ Int32
a) 
  | Int32
a forall a. Ord a => a -> a -> Bool
< Int32
0      = Bool
True
  | Bool
otherwise  = forall a. Integral a => a -> a -> a
mod Int32
a Int32
d forall a. Eq a => a -> a -> Bool
== Int32
0

-- | @GF(p^m)@ as a vector space over @GF(p^k)@
subFieldCoordinates :: SubField p m k -> Zech p m -> [Zech p k]
subFieldCoordinates :: forall (p :: Nat) (m :: Nat) (k :: Nat).
SubField p m k -> Zech p m -> [Zech p k]
subFieldCoordinates = forall a. HasCallStack => String -> a
error String
"subFieldCoordinates: how to implement this??"

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

-- | An element of the field @GF(p^m)@
--
-- Implementation note: 
-- Field elements are represented by integers from the interval @[-1...q-2]@:
--
-- * @-1@ corresponds to @0@
--
-- * @0@  corresponds to @1@
--
-- * @1@  corresponds to @g@
--
-- * @k@  corresponds to @g^k@
--
data Zech (p :: Nat) (m :: Nat) = Zech !ZechTable {-# UNPACK #-} !Int32

instance Eq (Zech p m) where
  == :: Zech p m -> Zech p m -> Bool
(==) (Zech ZechTable
_ Int32
k1) (Zech ZechTable
_ Int32
k2) = Int32
k1 forall a. Eq a => a -> a -> Bool
== Int32
k2 

instance Ord (Zech p m) where
  compare :: Zech p m -> Zech p m -> Ordering
compare (Zech ZechTable
_ Int32
k1) (Zech ZechTable
_ Int32
k2) = forall a. Ord a => a -> a -> Ordering
compare Int32
k1 Int32
k2

instance Show (Zech p m) where
  show :: Zech p m -> String
show (Zech ZechTable
_ Int32
n)
    | Int32
n forall a. Eq a => a -> a -> Bool
== -Int32
1    = String
"0"
    | Int32
n forall a. Eq a => a -> a -> Bool
==  Int32
0    = String
"1"
    | Int32
n forall a. Eq a => a -> a -> Bool
==  Int32
1    = String
"g"
    | Bool
otherwise  = String
"g^" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Int32
n

instance Num (Zech p m) where
  fromInteger :: Integer -> Zech p m
fromInteger = forall a. HasCallStack => String -> a
error String
"GaloisField/Zech/fromInteger: cannot be defined; use `embed` instead!"
  negate :: Zech p m -> Zech p m
negate = forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m
zechNeg
  + :: Zech p m -> Zech p m -> Zech p m
(+)    = forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m -> Zech p m
zechAdd
  (-)    = forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m -> Zech p m
zechSub
  * :: Zech p m -> Zech p m -> Zech p m
(*)    = forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m -> Zech p m
zechMul 
  abs :: Zech p m -> Zech p m
abs    = forall a. a -> a
id
  signum :: Zech p m -> Zech p m
signum = forall a. HasCallStack => String -> a
error String
"GaloisField/Zech/signum: not implemented"

instance Fractional (Zech p m) where
  fromRational :: Rational -> Zech p m
fromRational = forall a. HasCallStack => String -> a
error String
"GaloisField/Zech/fromRational: cannot be defined; use `embed` instead!"
  recip :: Zech p m -> Zech p m
recip = forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m
zechInv
  / :: Zech p m -> Zech p m -> Zech p m
(/)   = forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m -> Zech p m
zechDiv

instance Field (Zech p m) where
  type Witness (Zech p m) = WitnessZech p m
  type Prime   (Zech p m) = p
  type Dim     (Zech p m) = m

  characteristic :: Witness (Zech p m) -> Integer
characteristic (WitnessZech !ZechTable
w) = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a b. (a, b) -> a
fst (ZechTable -> (Int32, Int32)
_zechParams ZechTable
w))
  dimension :: Witness (Zech p m) -> Integer
dimension      (WitnessZech !ZechTable
w) = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a b. (a, b) -> b
snd (ZechTable -> (Int32, Int32)
_zechParams ZechTable
w))
  fieldSize :: Witness (Zech p m) -> Integer
fieldSize      (WitnessZech !ZechTable
w) = case ZechTable -> (Int32, Int32)
_zechParams ZechTable
w of (Int32
p,Int32
m) -> (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int32
p :: Integer) forall a b. (Num a, Integral b) => a -> b -> a
^ Int32
m
  enumerate :: Witness (Zech p m) -> [Zech p m]
enumerate         Witness (Zech p m)
w = forall (p :: Nat) (m :: Nat). WitnessZech p m -> [Zech p m]
enumerateZech Witness (Zech p m)
w
  witnessOf :: Zech p m -> Witness (Zech p m)
witnessOf        !Zech p m
x = case Zech p m
x of { Zech ZechTable
table Int32
_ -> forall (p :: Nat) (m :: Nat). ZechTable -> WitnessZech p m
WitnessZech ZechTable
table }
  embed :: Witness (Zech p m) -> Integer -> Zech p m
embed         !Witness (Zech p m)
w !Integer
x = forall (p :: Nat) (m :: Nat). WitnessZech p m -> Int -> Zech p m
embedZech Witness (Zech p m)
w (forall a. Num a => Integer -> a
fromInteger  Integer
x)
  embedSmall :: Witness (Zech p m) -> Int -> Zech p m
embedSmall    !Witness (Zech p m)
w !Int
x = forall (p :: Nat) (m :: Nat). WitnessZech p m -> Int -> Zech p m
embedZech Witness (Zech p m)
w Int
x
  randomFieldElem :: forall gen.
RandomGen gen =>
Witness (Zech p m) -> gen -> (Zech p m, gen)
randomFieldElem   Witness (Zech p m)
w = forall gen (p :: Nat) (m :: Nat).
RandomGen gen =>
WitnessZech p m -> gen -> (Zech p m, gen)
randomZech    Witness (Zech p m)
w
  randomInvertible :: forall gen.
RandomGen gen =>
Witness (Zech p m) -> gen -> (Zech p m, gen)
randomInvertible  Witness (Zech p m)
w = forall gen (p :: Nat) (m :: Nat).
RandomGen gen =>
WitnessZech p m -> gen -> (Zech p m, gen)
randomInvZech Witness (Zech p m)
w
  power :: Zech p m -> Integer -> Zech p m
power               = forall (p :: Nat) (m :: Nat). Zech p m -> Integer -> Zech p m
zechPow

  zero :: Witness (Zech p m) -> Zech p m
zero    (WitnessZech ZechTable
w) = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
w (-Int32
1)
  one :: Witness (Zech p m) -> Zech p m
one     (WitnessZech ZechTable
w) = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
w   Int32
0
  primGen :: Witness (Zech p m) -> Zech p m
primGen (WitnessZech ZechTable
w) = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
w   Int32
1
  isZero :: Zech p m -> Bool
isZero (Zech ZechTable
_ Int32
a) = Int32
a forall a. Eq a => a -> a -> Bool
== -Int32
1
  isOne :: Zech p m -> Bool
isOne  (Zech ZechTable
_ Int32
a) = Int32
a forall a. Eq a => a -> a -> Bool
== Int32
0

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

makeZechTable :: forall p m. WitnessGF p m -> ZechTable
makeZechTable :: forall (p :: Nat) (m :: Nat). WitnessGF p m -> ZechTable
makeZechTable WitnessGF p m
witness = (Int32, Int32)
-> Int32 -> Int32 -> Vector Int32 -> Vector Int32 -> ZechTable
ZechTable (Int32
p,Int32
m) Int32
qm1 Int32
e Vector Int32
embeds Vector Int32
zechlogs where
  g :: GF p m
g   = forall f. Field f => Witness f -> f
primGen WitnessGF p m
witness
  o :: GF p m
o   = forall f. Field f => Witness f -> f
one     WitnessGF p m
witness
  p :: Int32
p   = forall a. Num a => Integer -> a
fromInteger (forall f. Field f => Witness f -> Integer
characteristic WitnessGF p m
witness) :: Int32
  m :: Int32
m   = forall a. Num a => Integer -> a
fromInteger (forall f. Field f => Witness f -> Integer
dimension      WitnessGF p m
witness) :: Int32
  q :: Int32
q   = forall a. Num a => Integer -> a
fromInteger (forall f. Field f => Witness f -> Integer
fieldSize      WitnessGF p m
witness) :: Int32
  qm1 :: Int32
qm1 = Int32
q forall a. Num a => a -> a -> a
- Int32
1
  e :: Int32
e   = if Int32
p forall a. Eq a => a -> a -> Bool
== Int32
2 then Int32
0 else forall a. Integral a => a -> a -> a
Prelude.div Int32
qm1 Int32
2
  list :: [(GF p m, Int32)]
list = Int32 -> GF p m -> [(GF p m, Int32)]
worker Int32
0 (forall f. Field f => Witness f -> f
one WitnessGF p m
witness) :: [(GF p m, Int32)]
  dlog :: Map (GF p m) Int32
dlog = forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList [(GF p m, Int32)]
list
  worker :: Int32 -> GF p m -> [(GF p m, Int32)]
worker !Int32
e !GF p m
acc
    | Int32
e forall a. Ord a => a -> a -> Bool
< Int32
qm1    = (GF p m
acc,Int32
e) forall a. a -> [a] -> [a]
: Int32 -> GF p m -> [(GF p m, Int32)]
worker (Int32
eforall a. Num a => a -> a -> a
+Int32
1) (GF p m
accforall a. Num a => a -> a -> a
*GF p m
g)
    | Bool
otherwise  = []
  embeds :: Vector Int32
embeds   = forall a. Unbox a => [a] -> Vector a
Vec.fromList forall a b. (a -> b) -> a -> b
$ (-Int32
1) forall a. a -> [a] -> [a]
: [ forall k a. Ord k => Map k a -> k -> a
(Map.!) Map (GF p m) Int32
dlog (forall f. Field f => Witness f -> Int -> f
embedSmall WitnessGF p m
witness (forall a b. (Integral a, Num b) => a -> b
fromIntegral Int32
i)) | Int32
i<-[Int32
1..Int32
pforall a. Num a => a -> a -> a
-Int32
1] ]
  zechlogs :: Vector Int32
zechlogs = forall a. Unbox a => [a] -> Vector a
Vec.fromList forall a b. (a -> b) -> a -> b
$ {- 0 : -} [ forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault (-Int32
1) (GF p m
x forall a. Num a => a -> a -> a
+ GF p m
o) Map (GF p m) Int32
dlog | GF p m
x <- forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> a
fst [(GF p m, Int32)]
list ]

-- -- debugging 
-- printzech p m = case GF.mkGaloisField p m of 
--   Just (GF.SomeWitnessGF field) -> print (makeZechTable field)

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

embedZech :: WitnessZech p m -> Int -> Zech p m
embedZech :: forall (p :: Nat) (m :: Nat). WitnessZech p m -> Int -> Zech p m
embedZech (WitnessZech ZechTable
table) Int
k
  | Int
k forall a. Ord a => a -> a -> Bool
>= Int
0 Bool -> Bool -> Bool
&& Int
k forall a. Ord a => a -> a -> Bool
< Int
p  = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (forall a. Unbox a => Vector a -> Int -> a
Vec.unsafeIndex Vector Int32
embeds      Int
k   )
  | Bool
otherwise        = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (forall a. Unbox a => Vector a -> Int -> a
Vec.unsafeIndex Vector Int32
embeds (forall a. Integral a => a -> a -> a
mod Int
k Int
p)) 
  where
    p :: Int
p = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a b. (a, b) -> a
fst (ZechTable -> (Int32, Int32)
_zechParams ZechTable
table)) :: Int
    embeds :: Vector Int32
embeds = ZechTable -> Vector Int32
_embedding ZechTable
table

randomZech :: RandomGen gen => WitnessZech p m -> gen -> (Zech p m, gen)
randomZech :: forall gen (p :: Nat) (m :: Nat).
RandomGen gen =>
WitnessZech p m -> gen -> (Zech p m, gen)
randomZech (WitnessZech ZechTable
table) gen
g = case forall a g. (Random a, RandomGen g) => (a, a) -> g -> (a, g)
randomR (-Int32
1,ZechTable -> Int32
_qMinus1 ZechTable
tableforall a. Num a => a -> a -> a
-Int32
1) gen
g of
  (Int32
k,gen
g') -> (forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
k, gen
g')

randomInvZech :: RandomGen gen => WitnessZech p m -> gen -> (Zech p m, gen)
randomInvZech :: forall gen (p :: Nat) (m :: Nat).
RandomGen gen =>
WitnessZech p m -> gen -> (Zech p m, gen)
randomInvZech (WitnessZech ZechTable
table) gen
g = case forall a g. (Random a, RandomGen g) => (a, a) -> g -> (a, g)
randomR (Int32
0,ZechTable -> Int32
_qMinus1 ZechTable
tableforall a. Num a => a -> a -> a
-Int32
1) gen
g of
  (Int32
k,gen
g') -> (forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
k, gen
g')

enumerateZech :: WitnessZech p m -> [Zech p m]
enumerateZech :: forall (p :: Nat) (m :: Nat). WitnessZech p m -> [Zech p m]
enumerateZech (WitnessZech ZechTable
table) = [ forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
i | Int32
i<-[-Int32
1..Int32
nforall a. Num a => a -> a -> a
-Int32
1] ] where
  n :: Int32
n = ZechTable -> Int32
_qMinus1 ZechTable
table

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

zechNeg :: Zech p m -> Zech p m
zechNeg :: forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m
zechNeg (Zech ZechTable
table Int32
a)
  | Int32
a forall a. Eq a => a -> a -> Bool
== -Int32
1    = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a
  | Bool
otherwise  = let n :: Int32
n = ZechTable -> Int32
_qMinus1  ZechTable
table
                     c :: Int32
c = Int32
a forall a. Num a => a -> a -> a
+ (ZechTable -> Int32
_logMinus1 ZechTable
table)
                 in  if Int32
c forall a. Ord a => a -> a -> Bool
< Int32
n then forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
c else forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Int32
c forall a. Num a => a -> a -> a
- Int32
n)

zechAdd :: Zech p m -> Zech p m -> Zech p m 
zechAdd :: forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m -> Zech p m
zechAdd (Zech ZechTable
table Int32
a) (Zech ZechTable
_ Int32
b) 
  | Int32
a forall a. Eq a => a -> a -> Bool
== -Int32
1    = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
b     -- 0 + y
  | Int32
b forall a. Eq a => a -> a -> Bool
== -Int32
1    = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a     -- x + 0
  | Bool
otherwise  = let n :: Int32
n    = ZechTable -> Int32
_qMinus1  ZechTable
table
                     zech :: Vector Int32
zech = ZechTable -> Vector Int32
_zechLogs ZechTable
table
                     plusMod :: Int32 -> Int32
plusMod Int32
k = if Int32
k forall a. Ord a => a -> a -> Bool
< Int32
n then Int32
k else Int32
k forall a. Num a => a -> a -> a
- Int32
n
                 in  if Int32
a forall a. Ord a => a -> a -> Bool
>= Int32
b 
                       then let d :: Int32
d = forall a. Unbox a => Vector a -> Int -> a
Vec.unsafeIndex Vector Int32
zech (forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int32
a forall a. Num a => a -> a -> a
- Int32
b))
                            in  if Int32
d forall a. Ord a => a -> a -> Bool
< Int32
0 then forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
d 
                                         else forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Int32 -> Int32
plusMod (Int32
b forall a. Num a => a -> a -> a
+ Int32
d))
                       else let d :: Int32
d = forall a. Unbox a => Vector a -> Int -> a
Vec.unsafeIndex Vector Int32
zech (forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int32
b forall a. Num a => a -> a -> a
- Int32
a))
                            in  if Int32
d forall a. Ord a => a -> a -> Bool
< Int32
0 then forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
d 
                                         else forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Int32 -> Int32
plusMod (Int32
a forall a. Num a => a -> a -> a
+ Int32
d))

zechSub :: Zech p m -> Zech p m -> Zech p m 
zechSub :: forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m -> Zech p m
zechSub Zech p m
x Zech p m
y = forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m -> Zech p m
zechAdd Zech p m
x (forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m
zechNeg Zech p m
y)

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

zechMul :: Zech p m -> Zech p m -> Zech p m 
zechMul :: forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m -> Zech p m
zechMul (Zech ZechTable
table Int32
a) (Zech ZechTable
_ Int32
b) 
  | Int32
a forall a. Eq a => a -> a -> Bool
== -Int32
1    = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a     -- 0 * y
  | Int32
b forall a. Eq a => a -> a -> Bool
== -Int32
1    = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
b     -- y * 0
  | Bool
otherwise  = let n :: Int32
n = ZechTable -> Int32
_qMinus1 ZechTable
table
                     c :: Int32
c = Int32
a forall a. Num a => a -> a -> a
+ Int32
b
                 in  if Int32
c forall a. Ord a => a -> a -> Bool
< Int32
n then forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
c else forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Int32
c forall a. Num a => a -> a -> a
- Int32
n)

zechPow :: Zech p m -> Integer -> Zech p m 
zechPow :: forall (p :: Nat) (m :: Nat). Zech p m -> Integer -> Zech p m
zechPow z :: Zech p m
z@(Zech ZechTable
table Int32
a) Integer
e
  | Int32
a forall a. Eq a => a -> a -> Bool
== -Int32
1    = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a     -- 0^e = 0
  | Integer
e forall a. Eq a => a -> a -> Bool
== Integer
0     = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
0     -- x^0 = 1
  | Int32
a forall a. Eq a => a -> a -> Bool
== Int32
0     = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a     -- 1^e = 1
  | Bool
otherwise  = let n :: Integer
n = forall a b. (Integral a, Num b) => a -> b
fromIntegral (ZechTable -> Int32
_qMinus1 ZechTable
table) :: Integer
                     c :: Integer
c = forall a b. (Integral a, Num b) => a -> b
fromIntegral Int32
a forall a. Num a => a -> a -> a
* Integer
e            :: Integer
                 in  forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (forall a. Num a => Integer -> a
fromInteger (forall a. Integral a => a -> a -> a
mod Integer
c Integer
n))
  
zechInv :: Zech p m -> Zech p m 
zechInv :: forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m
zechInv (Zech ZechTable
table Int32
a)
  | Int32
a forall a. Eq a => a -> a -> Bool
== -Int32
1    = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a     -- 1 / 0 = undefined = 0 
  | Int32
a forall a. Eq a => a -> a -> Bool
==  Int32
0    = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a     -- 1 / 1 = 1 
  | Bool
otherwise  = let n :: Int32
n = ZechTable -> Int32
_qMinus1 ZechTable
table in  forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Int32
n forall a. Num a => a -> a -> a
- Int32
a)    -- we assume here that a > 0 !

zechDiv :: Zech p m -> Zech p m -> Zech p m 
zechDiv :: forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m -> Zech p m
zechDiv (Zech ZechTable
table Int32
a) (Zech ZechTable
_ Int32
b) 
  | Int32
a forall a. Eq a => a -> a -> Bool
== -Int32
1    = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a     -- 0 / x
  | Int32
b forall a. Eq a => a -> a -> Bool
== -Int32
1    = forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
b     -- x / 0
  | Bool
otherwise  = let n :: Int32
n = ZechTable -> Int32
_qMinus1 ZechTable
table
                     c :: Int32
c = Int32
a forall a. Num a => a -> a -> a
- Int32
b
                 in  if Int32
c forall a. Ord a => a -> a -> Bool
>= Int32
0 then forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
c else forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Int32
c forall a. Num a => a -> a -> a
+ Int32
n)

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