Safe Haskell	None
Language	Haskell2010

Math.FiniteField.GaloisField.Zech

Contents

Tables of Zech logarithms
Witness for the existence of the field
Field elements
Subfields

Description

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.

Synopsis

data ZechTable = ZechTable {
- _zechParams :: !(Int32, Int32)
- _qMinus1 :: !Int32
- _logMinus1 :: !Int32
- _embedding :: !(Vector Int32)
- _zechLogs :: !(Vector Int32)
}
makeZechTable :: forall p m. WitnessGF p m -> ZechTable
newtype WitnessZech (p :: Nat) (m :: Nat) = WitnessZech {
- fromWitnessZech :: ZechTable
}
data SomeWitnessZech = forall p m. SomeWitnessZech (WitnessZech p m)
mkZechField :: Int -> Int -> Maybe SomeWitnessZech
unsafeZechField :: Int -> Int -> SomeWitnessZech
constructZechField :: SNat64 p -> SNat64 m -> Maybe (WitnessZech p m)
data Zech (p :: Nat) (m :: Nat)
data SubField (p :: Nat) (m :: Nat) (k :: Nat)
ambientWitness :: SubField p m k -> WitnessZech p m
subFieldWitness :: SubField p m k -> WitnessZech p k
subFieldProof :: SubField p m k -> Divides k m
fiberSize :: SubField p m k -> Int32
subFieldName :: SubField p m k -> String
data SomeSubField (p :: Nat) (m :: Nat) = forall k. SomeSubField (SubField p m k)
constructSubField :: WitnessZech p m -> Divides k m -> SubField p m k
enumerateSubFields :: forall p m. WitnessZech p m -> [SomeSubField p m]
embedSubField :: SubField p m k -> Zech p k -> Zech p m
projectSubField :: SubField p m k -> Zech p m -> Maybe (Zech p k)
isInSubField :: SubField p m k -> Zech p m -> Bool

Tables of Zech logarithms

data ZechTable Source #

A table of Zech logarithms (and some more data required for the operations)

Constructors

ZechTable
Fields _zechParams :: !(Int32, Int32) the parameters `(p,m)` _qMinus1 :: !Int32 order of the multiplicative group `q-1 = p^m - 1` _logMinus1 :: !Int32 an integer `e` such that `g^e = -1` _embedding :: !(Vector Int32) embedding of `F_p` into `F_q` (including 0) _zechLogs :: !(Vector Int32) Zech's logarithms (except for 0; so the length is `q-1`)

Instances

Instances details

Show ZechTable Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech Methods showsPrec :: Int -> ZechTable -> ShowS # show :: ZechTable -> String # showList :: [ZechTable] -> ShowS #

makeZechTable :: forall p m. WitnessGF p m -> ZechTable Source #

Witness for the existence of the field

newtype WitnessZech (p :: Nat) (m :: Nat) Source #

Constructors

WitnessZech
Fields fromWitnessZech :: ZechTable

Instances

Instances details

Show (WitnessZech p m) Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech Methods showsPrec :: Int -> WitnessZech p m -> ShowS # show :: WitnessZech p m -> String # showList :: [WitnessZech p m] -> ShowS #

data SomeWitnessZech Source #

Constructors

forall p m. SomeWitnessZech (WitnessZech p m)

Instances

Instances details

Show SomeWitnessZech Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech Methods showsPrec :: Int -> SomeWitnessZech -> ShowS # show :: SomeWitnessZech -> String # showList :: [SomeWitnessZech] -> ShowS #

mkZechField :: Int -> Int -> Maybe SomeWitnessZech Source #

unsafeZechField :: Int -> Int -> SomeWitnessZech Source #

constructZechField :: SNat64 p -> SNat64 m -> Maybe (WitnessZech p m) Source #

Field elements

data Zech (p :: Nat) (m :: Nat) Source #

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

Instances

Instances details

