-- | 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
(Int -> ZechTable -> ShowS)
-> (ZechTable -> String)
-> ([ZechTable] -> ShowS)
-> Show ZechTable
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 { WitnessZech p m -> ZechTable
fromWitnessZech :: ZechTable }
  deriving Int -> WitnessZech p m -> ShowS
[WitnessZech p m] -> ShowS
WitnessZech p m -> String
(Int -> WitnessZech p m -> ShowS)
-> (WitnessZech p m -> String)
-> ([WitnessZech p m] -> ShowS)
-> Show (WitnessZech p m)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
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
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   -> Maybe SomeWitnessZech
forall a. Maybe a
Nothing
  Just SomeWitnessGF
some -> case SomeWitnessGF
some of
    GF.SomeWitnessGF WitnessGF p m
wgf -> SomeWitnessZech -> Maybe SomeWitnessZech
forall a. a -> Maybe a
Just (WitnessZech Any Any -> SomeWitnessZech
forall (p :: Nat) (m :: Nat). WitnessZech p m -> SomeWitnessZech
SomeWitnessZech (ZechTable -> WitnessZech Any Any
forall (p :: Nat) (m :: Nat). ZechTable -> WitnessZech p m
WitnessZech (WitnessGF p m -> ZechTable
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   -> String -> SomeWitnessZech
forall a. HasCallStack => String -> a
error (String -> SomeWitnessZech) -> String -> SomeWitnessZech
forall a b. (a -> b) -> a -> b
$ String
"unsafeZechField: 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 SomeWitnessZech
some -> SomeWitnessZech
some

constructZechField :: SNat64 p -> SNat64 m -> Maybe (WitnessZech p m)
constructZechField :: SNat64 p -> SNat64 m -> Maybe (WitnessZech p m)
constructZechField SNat64 p
sp SNat64 m
sm = case SNat64 p -> SNat64 m -> Maybe (WitnessGF p m)
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   -> Maybe (WitnessZech p m)
forall a. Maybe a
Nothing
  Just WitnessGF p m
wgf  -> WitnessZech p m -> Maybe (WitnessZech p m)
forall a. a -> Maybe a
Just (ZechTable -> WitnessZech p m
forall (p :: Nat) (m :: Nat). ZechTable -> WitnessZech p m
WitnessZech (WitnessGF p m -> ZechTable
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
  { SubField p m k -> WitnessZech p m
ambientWitness  :: !(WitnessZech p m)  -- ^ witness for the ambient field
  , SubField p m k -> WitnessZech p k
subFieldWitness :: !(WitnessZech p k)  -- ^ witness for the existence of the subfield
  , SubField p m k -> Divides k m
subFieldProof   :: !(Divides k m)      -- ^ proof that @k@ divides @m@
  , SubField p m k -> Int32
fiberSize       :: !Int32              -- ^ the quotient @(p^m-1)/(p^k-1)@
  }
  deriving Int -> SubField p m k -> ShowS
[SubField p m k] -> ShowS
SubField p m k -> String
(Int -> SubField p m k -> ShowS)
-> (SubField p m k -> String)
-> ([SubField p m k] -> ShowS)
-> Show (SubField p m k)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
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
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 :: SubField p m k -> String
subFieldName SubField p m k
w = Witness (Zech p k) -> String
forall f. Field f => Witness f -> String
fieldName (SubField p m k -> WitnessZech p k
forall (p :: Nat) (m :: Nat) (k :: Nat).
SubField p m k -> WitnessZech p k
subFieldWitness SubField p m k
w) String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" ⊆ " String -> ShowS
forall a. [a] -> [a] -> [a]
++   Witness (Zech p m) -> String
forall f. Field f => Witness f -> String
fieldName (SubField p m k -> WitnessZech p m
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 :: WitnessZech p m -> Divides k m -> SubField p m k
constructSubField WitnessZech p m
ambientw Divides k m
proof = 
  case SNat64 p -> SNat64 k -> Maybe (WitnessZech p k)
forall (p :: Nat) (m :: Nat).
SNat64 p -> SNat64 m -> Maybe (WitnessZech p m)
constructZechField (Witness (Zech p m) -> SNat64 (Prime (Zech p m))
forall f. Field f => Witness f -> SNat64 (Prime f)
fieldPrimeSNat64 Witness (Zech p m)
WitnessZech p m
ambientw) (Divides k m -> SNat64 k
forall (k :: Nat) (n :: Nat). Divides k n -> SNat64 k
divisorSNat Divides k m
proof) of
    Maybe (WitnessZech p k)
Nothing    -> String -> SubField p m k
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  -> (WitnessZech p m
-> WitnessZech p k -> Divides k m -> Int32 -> SubField p m k
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 = Witness (Zech p m) -> Integer
forall f. Field f => Witness f -> Integer
characteristic Witness (Zech p m)
WitnessZech p m
ambientw
      m :: Integer
m = Witness (Zech p m) -> Integer
forall f. Field f => Witness f -> Integer
dimension      Witness (Zech p m)
WitnessZech p m
ambientw
      k :: Word64
k = Divides k m -> Word64
forall (k :: Nat) (n :: Nat). Divides k n -> Word64
_divisor       Divides k m
proof
      d :: Int32
d = Int32 -> Int32 -> Int32
forall a. Integral a => a -> a -> a
div (Integer -> Int32
forall a. Num a => Integer -> a
fromInteger Integer
p Int32 -> Integer -> Int32
forall a b. (Num a, Integral b) => a -> b -> a
^ Integer
m Int32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
- Int32
1) (Integer -> Int32
forall a. Num a => Integer -> a
fromInteger Integer
p Int32 -> Word64 -> Int32
forall a b. (Num a, Integral b) => a -> b -> a
^ Word64
k Int32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
- Int32
1)

constructSubField_ :: WitnessZech p m -> SNat64 k -> Maybe (SubField p m k)
constructSubField_ :: WitnessZech p m -> SNat64 k -> Maybe (SubField p m k)
constructSubField_ WitnessZech p m
ambientw sk :: SNat64 k
sk@(SNat64 Word64
k) =
  case SNat64 k -> SNat64 m -> Maybe (Divides k m)
forall (k :: Nat) (n :: Nat).
SNat64 k -> SNat64 n -> Maybe (Divides k n)
divides SNat64 k
sk (Witness (Zech p m) -> SNat64 (Dim (Zech p m))
forall f. Field f => Witness f -> SNat64 (Dim f)
fieldDimSNat64 Witness (Zech p m)
WitnessZech p m
ambientw) of
    Maybe (Divides k m)
Nothing    -> Maybe (SubField p m k)
forall a. Maybe a
Nothing
    Just Divides k m
proof -> SubField p m k -> Maybe (SubField p m k)
forall a. a -> Maybe a
Just (WitnessZech p m -> Divides k m -> SubField p m k
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 :: WitnessZech p m -> [SomeSubField p m]
enumerateSubFields WitnessZech p m
ambientw = (Divisor m -> SomeSubField p m)
-> [Divisor m] -> [SomeSubField p m]
forall a b. (a -> b) -> [a] -> [b]
map Divisor m -> SomeSubField p m
construct (SNat64 m -> [Divisor m]
forall (n :: Nat). SNat64 n -> [Divisor n]
divisors (Witness (Zech p m) -> SNat64 (Dim (Zech p m))
forall f. Field f => Witness f -> SNat64 (Dim f)
fieldDimSNat64 Witness (Zech p m)
WitnessZech p m
ambientw)) where
  construct :: Divisor m -> SomeSubField p m
construct (Divisor Divides k m
proof) = SubField p m k -> SomeSubField p m
forall (p :: Nat) (m :: Nat) (k :: Nat).
SubField p m k -> SomeSubField p m
SomeSubField (WitnessZech p m -> Divides k m -> SubField p m k
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)

embedSubField :: SubField p m k -> Zech p k -> Zech p m
embedSubField :: 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 Int32 -> Int32 -> Bool
forall a. Ord a => a -> a -> Bool
< Int32
0      = ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech (WitnessZech p m -> ZechTable
forall (p :: Nat) (m :: Nat). WitnessZech p m -> ZechTable
fromWitnessZech WitnessZech p m
aw)  Int32
a
  | Bool
otherwise  = ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech (WitnessZech p m -> ZechTable
forall (p :: Nat) (m :: Nat). WitnessZech p m -> ZechTable
fromWitnessZech WitnessZech p m
aw) (Int32
aInt32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
*Int32
d)

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

isInSubField :: SubField p m k -> Zech p m -> Bool
isInSubField :: 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 Int32 -> Int32 -> Bool
forall a. Ord a => a -> a -> Bool
< Int32
0      = Bool
True
  | Bool
otherwise  = Int32 -> Int32 -> Int32
forall a. Integral a => a -> a -> a
mod Int32
a Int32
d Int32 -> Int32 -> Bool
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 :: SubField p m k -> Zech p m -> [Zech p k]
subFieldCoordinates = String -> SubField p m k -> Zech p m -> [Zech p k]
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 Int32 -> Int32 -> Bool
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) = Int32 -> Int32 -> Ordering
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 Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
== -Int32
1    = String
"0"
    | Int32
n Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
==  Int32
0    = String
"1"
    | Int32
n Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
==  Int32
1    = String
"g"
    | Bool
otherwise  = String
"g^" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Int32 -> String
forall a. Show a => a -> String
show Int32
n

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

instance Fractional (Zech p m) where
  fromRational :: Rational -> Zech p m
fromRational = String -> Rational -> Zech p m
forall a. HasCallStack => String -> a
error String
"GaloisField/Zech/fromRational: cannot be defined; use `embed` instead!"
  recip :: Zech p m -> Zech p m
recip = Zech p m -> Zech p m
forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m
zechInv
  / :: Zech p m -> Zech p m -> Zech p m
(/)   = 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 !w) = Int32 -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral ((Int32, Int32) -> Int32
forall a b. (a, b) -> a
fst (ZechTable -> (Int32, Int32)
_zechParams ZechTable
w))
  dimension :: Witness (Zech p m) -> Integer
dimension      (WitnessZech !w) = Int32 -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral ((Int32, Int32) -> Int32
forall a b. (a, b) -> b
snd (ZechTable -> (Int32, Int32)
_zechParams ZechTable
w))
  fieldSize :: Witness (Zech p m) -> Integer
fieldSize      (WitnessZech !w) = case ZechTable -> (Int32, Int32)
_zechParams ZechTable
w of (Int32
p,Int32
m) -> (Int32 -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int32
p :: Integer) Integer -> Int32 -> 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 = WitnessZech p m -> [Zech p m]
forall (p :: Nat) (m :: Nat). WitnessZech p m -> [Zech p m]
enumerateZech Witness (Zech p m)
WitnessZech 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
_ -> ZechTable -> WitnessZech p m
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 = WitnessZech p m -> Int -> Zech p m
forall (p :: Nat) (m :: Nat). WitnessZech p m -> Int -> Zech p m
embedZech Witness (Zech p m)
WitnessZech p m
w (Integer -> Int
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 = WitnessZech p m -> Int -> Zech p m
forall (p :: Nat) (m :: Nat). WitnessZech p m -> Int -> Zech p m
embedZech Witness (Zech p m)
WitnessZech p m
w Int
x
  randomFieldElem :: Witness (Zech p m) -> gen -> (Zech p m, gen)
randomFieldElem   Witness (Zech p m)
w = WitnessZech p m -> gen -> (Zech p m, gen)
forall gen (p :: Nat) (m :: Nat).
RandomGen gen =>
WitnessZech p m -> gen -> (Zech p m, gen)
randomZech    Witness (Zech p m)
WitnessZech p m
w
  randomInvertible :: Witness (Zech p m) -> gen -> (Zech p m, gen)
randomInvertible  Witness (Zech p m)
w = WitnessZech p m -> gen -> (Zech p m, gen)
forall gen (p :: Nat) (m :: Nat).
RandomGen gen =>
WitnessZech p m -> gen -> (Zech p m, gen)
randomInvZech Witness (Zech p m)
WitnessZech p m
w
  power :: Zech p m -> Integer -> Zech p m
power               = Zech p m -> Integer -> Zech p m
forall (p :: Nat) (m :: Nat). Zech p m -> Integer -> Zech p m
zechPow

  zero :: Witness (Zech p m) -> Zech p m
zero    (WitnessZech w) = ZechTable -> Int32 -> Zech p m
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 w) = ZechTable -> Int32 -> Zech p m
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 w) = ZechTable -> Int32 -> Zech p m
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 Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
== -Int32
1
  isOne :: Zech p m -> Bool
isOne  (Zech ZechTable
_ Int32
a) = Int32
a Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
== Int32
0

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

makeZechTable :: forall p m. WitnessGF p m -> ZechTable
makeZechTable :: 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   = Witness (GF p m) -> GF p m
forall f. Field f => Witness f -> f
primGen Witness (GF p m)
WitnessGF p m
witness
  o :: GF p m
o   = Witness (GF p m) -> GF p m
forall f. Field f => Witness f -> f
one     Witness (GF p m)
WitnessGF p m
witness
  p :: Int32
p   = Integer -> Int32
forall a. Num a => Integer -> a
fromInteger (Witness (GF p m) -> Integer
forall f. Field f => Witness f -> Integer
characteristic Witness (GF p m)
WitnessGF p m
witness) :: Int32
  m :: Int32
m   = Integer -> Int32
forall a. Num a => Integer -> a
fromInteger (Witness (GF p m) -> Integer
forall f. Field f => Witness f -> Integer
dimension      Witness (GF p m)
WitnessGF p m
witness) :: Int32
  q :: Int32
q   = Integer -> Int32
forall a. Num a => Integer -> a
fromInteger (Witness (GF p m) -> Integer
forall f. Field f => Witness f -> Integer
fieldSize      Witness (GF p m)
WitnessGF p m
witness) :: Int32
  qm1 :: Int32
qm1 = Int32
q Int32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
- Int32
1
  e :: Int32
e   = if Int32
p Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
== Int32
2 then Int32
0 else Int32 -> Int32 -> Int32
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 (Witness (GF p m) -> GF p m
forall f. Field f => Witness f -> f
one Witness (GF p m)
WitnessGF p m
witness) :: [(GF p m, Int32)]
  dlog :: Map (GF p m) Int32
dlog = [(GF p m, Int32)] -> Map (GF p m) Int32
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 Int32 -> Int32 -> Bool
forall a. Ord a => a -> a -> Bool
< Int32
qm1    = (GF p m
acc,Int32
e) (GF p m, Int32) -> [(GF p m, Int32)] -> [(GF p m, Int32)]
forall a. a -> [a] -> [a]
: Int32 -> GF p m -> [(GF p m, Int32)]
worker (Int32
eInt32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
+Int32
1) (GF p m
accGF p m -> GF p m -> GF p m
forall a. Num a => a -> a -> a
*GF p m
g)
    | Bool
otherwise  = []
  embeds :: Vector Int32
embeds   = [Int32] -> Vector Int32
forall a. Unbox a => [a] -> Vector a
Vec.fromList ([Int32] -> Vector Int32) -> [Int32] -> Vector Int32
forall a b. (a -> b) -> a -> b
$ (-Int32
1) Int32 -> [Int32] -> [Int32]
forall a. a -> [a] -> [a]
: [ Map (GF p m) Int32 -> GF p m -> Int32
forall k a. Ord k => Map k a -> k -> a
(Map.!) Map (GF p m) Int32
dlog (Witness (GF p m) -> Int -> GF p m
forall f. Field f => Witness f -> Int -> f
embedSmall Witness (GF p m)
WitnessGF p m
witness (Int32 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int32
i)) | Int32
i<-[Int32
1..Int32
pInt32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
-Int32
1] ]
  zechlogs :: Vector Int32
zechlogs = [Int32] -> Vector Int32
forall a. Unbox a => [a] -> Vector a
Vec.fromList ([Int32] -> Vector Int32) -> [Int32] -> Vector Int32
forall a b. (a -> b) -> a -> b
$ {- 0 : -} [ Int32 -> GF p m -> Map (GF p m) Int32 -> Int32
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault (-Int32
1) (GF p m
x GF p m -> GF p m -> GF p m
forall a. Num a => a -> a -> a
+ GF p m
o) Map (GF p m) Int32
dlog | GF p m
x <- ((GF p m, Int32) -> GF p m) -> [(GF p m, Int32)] -> [GF p m]
forall a b. (a -> b) -> [a] -> [b]
map (GF p m, Int32) -> GF p m
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 :: WitnessZech p m -> Int -> Zech p m
embedZech (WitnessZech ZechTable
table) Int
k
  | Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 Bool -> Bool -> Bool
&& Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
p  = ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Vector Int32 -> Int -> Int32
forall a. Unbox a => Vector a -> Int -> a
Vec.unsafeIndex Vector Int32
embeds      Int
k   )
  | Bool
otherwise        = ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Vector Int32 -> Int -> Int32
forall a. Unbox a => Vector a -> Int -> a
Vec.unsafeIndex Vector Int32
embeds (Int -> Int -> Int
forall a. Integral a => a -> a -> a
mod Int
k Int
p)) 
  where
    p :: Int
p = Int32 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral ((Int32, Int32) -> Int32
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 :: WitnessZech p m -> gen -> (Zech p m, gen)
randomZech (WitnessZech ZechTable
table) gen
g = case (Int32, Int32) -> gen -> (Int32, gen)
forall a g. (Random a, RandomGen g) => (a, a) -> g -> (a, g)
randomR (-Int32
1,ZechTable -> Int32
_qMinus1 ZechTable
tableInt32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
-Int32
1) gen
g of
  (Int32
k,gen
g') -> (ZechTable -> Int32 -> Zech p m
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 :: WitnessZech p m -> gen -> (Zech p m, gen)
randomInvZech (WitnessZech ZechTable
table) gen
g = case (Int32, Int32) -> gen -> (Int32, gen)
forall a g. (Random a, RandomGen g) => (a, a) -> g -> (a, g)
randomR (Int32
0,ZechTable -> Int32
_qMinus1 ZechTable
tableInt32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
-Int32
1) gen
g of
  (Int32
k,gen
g') -> (ZechTable -> Int32 -> Zech p m
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 :: WitnessZech p m -> [Zech p m]
enumerateZech (WitnessZech ZechTable
table) = [ ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
i | Int32
i<-[-Int32
1..Int32
nInt32 -> Int32 -> Int32
forall 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 :: Zech p m -> Zech p m
zechNeg (Zech ZechTable
table Int32
a)
  | Int32
a Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
== -Int32
1    = ZechTable -> Int32 -> Zech p m
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 Int32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
+ (ZechTable -> Int32
_logMinus1 ZechTable
table)
                 in  if Int32
c Int32 -> Int32 -> Bool
forall a. Ord a => a -> a -> Bool
< Int32
n then ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
c else ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Int32
c Int32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
- Int32
n)

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

zechSub :: Zech p m -> Zech p m -> Zech p m 
zechSub :: Zech p m -> Zech p m -> Zech p m
zechSub Zech p m
x Zech p m
y = Zech p m -> Zech p m -> Zech p m
forall (p :: Nat) (m :: Nat). Zech p m -> Zech p m -> Zech p m
zechAdd Zech p m
x (Zech p m -> Zech p m
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 :: Zech p m -> Zech p m -> Zech p m
zechMul (Zech ZechTable
table Int32
a) (Zech ZechTable
_ Int32
b) 
  | Int32
a Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
== -Int32
1    = ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a     -- 0 * y
  | Int32
b Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
== -Int32
1    = ZechTable -> Int32 -> Zech p m
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 Int32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
+ Int32
b
                 in  if Int32
c Int32 -> Int32 -> Bool
forall a. Ord a => a -> a -> Bool
< Int32
n then ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
c else ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Int32
c Int32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
- Int32
n)

zechPow :: Zech p m -> Integer -> Zech p m 
zechPow :: Zech p m -> Integer -> Zech p m
zechPow z :: Zech p m
z@(Zech ZechTable
table Int32
a) Integer
e
  | Int32
a Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
== -Int32
1    = ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a     -- 0^e = 0
  | Integer
e Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0     = ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
0     -- x^0 = 1
  | Int32
a Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
== Int32
0     = ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a     -- 1^e = 1
  | Bool
otherwise  = let n :: Integer
n = Int32 -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (ZechTable -> Int32
_qMinus1 ZechTable
table) :: Integer
                     c :: Integer
c = Int32 -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int32
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
e            :: Integer
                 in  ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Integer -> Int32
forall a. Num a => Integer -> a
fromInteger (Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
mod Integer
c Integer
n))
  
zechInv :: Zech p m -> Zech p m 
zechInv :: Zech p m -> Zech p m
zechInv (Zech ZechTable
table Int32
a)
  | Int32
a Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
== -Int32
1    = ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a     -- 1 / 0 = undefined = 0 
  | Int32
a Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
==  Int32
0    = ZechTable -> Int32 -> Zech p m
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  ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Int32
n Int32 -> Int32 -> Int32
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 :: Zech p m -> Zech p m -> Zech p m
zechDiv (Zech ZechTable
table Int32
a) (Zech ZechTable
_ Int32
b) 
  | Int32
a Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
== -Int32
1    = ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
a     -- 0 / x
  | Int32
b Int32 -> Int32 -> Bool
forall a. Eq a => a -> a -> Bool
== -Int32
1    = ZechTable -> Int32 -> Zech p m
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 Int32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
- Int32
b
                 in  if Int32
c Int32 -> Int32 -> Bool
forall a. Ord a => a -> a -> Bool
>= Int32
0 then ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table Int32
c else ZechTable -> Int32 -> Zech p m
forall (p :: Nat) (m :: Nat). ZechTable -> Int32 -> Zech p m
Zech ZechTable
table (Int32
c Int32 -> Int32 -> Int32
forall a. Num a => a -> a -> a
+ Int32
n)

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