Math.FiniteField.Class

Type class interface to different implementations of finite fields

Fields

class (Eq f, Ord f, Show f, Num f, Fractional f, Show (Witness f)) => Field f where

A class for field element types

Minimal complete definition

characteristic, dimension, isZero, isOne, embed, randomFieldElem, primGen, witnessOf, enumerate

Associated Types

type Witness f = w | w -> f

witness for the existence of the field (this is an injective type family!)

type Prime f :: Nat

the characteristic at type level

type Dim f :: Nat

the dimension at type level

Methods

characteristic :: Witness f -> Integer

the prime characteristic

dimension :: Witness f -> Integer

dimension over the prime field (the exponent m in q=p^m)

fieldSize :: Witness f -> Integer

the size (or order) of the field

zero :: Witness f -> f

The additive identity of the field

one :: Witness f -> f

The multiplicative identity of the field

isZero :: f -> Bool

check for equality with the additive identity

isOne :: f -> Bool

check for equality with the multiplicative identity

embed :: Witness f -> Integer -> f

an element of the prime field

embedSmall :: Witness f -> Int -> f

randomFieldElem :: RandomGen gen => Witness f -> gen -> (f, gen)

a uniformly random field element

randomInvertible :: RandomGen gen => Witness f -> gen -> (f, gen)

a random invertible element

primGen :: Witness f -> f

a primitive generator

witnessOf :: f -> Witness f

extract the witness from a field element

power :: f -> Integer -> f

exponentiation

powerSmall :: f -> Int -> f

frobenius :: f -> f

Frobenius automorphism x -> x^p

enumerate :: Witness f -> [f]

list of field elements (of course it's only useful for very small fields)

Instances

Field (Fp p)

Defined in Math.FiniteField.PrimeField.Generic

Associated Types

type Witness (Fp p) = (w :: Type)

type Prime (Fp p) :: Nat

type Dim (Fp p) :: Nat

Methods

characteristic :: Witness (Fp p) -> Integer

dimension :: Witness (Fp p) -> Integer

fieldSize :: Witness (Fp p) -> Integer

zero :: Witness (Fp p) -> Fp p

one :: Witness (Fp p) -> Fp p

isZero :: Fp p -> Bool

isOne :: Fp p -> Bool

embed :: Witness (Fp p) -> Integer -> Fp p

embedSmall :: Witness (Fp p) -> Int -> Fp p

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

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

primGen :: Witness (Fp p) -> Fp p

witnessOf :: Fp p -> Witness (Fp p)

power :: Fp p -> Integer -> Fp p

powerSmall :: Fp p -> Int -> Fp p

frobenius :: Fp p -> Fp p

enumerate :: Witness (Fp p) -> [Fp p]

Field (Fp p)

Defined in Math.FiniteField.PrimeField.Small

Associated Types

type Witness (Fp p) = (w :: Type)

type Prime (Fp p) :: Nat

type Dim (Fp p) :: Nat

Methods

characteristic :: Witness (Fp p) -> Integer

dimension :: Witness (Fp p) -> Integer

fieldSize :: Witness (Fp p) -> Integer

zero :: Witness (Fp p) -> Fp p

one :: Witness (Fp p) -> Fp p

isZero :: Fp p -> Bool

isOne :: Fp p -> Bool

embed :: Witness (Fp p) -> Integer -> Fp p

embedSmall :: Witness (Fp p) -> Int -> Fp p

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

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

primGen :: Witness (Fp p) -> Fp p

witnessOf :: Fp p -> Witness (Fp p)

power :: Fp p -> Integer -> Fp p

powerSmall :: Fp p -> Int -> Fp p

frobenius :: Fp p -> Fp p

enumerate :: Witness (Fp p) -> [Fp p]

Field (GF p m)

Defined in Math.FiniteField.GaloisField.Small

Associated Types

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

type Prime (GF p m) :: Nat

type Dim (GF p m) :: Nat

Methods

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

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

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

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

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

isZero :: GF p m -> Bool

isOne :: GF p m -> Bool

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

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

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

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

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

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

power :: GF p m -> Integer -> GF p m

powerSmall :: GF p m -> Int -> GF p m

frobenius :: GF p m -> GF p m

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

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]

Field (CFq p m)

Defined in Math.FiniteField.GaloisField.Zech.C

Associated Types

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

type Prime (CFq p m) :: Nat

type Dim (CFq p m) :: Nat

Methods

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

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

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

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

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

isZero :: CFq p m -> Bool

isOne :: CFq p m -> Bool

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

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

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

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

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

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

power :: CFq p m -> Integer -> CFq p m

powerSmall :: CFq p m -> Int -> CFq p m

frobenius :: CFq p m -> CFq p m

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

fieldPrimeSNat :: Field f => Witness f -> SNat (Prime f)

fieldPrimeSNat64 :: Field f => Witness f -> SNat64 (Prime f)

fieldDimSNat :: Field f => Witness f -> SNat (Dim f)

fieldDimSNat64 :: Field f => Witness f -> SNat64 (Dim f)

data SomeField

Constructors

forall f.Field f => SomeField (Witness f)

Instances

Show SomeField

Defined in Math.FiniteField.Class

Methods

showsPrec :: Int -> SomeField -> ShowS

show :: SomeField -> String

showList :: [SomeField] -> ShowS

Some generic functions

fieldName :: Field f => Witness f -> String

Returns "GF(p)" or "GF(p^m)"

inverse :: Field f => f -> f

The multiplicate inverse (synonym for recip)

enumPrimeField :: forall f. Field f => Witness f -> [f]

Enumerate the elements of the prime field only

multGroup :: Field f => Witness f -> [f]

The nonzero elements in cyclic order, starting from the primitive generator (of course this is only useful for very small fields)

discreteLogTable :: forall f. Field f => Witness f -> Map f Int

Computes a table of discrete logarithms with respect to the primitive generator. Note: zero (that is, the additive identitiy of the field) is not present in the resulting map.

powerDefault :: forall f. Field f => f -> Integer -> f

Generic exponentiation