Math.FiniteField.GaloisField.Zech

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.

Tables of Zech logarithms

data ZechTable

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

Show ZechTable

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

Witness for the existence of the field

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

Constructors

WitnessZech

Fields

• fromWitnessZech :: ZechTable

Instances

Show (WitnessZech p m)

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

Constructors

forall p m. SomeWitnessZech (WitnessZech p m)

Instances

Show SomeWitnessZech

Defined in Math.FiniteField.GaloisField.Zech

Methods

showsPrec :: Int -> SomeWitnessZech -> ShowS

show :: SomeWitnessZech -> String

showList :: [SomeWitnessZech] -> ShowS

mkZechField :: Int -> Int -> Maybe SomeWitnessZech

unsafeZechField :: Int -> Int -> SomeWitnessZech

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

Field elements

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

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

Num (Zech p m)

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

Fractional (Zech p m)

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

Show (Zech p m)

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)

Defined in Math.FiniteField.GaloisField.Zech

Associated Types

type Witness (Zech p m) = (w :: Type)

type Prime (Zech p m) :: Nat

type Dim (Zech p m) :: Nat

Methods

characteristic :: Witness (Zech p m) -> Integer

dimension :: Witness (Zech p m) -> Integer

fieldSize :: Witness (Zech p m) -> Integer

zero :: Witness (Zech p m) -> Zech p m

one :: Witness (Zech p m) -> Zech p m

isZero :: Zech p m -> Bool

isOne :: Zech p m -> Bool

embed :: Witness (Zech p m) -> Integer -> Zech p m

embedSmall :: Witness (Zech p m) -> Int -> Zech p m

randomFieldElem :: RandomGen gen => Witness (Zech p m) -> gen -> (Zech p m, gen)

randomInvertible :: RandomGen gen => Witness (Zech p m) -> gen -> (Zech p m, gen)

primGen :: Witness (Zech p m) -> Zech p m

witnessOf :: Zech p m -> Witness (Zech p m)

power :: Zech p m -> Integer -> Zech p m

powerSmall :: Zech p m -> Int -> Zech p m

frobenius :: Zech p m -> Zech p m

enumerate :: Witness (Zech p m) -> [Zech p m]

Eq (Zech p m)

Defined in Math.FiniteField.GaloisField.Zech

Methods

(==) :: Zech p m -> Zech p m -> Bool

(/=) :: Zech p m -> Zech p m -> Bool

Ord (Zech p m)

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

type Dim (Zech p m)

Defined in Math.FiniteField.GaloisField.Zech

type Dim (Zech p m) = m

type Prime (Zech p m)

Defined in Math.FiniteField.GaloisField.Zech

type Prime (Zech p m) = p

type Witness (Zech p m)

Defined in Math.FiniteField.GaloisField.Zech

type Witness (Zech p m) = WitnessZech p 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)

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

Instances

Show (SubField p m k)

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

witness for the ambient field

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

witness for the existence of the subfield

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

proof that k divides m

fiberSize :: SubField p m k -> Int32

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

subFieldName :: SubField p m k -> String

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

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

Some subfield of GF(p,m)

Constructors

forall k. SomeSubField (SubField p m k)

Instances

Show (SomeSubField p m)

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

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