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

Math.FiniteField.Class

Description

Type class interface to different implementations of finite fields

Synopsis

Documentation

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

Minimal complete definition

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

Associated Types

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

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

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 t he witness from a field element

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

exponentiation

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

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.Small

Associated Types

type Witness (Fp p) = (r :: Type) 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 #

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

Field (Fp p) Source # 
Instance details

Defined in Math.FiniteField.PrimeField.Generic

Associated Types

type Witness (Fp p) = (r :: Type) 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 #

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) = (r :: Type) 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 #

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) = (r :: Type) 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 #

enumerate :: Witness (Zech p m) -> [Zech 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

Methods

showsPrec :: Int -> SomeField -> ShowS #

show :: SomeField -> String #

showList :: [SomeField] -> ShowS #

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 is not present in the resulting map.

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

Generic exponentiation