Finite Field Computation
Finite Field Element Representation
Representing elements of a finite field as polynomials modulo an irreducible, choosing the modulus, and the trade-offs against logarithmic and normal bases.
Engineering / MathematicsFinite Field Computation2 min readKV-MATH-0523
A finite field has p^n elements for a prime p and is unique up to isomorphism for each size. Uniqueness of the field does not mean uniqueness of representation, and the choice determines which operations are cheap.
Polynomial basis
The standard representation takes elements as polynomials of degree less than n over the prime field, with arithmetic modulo a fixed irreducible polynomial of degree n.
| Operation | Cost | Notes |
|---|---|---|
| Addition | O(n) in F_p | Coefficientwise; no reduction needed |
| Multiplication | O(n^2) schoolbook, then reduce | Reduction is cheap for a sparse modulus |
| Inversion | Extended Euclidean on polynomials | Substantially more expensive than multiplication |
| Frobenius (p-th power) | Linear map, precomputable | Cheap once tabulated |
Choosing the modulus
Finding an irreducible polynomial of given degree is easy: pick at random and test. A random polynomial of degree n is irreducible with probability about 1/n, and irreducibility testing is fast via distinct degree factorisation.
Alternative representations
Zech logarithms
Store a table of discrete logarithms relative to a generator. Multiplication becomes addition of exponents; addition needs a table lookup. Excellent for small fields, infeasible for large ones because the table has p^n entries.
Normal basis
Uses a basis closed under Frobenius. Raising to the p-th power becomes a cyclic shift — nearly free. Multiplication is more expensive unless an optimal normal basis exists.
Tower representation
Builds the field as a tower of small extensions. Useful when the degree factors conveniently and for fields of characteristic two.
Interoperability
Frequently Asked Questions
Is the finite field really unique for a given size?
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.5.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.