finite-fields-0.2.0.1: Arithmetic in finite fields
Safe HaskellSafe-Inferred
LanguageHaskell2010

Math.FiniteField.Class

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

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

characteristic :: Witness f -> Integer Source #

the prime characteristic

dimension :: Witness f -> Integer Source #

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

fieldSize :: Witness f -> Integer Source #

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 details

Defined in Math.FiniteField.PrimeField.Generic

Associated Types

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

type Prime (Fp p) :: Nat Source #

type Dim (Fp p) :: Nat Source #

Methods

characteristic :: Witness (Fp p) -> Integer Source #

dimension :: 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 details

Defined in Math.FiniteField.PrimeField.Small

Associated Types

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

type Prime (Fp p) :: Nat Source #

type Dim (Fp p) :: Nat Source #

Methods

characteristic :: Witness (Fp p) -> Integer Source #

dimension :: 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 details

Defined in Math.FiniteField.GaloisField.Small

Associated Types

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

type Prime (GF p m) :: Nat Source #

type Dim (GF p m) :: Nat Source #

Methods

characteristic :: 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 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 #

Field (CFq p m) Source # 
Instance details

Defined in Math.FiniteField.GaloisField.Zech.C

Associated Types

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

type Prime (CFq p m) :: Nat Source #

type Dim (CFq p m) :: Nat Source #

Methods

characteristic :: 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
Show SomeField Source # 
Instance details

Defined in Math.FiniteField.Class

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