Engineering/Mathematics/Algorithm engineering

Factoring Polynomials over Finite Fields

Unlike integer factorization, polynomial factorization over a finite field is solved: randomised algorithms run in polynomial time and are fast in practice. The whole approach rests on one structural gift — the Frobenius map — that the integers do not provide.

Core algorithm
Computing
Polynomial time
≈16 min read
Builds finite fields

Polynomial timeSolved problemRandomised algorithms factor degree-k polynomials over F_q in expected Õ(k² + k log q) operations.

gcd(f, X^{q^d}−X)Degree separationExtracts exactly the factors of degree d — the distinct-degree stage.

≥ 1/2Splitting probabilityEach Cantor–Zassenhaus trial separates a given pair of factors with probability at least one half.

dim kerBerlekampThe number of irreducible factors equals the kernel dimension of Frobenius − I.

Executive summary

Factorization proceeds in three stages, and separating them is what makes the problem tractable. Squarefree decomposition removes repeated factors using the derivative. Distinct-degree factorization separates the remaining factors by degree using gcds with X^{q^d} − X. Equal-degree factorization splits a product of same-degree irreducibles, and this is the only stage that requires randomness.

Berlekamp's algorithm is an alternative that solves the whole problem with linear algebra: the factors correspond to the kernel of the Frobenius map minus the identity. It is preferable for small fields and low degrees; Cantor–Zassenhaus scales better for large q.

Squarefree decomposition
Compute gcd(f, f′) to strip repeated factors, handling the characteristic-p case where the derivative vanishes.
Distinct-degree factorization
For d = 1, 2, … compute gcd(f, X^{q^d} − X), which collects precisely the irreducible factors of degree d.
Equal-degree factorization
Split each same-degree product with random probes; each trial succeeds with probability at least one half.
Verify
Multiply the factors back together. Verification is cheap and turns a randomised procedure into a certain answer.

Contents

Squarefree decomposition

A repeated irreducible factor of f divides gcd(f, f′), so a single gcd separates the squarefree part from the rest — no factoring required.

Squarefree decomposition over F_q, characteristic p

if f′ = 0:
// every exponent is a multiple of p
write f = g(X^p); take p-th roots of coefficients (Frobenius is invertible)
recurse on g₁ with f = g₁^p
d ← gcd(f, f′); w ← f/d
// w holds each distinct irreducible factor exactly once
peel multiplicities: repeatedly gcd w with d, dividing out as multiplicities are identified
output list of (squarefree factor, multiplicity)

O(k²) field operations for degree k. Always the first stage — the later algorithms assume a squarefree input.

The vanishing-derivative branch is not optional

Over F_q with characteristic p, the polynomial X^p − a has zero derivative even though it is non-constant. An implementation that assumes f′ ≠ 0 for non-constant f will loop or return wrong results on such inputs. Take p-th roots of the coefficients using the inverse Frobenius, which exists because Frobenius is bijective on a finite field.

Contents

Distinct-degree factorization

Theorem T1

The degree-separating identity

X^{q^d} − X = ∏ { g : g monic irreducible over F_q, deg g ∣ d }

Hence for a squarefree f, the gcd of f with X^{q^d} − X is exactly the product of the irreducible factors of f whose degree divides d. Processing d in increasing order and dividing out at each step isolates the factors of each degree.

Distinct-degree factorization

input: squarefree monic f
h ← X mod f; d ← 0
while deg f > 0:
d ← d+1; h ← h^q mod f // one Frobenius application
g ← gcd(h − X, f) // product of the degree-d factors
if g ≠ 1: record (g, d); f ← f/g; h ← h mod f
if deg f < 2d+2: record (f, deg f); break
output list of (product of degree-d factors, d)

O(k) Frobenius applications, each O(k² log q) classically, plus one gcd per step. The early-exit test avoids a full sweep when the remaining factor must be irreducible.

