Math.FiniteField.GaloisField.Small

Small Galois fields via a precomputed table of Conway polynomials.

This covers:

• all fields with order <= 2^30
• all fields with characteristic < 2^16 and order < 2^64 (?)
• higher powers for very small prime characteristic
• some more

To look up Conway polynomials, see the module Math.FiniteField.Conway.

Witness for the existence of the field

data WitnessGF (p :: Nat) (m :: Nat) where

We need either a Conway polynomial, or in the m=1 case, a proof that p is prime

Constructors

WitnessFp :: IsSmallPrime p -> WitnessGF p 1

WitnessFq :: ConwayPoly p m -> WitnessGF p m

Instances

Show (WitnessGF p m)

Defined in Math.FiniteField.GaloisField.Small

Methods

showsPrec :: Int -> WitnessGF p m -> ShowS

show :: WitnessGF p m -> String

showList :: [WitnessGF p m] -> ShowS

data SomeWitnessGF

Constructors

forall p m. SomeWitnessGF (WitnessGF p m)

Instances

Show SomeWitnessGF

Defined in Math.FiniteField.GaloisField.Small

Methods

showsPrec :: Int -> SomeWitnessGF -> ShowS

show :: SomeWitnessGF -> String

showList :: [SomeWitnessGF] -> ShowS

mkGaloisField :: Int -> Int -> Maybe SomeWitnessGF

Usage:

mkGaloisField p m

to construct the field with q = p^m elements

Implementation note: For m=1 we may do a primality test, which is very slow at the moment. You can use unsafeGaloisField below to avoid this.

unsafeGaloisField :: Int -> Int -> SomeWitnessGF

In the case of m=1 you are responsible for guaranteeing that p is a prime (for m>1 we have to look up a Conway polynomial anyway).

constructGaloisField :: forall p m. SNat64 p -> SNat64 m -> Maybe (WitnessGF p m)

Field elements

data GF (p :: Nat) (m :: Nat)

An element of the Galois field of order q = p^m

Instances

Num (GF p m)

Defined in Math.FiniteField.GaloisField.Small

Methods

(+) :: GF p m -> GF p m -> GF p m

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

(*) :: GF p m -> GF p m -> GF p m

negate :: GF p m -> GF p m

abs :: GF p m -> GF p m

signum :: GF p m -> GF p m

fromInteger :: Integer -> GF p m

Fractional (GF p m)

Defined in Math.FiniteField.GaloisField.Small

Methods

(/) :: GF p m -> GF p m -> GF p m

recip :: GF p m -> GF p m

fromRational :: Rational -> GF p m

Show (GF p m)

Defined in Math.FiniteField.GaloisField.Small

Methods

showsPrec :: Int -> GF p m -> ShowS

show :: GF p m -> String

showList :: [GF p m] -> ShowS

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]

Eq (GF p m)

Defined in Math.FiniteField.GaloisField.Small

Methods

(==) :: GF p m -> GF p m -> Bool

(/=) :: GF p m -> GF p m -> Bool

Ord (GF p m)

Note: the Ord instance is present only so that you can use GF as key in Maps - the ordering is kind of arbitrary!

Defined in Math.FiniteField.GaloisField.Small

Methods

compare :: GF p m -> GF p m -> Ordering

(<) :: GF p m -> GF p m -> Bool

(<=) :: GF p m -> GF p m -> Bool

(>) :: GF p m -> GF p m -> Bool

(>=) :: GF p m -> GF p m -> Bool

max :: GF p m -> GF p m -> GF p m

min :: GF p m -> GF p m -> GF p m

type Dim (GF p m)

Defined in Math.FiniteField.GaloisField.Small

type Dim (GF p m) = m

type Prime (GF p m)

Defined in Math.FiniteField.GaloisField.Small

type Prime (GF p m) = p

type Witness (GF p m)

Defined in Math.FiniteField.GaloisField.Small

type Witness (GF p m) = WitnessGF p m