finite-fields-0.2: Arithmetic in finite fields
Safe HaskellNone
LanguageHaskell2010

Math.FiniteField.GaloisField.Zech

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

Tables of Zech logarithms

data ZechTable Source #

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

Constructors

ZechTable 

Fields

Instances

Instances details
Show ZechTable Source # 
Instance details

Defined in Math.FiniteField.GaloisField.Zech

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 

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

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

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 #