Frobenius dominates the cost. Computing h^q mod f is a modular exponentiation with exponent q. Precomputing the matrix of the Frobenius map on F_q[X]/(f) turns each subsequent application into a matrix–vector product.
Irreducibility test for free. A degree-k polynomial is irreducible exactly when X^{q^k} ≡ X (mod f) and gcd(f, X^{q^k/ℓ} − X) = 1 for every prime ℓ ∣ k. This is the standard test used when constructing finite fields.
Root finding is the case d = 1. The roots of f in F_q are the linear factors, extracted by gcd(f, X^q − X) followed by an equal-degree split.

Contents

Equal-degree factorization: Cantor–Zassenhaus

After the previous stage, each remaining polynomial is a product of r distinct irreducibles all of the same degree d. By the Chinese remainder theorem, F_q[X]/(f) ≅ (F_q^d)^r, and a random element has an independent coordinate in each copy. Raising to the power (q^d−1)/2 sends each coordinate to ±1 at random, so a gcd separates the components.

Cantor–Zassenhaus equal-degree split (odd q)

input: f, a product of r ≥ 2 distinct irreducibles each of degree d
repeat:
pick a random a ∈ F_q[X] with deg a < deg f
g ← gcd(a, f); if g ≠ 1: return g // lucky hit
b ← a^{(q^d − 1)/2} mod f
g ← gcd(b − 1, f)
if 1 < deg g < deg f: return g // non-trivial split found
recurse on g and f/g until all factors are irreducible

Each trial costs one modular exponentiation, O(d log q) squarings in F_q[X]/(f). The probability of a non-trivial split is at least 1/2, so the expected number of trials is at most 2.

Characteristic two needs a different probe

The exponent (q^d−1)/2 is meaningless when q is even. The standard substitute is the trace map a + a² + a⁴ + ⋯ + a^{2^d−1}, whose value in each component is 0 or 1 with equal probability, giving the same splitting behaviour.

Contents

Berlekamp's algorithm

Theorem T2

The Berlekamp subalgebra

For squarefree f with r irreducible factors, the set B = {a ∈ F_q[X]/(f) : a^q = a} is an F_q-vector space of dimension exactly r — it is the kernel of the linear map Q − I, where Q is the matrix of the Frobenius map. Any non-constant a ∈ B yields a non-trivial factor, because f = ∏_{c ∈ F_q} gcd(f, a − c).

Build the Frobenius matrix
Compute X^iq mod f for i = 0,…,k−1; these are the columns of Q. Cost O(k² log q + k³) or better.
Compute the kernel of Q − I
Gaussian elimination gives a basis; its dimension is the number of irreducible factors, known before any factor is found.
Split using basis elements
For a non-constant basis element a, the gcds gcd(f, a − c) over c ∈ F_q split f. Small q means few values of c to try.

Choosing between the two approaches
Criterion	Berlekamp	Cantor–Zassenhaus
Cost dependence on q	Splitting step scales with q if done deterministically	Only logarithmic in q
Cost dependence on degree	O(k³) for the linear algebra	Õ(k²) with the standard stages
Randomness	Needed only to pick useful kernel elements	Essential to the splitting step
Extra information	Reveals the number of factors immediately	Discovers factors one at a time
Best for	Small q, moderate degree	Large q, high degree

Production computer algebra systems implement both and select on the parameters, often after a cheap distinct-degree pass that may finish the job on its own.

Contents

Constructing irreducible polynomials

Building a finite field F_q^k requires an irreducible polynomial of degree k over F_q. Random search is the method of choice.

Random irreducible polynomial of degree k over F_q

repeat:
pick a random monic f of degree k
if f passes the irreducibility test: return f
// test: X^{q^k} ≡ X (mod f) and gcd(f, X^{q^{k/ℓ}} − X) = 1 for each prime ℓ ∣ k

Success probability ≈ 1/k by the Möbius count I_q(k) ≈ q^k/k, so about k trials are expected. Each test costs O(k² log q) field operations.

