Engineering / Mathematics — Finite Fields
Computing Minimal Polynomials over Finite Fields
Computing the minimal polynomial of a finite field element using conjugates or linear algebra.
Executive summary
The minimal polynomial of an element over a subfield is the product over its conjugates, computable by repeated Frobenius application.
An alternative computes it by linear algebra on the powers, and a third uses the linearly generated sequence machinery.
Learning objectives
- Compute a minimal polynomial from conjugates.
- Compare the available methods.
- Determine the degree of an element.
01From conjugates
Minimal polynomial via conjugates
element α of F_{q^k}the minimal polynomial of α over F_q- Set β = α and collect the orbit.
- Repeatedly apply Frobenius: β = β^q, appending each result.
- Stop when the orbit returns to α; the orbit size is the degree d.
- Form the product of (X − β) over the orbit.
- The coefficients lie in F_q; return the resulting polynomial.
O(d) Frobenius applications plus O(d²) to expand the productThe orbit size is the degree, so the algorithm determines the degree as a by-product. The coefficients are guaranteed to lie in the base field because they are symmetric functions of the conjugates and hence fixed by Frobenius.
02Alternative methods
| Method | Cost | Notes |
|---|---|---|
| Conjugate product | O(dk²) | Direct; degree found automatically |
| Linear algebra on powers | O(k³) | Deterministic; forms the power matrix |
| Sequence method | O(k²) plus k multiplications | Randomised; needs verification |
The conjugate method is preferred when the degree is small relative to k, since its cost scales with the actual degree rather than with the field dimension. The sequence method wins for large k where the cubic term dominates.
The sequence method projects the powers of the element onto a random linear functional and runs Berlekamp–Massey. It is the same technique used for matrix minimal polynomials and sparse linear algebra, applied here.
03Degree and subfield membership
Degree criterion
The degree of α over F_q is the least d with α^{q^d} = α, and it divides k.
Equivalently, α lies in F_{q^d} for exactly those d that are multiples of its degree.
Compute the orbit under Frobenius
Apply repeatedly until the element returns.
Read off the degree
The orbit length is the degree.
Determine the smallest containing subfield
It is F_{q^d} for that degree d.
This gives a direct test for subfield membership: an element lies in F_{q^d} exactly when α^{q^d} = α, a single Frobenius power computation.
Elements of degree exactly k generate the whole field and are called primitive in the field-generation sense. They are common — most elements have full degree — which is why random search for a generator of the field succeeds quickly.
04Frequently asked questions
Does the degree always divide k?
Yes. The element generates a subfield, whose degree must divide k by the tower law. So possible degrees are exactly the divisors of k.
How is the Frobenius matrix built?
By computing the q-th power of each basis element and recording the coordinates as columns. That costs k exponentiations once, after which every application is a matrix-vector product.
Is a full-degree element the same as a multiplicative generator?
No — the two notions differ. A full-degree element generates the field additively-and-multiplicatively as a ring, while a multiplicative generator generates the cyclic group of non-zero elements. Every multiplicative generator has full degree, but not conversely.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 465-467.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.