Eq (Zech p m) Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech Methods (==) :: Zech p m -> Zech p m -> Bool # (/=) :: Zech p m -> Zech p m -> Bool #
Fractional (Zech p m) Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech Methods (/) :: Zech p m -> Zech p m -> Zech p m # recip :: Zech p m -> Zech p m # fromRational :: Rational -> Zech p m #
Num (Zech p m) Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech Methods (+) :: Zech p m -> Zech p m -> Zech p m # (-) :: Zech p m -> Zech p m -> Zech p m # (*) :: Zech p m -> Zech p m -> Zech p m # negate :: Zech p m -> Zech p m # abs :: Zech p m -> Zech p m # signum :: Zech p m -> Zech p m # fromInteger :: Integer -> Zech p m #
Ord (Zech p m) Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech Methods compare :: Zech p m -> Zech p m -> Ordering # (<) :: Zech p m -> Zech p m -> Bool # (<=) :: Zech p m -> Zech p m -> Bool # (>) :: Zech p m -> Zech p m -> Bool # (>=) :: Zech p m -> Zech p m -> Bool # max :: Zech p m -> Zech p m -> Zech p m # min :: Zech p m -> Zech p m -> Zech p m #
Show (Zech p m) Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech Methods showsPrec :: Int -> Zech p m -> ShowS # show :: Zech p m -> String # showList :: [Zech p m] -> ShowS #
Field (Zech p m) Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech Associated Types type Witness (Zech p m) = (w :: Type) Source # type Prime (Zech p m) :: Nat Source # type Dim (Zech p m) :: Nat Source # Methods characteristic :: Witness (Zech p m) -> Integer Source # dimension :: Witness (Zech p m) -> Integer Source # fieldSize :: Witness (Zech p m) -> Integer Source # zero :: Witness (Zech p m) -> Zech p m Source # one :: Witness (Zech p m) -> Zech p m Source # isZero :: Zech p m -> Bool Source # isOne :: Zech p m -> Bool Source # embed :: Witness (Zech p m) -> Integer -> Zech p m Source # embedSmall :: Witness (Zech p m) -> Int -> Zech p m Source # randomFieldElem :: RandomGen gen => Witness (Zech p m) -> gen -> (Zech p m, gen) Source # randomInvertible :: RandomGen gen => Witness (Zech p m) -> gen -> (Zech p m, gen) Source # primGen :: Witness (Zech p m) -> Zech p m Source # witnessOf :: Zech p m -> Witness (Zech p m) Source # power :: Zech p m -> Integer -> Zech p m Source # powerSmall :: Zech p m -> Int -> Zech p m Source # frobenius :: Zech p m -> Zech p m Source # enumerate :: Witness (Zech p m) -> [Zech p m] Source #
type Witness (Zech p m) Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech type Witness (Zech p m) = WitnessZech p m
type Prime (Zech p m) Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech type Prime (Zech p m) = p
type Dim (Zech p m) Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech type Dim (Zech p m) = m

Subfields

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.

data SubField (p :: Nat) (m :: Nat) (k :: Nat) Source #

A witness for the subfield GF(p,k) of GF(p,m)

Instances

Instances details

Show (SubField p m k) Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech Methods showsPrec :: Int -> SubField p m k -> ShowS # show :: SubField p m k -> String # showList :: [SubField p m k] -> ShowS #

ambientWitness :: SubField p m k -> WitnessZech p m Source #

witness for the ambient field

subFieldWitness :: SubField p m k -> WitnessZech p k Source #

witness for the existence of the subfield

subFieldProof :: SubField p m k -> Divides k m Source #

proof that k divides m

fiberSize :: SubField p m k -> Int32 Source #

the quotient (p^m-1)/(p^k-1)

subFieldName :: SubField p m k -> String Source #

Returns something like "GF(p^3) ⊆ GF(p^6)"

data SomeSubField (p :: Nat) (m :: Nat) Source #

Some subfield of GF(p,m)

Constructors

forall k. SomeSubField (SubField p m k)

Instances

Instances details

Show (SomeSubField p m) Source #
Instance details Defined in Math.FiniteField.GaloisField.Zech Methods showsPrec :: Int -> SomeSubField p m -> ShowS # show :: SomeSubField p m -> String # showList :: [SomeSubField p m] -> ShowS #

constructSubField :: WitnessZech p m -> Divides k m -> SubField p m k Source #

enumerateSubFields :: forall p m. WitnessZech p m -> [SomeSubField p m] Source #

embedSubField :: SubField p m k -> Zech p k -> Zech p m Source #

projectSubField :: SubField p m k -> Zech p m -> Maybe (Zech p k) Source #

isInSubField :: SubField p m k -> Zech p m -> Bool Source #