Prefer sparse moduli. Reduction modulo f costs one shifted subtraction per non-zero term, so trinomials and pentanomials give the fastest field arithmetic. Standards for binary fields specify particular low-weight polynomials.
Primitive polynomials — those whose roots generate F*_q^k — are needed for maximal-length shift register sequences. Verifying primitivity requires the factorization of q^k−1, which is a much harder precondition than irreducibility.
Deterministic construction is possible in polynomial time only under the extended Riemann hypothesis, or in special characteristics. Unconditional deterministic construction for arbitrary q and k remains open — a striking gap given how easy the randomised version is.

Contents

Quick reference and FAQ

Facts
Fact	Statement
Squarefree test	gcd(f, f′) = 1
Degree separation	gcd(f, X^{q^d} − X) collects degree-d factors
Irreducibility	X^{q^k} ≡ X and coprimality at each k/ℓ
Split probability	≥ 1/2 per Cantor–Zassenhaus trial
Factor count	dim ker(Q − I) in Berlekamp's method
Irreducible density	≈ 1/k among monic degree-k polynomials
Overall cost	Expected Õ(k² + k log q) operations
Characteristic 2	Use the trace map instead of the (q^d−1)/2 power

Why is randomness needed at all?

The equal-degree stage must break a symmetry: the factors are indistinguishable by any polynomial-time deterministic criterion currently known, and a random probe breaks the tie. Deterministic alternatives exist under the extended Riemann hypothesis or for small characteristic.

Does this help with factoring polynomials over ℚ?

It is the first step. Factor modulo a well-chosen prime, lift the factorization to a prime power by Hensel's lemma, then recombine factors — with lattice reduction (LLL) used to make the recombination step polynomial time rather than exponential.

How is the number of irreducible factors known before finding them?

Berlekamp's method computes it as the kernel dimension of Q − I, which is a single Gaussian elimination. The distinct-degree stage also reveals the degree profile before any equal-degree splitting is attempted.

Can these algorithms find roots of a polynomial over a finite field?

Yes — root finding is the degree-one case. Compute gcd(f, X^q − X) to isolate the linear factors, then apply equal-degree splitting with d = 1. This is the standard method behind modular square and cube root extraction for general exponents.

Contents

References and further reading

V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 21.
E. R. Berlekamp, 'Factoring polynomials over finite fields', Bell System Technical Journal 46 (1967) 1853–1859.
D. G. Cantor and H. Zassenhaus, 'A new algorithm for factoring polynomials over finite fields', Math. Comp. 36 (1981) 587–592.
J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge, 2013 — Chapter 14.
V. Shoup, 'A new polynomial factorization algorithm and its implementation', J. Symbolic Computation 20 (1995) 363–397.

KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: factoring-polynomials-over-finite-fieldsReview cycle: annual

Factoring Polynomials over Finite Fields

Executive summary

Squarefree decomposition

Distinct-degree factorization

Equal-degree factorization

Verify

Squarefree decomposition

Distinct-degree factorization

The degree-separating identity

Equal-degree factorization: Cantor–Zassenhaus

Berlekamp's algorithm

The Berlekamp subalgebra

Build the Frobenius matrix

Compute the kernel of Q − I

Split using basis elements

Constructing irreducible polynomials

Quick reference and FAQ

References and further reading

Continue learning

KEVOS Intelligence

Executive summary

Squarefree decomposition

Distinct-degree factorization

Equal-degree factorization

Verify

Squarefree decomposition

Distinct-degree factorization

The degree-separating identity

Equal-degree factorization: Cantor–Zassenhaus

Berlekamp's algorithm

The Berlekamp subalgebra

Build the Frobenius matrix

Compute the kernel of Q − I

Split using basis elements

Constructing irreducible polynomials

Quick reference and FAQ

Related pages in this library

References and further reading

Continue learning