-- | 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@ 
--
-- TODO: also export the tables to C, and write C implementation of
-- of the field operations.
--

{-# 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
    -- * Field elements
  , Zech
  )
  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.GaloisField.Small ( GF , WitnessGF )
import qualified Math.FiniteField.GaloisField.Small as GF

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

data ZechTable = ZechTable
  { ZechTable -> (Int32, Int32)
_zechParams :: !(Int32,Int32)     -- ^ @(p,m)@
  , ZechTable -> Int32
_qMinus1    :: !Int32             -- ^ @p^m-1 = q-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 0)
  }
  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

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

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

  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)

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