{-# LANGUAGE BangPatterns, ScopedTypeVariables, TypeFamilies #-}
{-# LANGUAGE StandaloneDeriving, ExistentialQuantification #-}
module Math.FiniteField.GaloisField.Zech
(
ZechTable(..)
, makeZechTable
, WitnessZech(..)
, SomeWitnessZech(..)
, mkZechField
, unsafeZechField
, constructZechField
, Zech
, SubField , ambientWitness , subFieldWitness , subFieldProof , fiberSize
, subFieldName
, SomeSubField(..)
, constructSubField , enumerateSubFields
, embedSubField
, projectSubField
, isInSubField
)
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
data ZechTable = ZechTable
{ ZechTable -> (Int32, Int32)
_zechParams :: !(Int32,Int32)
, ZechTable -> Int32
_qMinus1 :: !Int32
, ZechTable -> Int32
_logMinus1 :: !Int32
, ZechTable -> Vector Int32
_embedding :: !(Vector Int32)
, ZechTable -> Vector Int32
_zechLogs :: !(Vector Int32)
}
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))
data SubField (p :: Nat) (m :: Nat) (k :: Nat) = SubField
{ SubField p m k -> WitnessZech p m
ambientWitness :: !(WitnessZech p m)
, SubField p m k -> WitnessZech p k
subFieldWitness :: !(WitnessZech p k)
, SubField p m k -> Divides k m
subFieldProof :: !(Divides k m)
, SubField p m k -> Int32
fiberSize :: !Int32
}
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
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)
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
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??"
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
$ [ 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 ]
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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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)
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
| 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
| 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)