This is a Haskell library implementing arithmetics in finite fields.
So far we have implemented:
- generic prime fields - module
- small prime fields, where small means
p < 2^31- module
- small Galois fields, using a precomputed table of Conway polynomials - module
- small Galois fields, using tables of Zech's logarithm
- C implementation of the Zech's logarithm stuff
- subfields (only for the Zech representation)
- generic field extensions
- big finite fields relevant for cryptography
- maybe even JIT compiling specific fields would make sense?
- optional: elliptic curves over finite fields? (again we could have "small" curves for algebraic geometry and "very big" curves for cryptography...)
How to use
The API is still in flux while I try to figure out the balance between ergonomy and type-safety.
For now, each field has a "witness" which has two purposes: 1) it's a proof that
the field actually exists (eg.
p is a prime); and 2) carrying the necessary
data to for computations (eg. Conway polynomials). So there are two Haskell types
for each implementation: the witness represents the field itself, and the other
type represents the elements of the field.
Both the witness types and the field element types are parametrized by the field
m for a field of order
q = p^m). You can "create" fields
wrapped into existential types, and then you can do
case _ of on that existential
type and do the calculations inside. Unfortunately this also means that the API is not
There is a common type class for all fields (defined in module
so you can write polymorphic code and run it "in" any field implementation.
There are some example applications in the