finite-fields-0.2.0.1: Arithmetic in finite fields

Math.FiniteField.Class

Contents

Description

Type class interface to different implementations of finite fields

Synopsis

Fields

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

A class for field element types

Minimal complete definition

Associated Types

type Witness f = w | w -> f Source #

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

type Prime f :: Nat Source #

the characteristic at type level

type Dim f :: Nat Source #

the dimension at type level

Methods

the prime characteristic

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

the size (or order) of the field

zero :: Witness f -> f Source #

The additive identity of the field

one :: Witness f -> f Source #

The multiplicative identity of the field

isZero :: f -> Bool Source #

check for equality with the additive identity

isOne :: f -> Bool Source #

check for equality with the multiplicative identity

embed :: Witness f -> Integer -> f Source #

an element of the prime field

embedSmall :: Witness f -> Int -> f Source #

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

a uniformly random field element

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

a random invertible element

primGen :: Witness f -> f Source #

a primitive generator

witnessOf :: f -> Witness f Source #

extract the witness from a field element

power :: f -> Integer -> f Source #

exponentiation

powerSmall :: f -> Int -> f Source #

frobenius :: f -> f Source #

Frobenius automorphism x -> x^p

enumerate :: Witness f -> [f] Source #

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

Instances

Instances details
 Field (Fp p) Source # Instance detailsDefined in Math.FiniteField.PrimeField.Generic Associated Typestype Witness (Fp p) = (w :: Type) Source #type Prime (Fp p) :: Nat Source #type Dim (Fp p) :: Nat Source # Methodsdimension :: Witness (Fp p) -> Integer Source #fieldSize :: Witness (Fp p) -> Integer Source #zero :: Witness (Fp p) -> Fp p Source #one :: Witness (Fp p) -> Fp p Source #isZero :: Fp p -> Bool Source #isOne :: Fp p -> Bool Source #embed :: Witness (Fp p) -> Integer -> Fp p Source #embedSmall :: Witness (Fp p) -> Int -> Fp p Source #randomFieldElem :: RandomGen gen => Witness (Fp p) -> gen -> (Fp p, gen) Source #randomInvertible :: RandomGen gen => Witness (Fp p) -> gen -> (Fp p, gen) Source #primGen :: Witness (Fp p) -> Fp p Source #witnessOf :: Fp p -> Witness (Fp p) Source #power :: Fp p -> Integer -> Fp p Source #powerSmall :: Fp p -> Int -> Fp p Source #frobenius :: Fp p -> Fp p Source #enumerate :: Witness (Fp p) -> [Fp p] Source # Field (Fp p) Source # Instance detailsDefined in Math.FiniteField.PrimeField.Small Associated Typestype Witness (Fp p) = (w :: Type) Source #type Prime (Fp p) :: Nat Source #type Dim (Fp p) :: Nat Source # Methodsdimension :: Witness (Fp p) -> Integer Source #fieldSize :: Witness (Fp p) -> Integer Source #zero :: Witness (Fp p) -> Fp p Source #one :: Witness (Fp p) -> Fp p Source #isZero :: Fp p -> Bool Source #isOne :: Fp p -> Bool Source #embed :: Witness (Fp p) -> Integer -> Fp p Source #embedSmall :: Witness (Fp p) -> Int -> Fp p Source #randomFieldElem :: RandomGen gen => Witness (Fp p) -> gen -> (Fp p, gen) Source #randomInvertible :: RandomGen gen => Witness (Fp p) -> gen -> (Fp p, gen) Source #primGen :: Witness (Fp p) -> Fp p Source #witnessOf :: Fp p -> Witness (Fp p) Source #power :: Fp p -> Integer -> Fp p Source #powerSmall :: Fp p -> Int -> Fp p Source #frobenius :: Fp p -> Fp p Source #enumerate :: Witness (Fp p) -> [Fp p] Source # Field (GF p m) Source # Instance detailsDefined in Math.FiniteField.GaloisField.Small Associated Typestype Witness (GF p m) = (w :: Type) Source #type Prime (GF p m) :: Nat Source #type Dim (GF p m) :: Nat Source # Methodscharacteristic :: Witness (GF p m) -> Integer Source #dimension :: Witness (GF p m) -> Integer Source #fieldSize :: Witness (GF p m) -> Integer Source #zero :: Witness (GF p m) -> GF p m Source #one :: Witness (GF p m) -> GF p m Source #isZero :: GF p m -> Bool Source #isOne :: GF p m -> Bool Source #embed :: Witness (GF p m) -> Integer -> GF p m Source #embedSmall :: Witness (GF p m) -> Int -> GF p m Source #randomFieldElem :: RandomGen gen => Witness (GF p m) -> gen -> (GF p m, gen) Source #randomInvertible :: RandomGen gen => Witness (GF p m) -> gen -> (GF p m, gen) Source #primGen :: Witness (GF p m) -> GF p m Source #witnessOf :: GF p m -> Witness (GF p m) Source #power :: GF p m -> Integer -> GF p m Source #powerSmall :: GF p m -> Int -> GF p m Source #frobenius :: GF p m -> GF p m Source #enumerate :: Witness (GF p m) -> [GF p m] Source # Field (Zech p m) Source # Instance detailsDefined in Math.FiniteField.GaloisField.Zech Associated Typestype Witness (Zech p m) = (w :: Type) Source #type Prime (Zech p m) :: Nat Source #type Dim (Zech p m) :: Nat Source # Methodscharacteristic :: 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 # Field (CFq p m) Source # Instance detailsDefined in Math.FiniteField.GaloisField.Zech.C Associated Typestype Witness (CFq p m) = (w :: Type) Source #type Prime (CFq p m) :: Nat Source #type Dim (CFq p m) :: Nat Source # Methodscharacteristic :: Witness (CFq p m) -> Integer Source #dimension :: Witness (CFq p m) -> Integer Source #fieldSize :: Witness (CFq p m) -> Integer Source #zero :: Witness (CFq p m) -> CFq p m Source #one :: Witness (CFq p m) -> CFq p m Source #isZero :: CFq p m -> Bool Source #isOne :: CFq p m -> Bool Source #embed :: Witness (CFq p m) -> Integer -> CFq p m Source #embedSmall :: Witness (CFq p m) -> Int -> CFq p m Source #randomFieldElem :: RandomGen gen => Witness (CFq p m) -> gen -> (CFq p m, gen) Source #randomInvertible :: RandomGen gen => Witness (CFq p m) -> gen -> (CFq p m, gen) Source #primGen :: Witness (CFq p m) -> CFq p m Source #witnessOf :: CFq p m -> Witness (CFq p m) Source #power :: CFq p m -> Integer -> CFq p m Source #powerSmall :: CFq p m -> Int -> CFq p m Source #frobenius :: CFq p m -> CFq p m Source #enumerate :: Witness (CFq p m) -> [CFq p m] Source #

data SomeField Source #

Constructors

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

Instances

Instances details
 Source # Instance detailsDefined in Math.FiniteField.Class MethodsshowList :: [SomeField] -> ShowS #

Some generic functions

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

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

inverse :: Field f => f -> f Source #

The multiplicate inverse (synonym for recip)

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

Enumerate the elements of the prime field only

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

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 Source #

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 Source #

Generic exponentiation