Safe Haskell | Safe-Inferred |
---|---|

Language | Haskell2010 |

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.

## Synopsis

- data WitnessGF (p :: Nat) (m :: Nat) where
- WitnessFp :: IsSmallPrime p -> WitnessGF p 1
- WitnessFq :: ConwayPoly p m -> WitnessGF p m

- data SomeWitnessGF = forall p m. SomeWitnessGF (WitnessGF p m)
- mkGaloisField :: Int -> Int -> Maybe SomeWitnessGF
- unsafeGaloisField :: Int -> Int -> SomeWitnessGF
- constructGaloisField :: forall p m. SNat64 p -> SNat64 m -> Maybe (WitnessGF p m)
- data GF (p :: Nat) (m :: Nat)

# Witness for the existence of the field

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

We need either a Conway polynomial, or in the `m=1`

case, a proof that `p`

is prime

WitnessFp :: IsSmallPrime p -> WitnessGF p 1 | |

WitnessFq :: ConwayPoly p m -> WitnessGF p m |

data SomeWitnessGF Source #

forall p m. SomeWitnessGF (WitnessGF p m) |

#### Instances

Show SomeWitnessGF Source # | |

Defined in Math.FiniteField.GaloisField.Small showsPrec :: Int -> SomeWitnessGF -> ShowS # show :: SomeWitnessGF -> String # showList :: [SomeWitnessGF] -> ShowS # |

mkGaloisField :: Int -> Int -> Maybe SomeWitnessGF Source #

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

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

# Field elements

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

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