Finite Field Computation
Finite Field Multiplication and Inversion
Multiplication with reduction, inversion by extended Euclid or by exponentiation, and the Itoh-Tsujii method for extension fields.
Engineering / MathematicsFinite Field Computation2 min readKV-MATH-0524
Field multiplication is a polynomial product followed by a reduction. Inversion is where the cost concentrates, and there are three genuinely different approaches with different break-even points.
Multiplication
Field multiplication in the polynomial basis
- MultiplyForm the polynomial product, degree up to 2n - 2.
- ReduceReduce modulo the defining irreducible polynomial.
- Normalise coefficientsReduce each coefficient modulo p.
Three approaches to inversion
| Method | Cost | When preferred |
|---|---|---|
| Extended Euclidean on polynomials | O(n^2) operations in F_p | General purpose; usually the default |
| Exponentiation by field order minus two | About log(p^n) multiplications | Simple, constant-time, useful when uniformity matters |
| Itoh-Tsujii | Reduces to an inversion in the prime field plus Frobenius work | Extension fields where Frobenius is cheap |
The Itoh-Tsujii idea
Reduce inversion in the extension to inversion in the prime field. Multiply the element by its conjugates under Frobenius; the product is the norm, which lies in the prime field. Invert there, then multiply back by the conjugate product.
Batching
Where many inversions are required, Montgomery's simultaneous inversion applies unchanged in a finite field — see simultaneous inversion. The break-even point is even lower than in the integer case because field inversion is comparatively more expensive.
Characteristic two
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.5.2. 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.