A polynomial can have no roots in its coefficient field and still be reducible. That is the first boundary a computational factorisation algorithm must respect. Finding linear factors is only one part of the job. A quartic can split into two irreducible quadratics, and a degree-six polynomial can split into two cubics, while neither has a root in the original field.
Over a finite field, a complete algorithm therefore asks several different questions. Are factors repeated? What degrees do the irreducible factors have? Can factors of the same degree be separated? Has the final product been reconstructed exactly? Combining those questions into one vague instruction to factorise hides both the Mathematics and the failure modes.
This is Guide 10 in the Bukit Timah Tutor Computational Number Theory series. It builds on Guide 9: Finite Fields and Polynomial Arithmetic. It is an advanced enrichment route, separate from school exercises in real or rational polynomial factorisation. The BTT Mathematics Hub connects both routes without treating them as the same learning task.
1. State the factorisation problem precisely
Let Fq be a field with q elements, where q is a prime power. Given a nonzero polynomial f in Fq[X], a complete factorisation has the form c·f1^e1·…·fr^er. The constant c is the nonzero leading coefficient; each fi is monic and irreducible; the fi are distinct; and every exponent ei is positive.
The field is part of the input. A polynomial irreducible over F2 can split over F4, and an integer polynomial can behave differently after its coefficients are reduced modulo different primes. An answer without a declared coefficient field is not a complete computational specification.
Over a field, polynomial factorisation is unique up to factor order once the irreducible factors are normalised to be monic. The standard finite-field algorithmic division into square-free, distinct-degree and equal-degree work is described in the Waterloo symbolic-computation notes and Shoup’s treatment. [1,2]
The zero polynomial is excluded because it does not have this finite factorisation form. A nonzero constant has no positive-degree irreducible factors; its factorisation is just its unit coefficient. A linear polynomial is already irreducible after normalisation. Handling these cases first removes ambiguity from later loops.
2. A root test does not finish a factorisation
Over F3, consider f=(X²+1)(X²+X+2). Neither quadratic has a root. For X²+1, the three values are 1,2,2. For X²+X+2, they are 2,1,2. Therefore each quadratic is irreducible over F3.
Multiplying the two factors and reducing coefficients gives f=X⁴+X³+X+2. This quartic has no root in F3 because neither factor vanishes there. Nevertheless, it is reducible: its displayed factorisation has two degree-two factors.
A program that evaluates f at zero, one and two and then declares it irreducible is wrong. It has established only that f has no linear factor. For degree two or three that would be enough; for degree four it is not. The mathematical implication changed when the degree changed.
This is an excellent diagnostic example because all the arithmetic is small. The learner cannot blame the failure on huge numbers or a complicated implementation. The error is a mistaken stopping rule.
3. Polynomial gcd is the basic extraction tool
The Euclidean algorithm over Fq[X] repeatedly performs polynomial division with remainder. The last nonzero remainder is normalised to be monic. As with integers, replacing (A,B) by (B,A mod B) preserves the common-divisor structure while reducing the size of the problem.
If a polynomial H contains some but not all of the irreducible factors of f, then gcd(f,H) extracts precisely the shared part, with multiplicities controlled by the exponents in both polynomials. Many apparently different factorisation methods are ways of manufacturing an H with useful selective behaviour.
The gcd output can be checked by dividing both inputs by it. To establish that it is the greatest common divisor rather than just a common factor, a polynomial Bézout relation can be retained. This distinction mirrors the certificates in the integer Euclidean-algorithm guide.
All subsequent calculations require genuine field coefficients. Ordinary residues modulo nine do not form a field, even though GF(9) does. An attempted leading-coefficient inverse can fail in a composite integer residue ring and invalidate the usual polynomial Euclidean algorithm.
4. Repeated factors and the formal derivative
The formal derivative of f=ΣaiX^i is f’=Σi·aiX^(i−1), with coefficients interpreted in the field. Over a finite field, f is square-free exactly when gcd(f,f’)=1. Square-free means that no nonconstant polynomial square divides f. [1]
Suppose f=h²k. The product rule gives f’=2hh’k+h²k’, so h divides both f and f’. The same idea reveals repeated irreducible factors. The derivative supplies information about multiplicity, not merely about a graph’s slope.
For a worked example over F3, take f=(X+1)²(X²+1). Expansion gives X⁴+2X³+2X²+2X+1. Its derivative is X³+X+2 because 4 becomes 1, 6 becomes zero and 4 becomes 1 modulo three.
The monic gcd of f and f’ is X+1. Dividing f by that gcd gives (X+1)(X²+1), and another gcd separates the multiplicity-two linear part from the multiplicity-one quadratic part. The complete factorisation retains the exponent two; returning only the distinct factors would lose information.
5. Characteristic p creates a special derivative case
Over F3, the derivative of X³+1 is zero. The polynomial itself is not constant: X³+1=(X+1)³. The coefficient three disappears from the derivative because the characteristic is three.
More generally, a polynomial with zero derivative in characteristic p has nonzero terms only at exponents divisible by p. Over a finite field, Frobenius is bijective, so its coefficients have unique p-th roots. The polynomial is a p-th power of a smaller polynomial.
For example, X⁶+2X³+1 over F3 is (X²+2X+1)³. The smaller polynomial is (X+1)², so the original is (X+1)⁶. The exponent six is recovered by multiplying the smaller multiplicity by three.
Blindly computing f/gcd(f,f’) fails here: gcd(f,0)=f, so the quotient is one and all factors disappear. A complete square-free decomposition must recursively handle the p-th-power remainder. Over an extension Fq with q=p^m, coefficient p-th roots are not obtained by merely leaving arbitrary coefficients unchanged; inverse Frobenius supplies them.
6. Why Frobenius identifies factor degrees
The polynomial X^(q^d)−X is the product, without repetition, of all monic irreducible polynomials over Fq whose degrees divide d. This theorem is the central structural input behind the degree tests below. [1,2]
One way to understand it is through finite extension fields. The roots of X^(q^d)−X form the field with q^d elements. An element whose minimal polynomial has degree e belongs to that field exactly when e divides d. The derivative of X^(q^d)−X is −1, so the polynomial has no repeated roots.
Consequently, gcd(f,X^q−X) collects the distinct linear factors of f. The gcd with X^(q²)−X collects factors of degrees one and two. The gcd with X^(q³)−X collects degrees one and three, not degrees one, two and three. The condition is divides d, not at most d.
This last distinction matters. A formula using q^3 does not automatically include quadratic factors. Distinct-degree factorisation works by removing previously identified factors as it proceeds, not by treating successive Frobenius polynomials as ordinary cumulative degree cutoffs.
7. Never construct the enormous polynomial first
The formal degree of X^(q^d) can be enormous, but the gcd only needs its remainder modulo the current polynomial. Compute that remainder by repeated modular powering. This is the polynomial version of avoiding an enormous integer power when only a residue is needed.
h0 = X mod f h1 = h0^q mod f h2 = h1^q mod f ... hd = X^(q^d) mod f.
Every stored remainder has degree below degree(f). The exponent q is processed with binary powering or another exact field-aware method. Intermediate products are reduced before their degrees grow without control.
After dividing f by a discovered factor, the working modulus changes. A stored remainder should be reduced modulo the new residual polynomial before being used again. The mathematical congruence survives because the new modulus divides the old one; the representation must nevertheless be updated consistently.
This is the same principle as fast modular exponentiation: preserve the information required by the final question, not every coefficient of the huge unreduced object.
8. An irreducibility certificate
For a monic degree-n polynomial f over Fq, one useful criterion is: X^(q^n)=X modulo f, and for every prime divisor ℓ of n, gcd(f,X^(q^(n/ℓ))−X)=1. For n=1, the gcd list is empty and every monic linear polynomial passes. Constant and zero inputs are handled separately. [2]
Here is why the two parts work together. The first condition says f divides the square-free polynomial X^(q^n)−X. Therefore f is square-free and every irreducible factor degree divides n. If f had a proper factor of degree d dividing n, choose a prime ℓ dividing n/d. Then d divides n/ℓ, so that factor would appear in the prohibited gcd.
Conversely, an irreducible degree-n polynomial divides X^(q^n)−X, while its degree does not divide any smaller n/ℓ. Thus it satisfies every condition. The argument explains why testing only the final Frobenius equality is insufficient: a product of smaller factors with degrees dividing n can also satisfy that equality.
A certificate can retain the relevant modular-power remainders and gcd results. Verifying these exact identities does not depend on trusting the search process that selected f. This is especially useful when an irreducible polynomial will later define a field.
9. A small irreducibility check over F2
Take f=X³+X+1. In its quotient, X³=X+1. Squaring and reducing yields X⁴=X²+X; squaring again gives X⁸=X⁴+X²=X. The final Frobenius condition for n=3 therefore holds.
The only prime divisor of n is three, so the remaining test uses X^(2^(3/3))−X=X²+X. Its gcd with f is one: its factors are X and X+1, while f has neither zero nor one as a root.
Both tests pass. This agrees with the simpler cubic no-root argument from Guide 9. We use a more elaborate certificate here not because the small cubic needs it, but because the same test remains meaningful when a polynomial is too large for an elementary root check.
By contrast, X⁴+X²+1 over F2 has no root yet equals (X²+X+1)². Its zero derivative immediately reveals a repeated-factor obstruction. Different tests expose different parts of the structure; they are not interchangeable labels for irreducibility.
10. Distinct-degree factorisation
After square-free decomposition, work with a monic square-free polynomial R. At degree d, compute the gcd with X^(q^d)−X. Because all smaller-degree factors have already been removed, the nontrivial gcd now contains precisely the factors of degree d.
Input: monic square-free R over Fq
h = X mod R
d = 1
while 2d ≤ degree(R):
h = h^q mod R
G = gcd(R, h−X)
if G is not 1:
record (G, d)
R = R/G
if R is 1: stop
h = h mod R
d = d+1
if R is not 1:
record (R, degree(R))
The final residual polynomial is irreducible: if it had two or more factors, at least one would have degree at most half the residual degree and would already have been found. This stopping argument requires the invariant that smaller-degree factors have been removed.
A recorded pair (G,d) does not say that G is irreducible. It says every irreducible factor of G has degree d. If degree(G)=3d, there are three remaining factors to separate. Confusing a degree group with a finished factor is another common premature stopping error.
11. A degree-six example with no linear factor
Over F2, let f=X⁶+X⁵+X⁴+X³+X²+X+1. It factors as (X³+X+1)(X³+X²+1). Both cubics have no root in F2 and are irreducible.
The degree-one and degree-two Frobenius gcds are one. At d=3, the gcd returns the entire degree-six polynomial because both cubic factors have degree dividing three. That is a successful distinct-degree classification, but it is not a completed factorisation.
The output at this point is one equal-degree block containing two cubic factors. A separate splitting stage is needed. This example shows why an algorithm can make meaningful progress without immediately printing smaller factors: it has narrowed the possible factor degrees.
The displayed factorisation can be verified by direct multiplication. A responsible implementation still checks the irreducibility of both terminal cubics, or retains certificates from its construction, rather than assuming that two printed cubic factors must be irreducible.
12. Berlekamp’s idea: find Frobenius-fixed residues
Let f be monic and square-free. Consider the quotient algebra A=Fq[X]/(f). It need not be a field because f may be reducible. Frobenius maps b to b^q and is linear over Fq. Berlekamp’s method computes residues satisfying b^q=b modulo f by solving a linear system over Fq. [1]
In the basis 1,X,…,X^(n−1), the j-th column of its matrix contains the coefficients of X^(qj) modulo f. Subtract the identity matrix and compute the nullspace. A nonconstant fixed residue can distinguish different irreducible components.
The reason is visible through polynomial CRT. If f has r distinct irreducible factors, its quotient decomposes into r finite fields. A Frobenius-fixed element has, in each component, a value in Fq. Thus the fixed subspace has dimension r over Fq. The linear algebra detects how many independent components are present.
The constant residue one always lies in the kernel, so finding a nonzero kernel vector is not itself evidence of reducibility. The informative quantity is the dimension and the availability of a nonconstant fixed residue.
13. A complete Berlekamp example
Work over F2 with f=X³+X²+X. The polynomial is square-free and equals X(X²+X+1), but we will recover the split through Frobenius. In the quotient, X³=X²+X and X⁴=X.
Squaring the basis elements 1,X,X² therefore gives 1,X²,X. With columns written in that order, the Frobenius matrix and its difference from the identity are:
Q = [1 0 0] Q−I = [0 0 0]
[0 0 1] [0 1 1]
[0 1 0] [0 1 1]
The kernel condition is b1=b2, while b0 is free. A basis is 1 and X+X². Choose b=X²+X. Then b²=X⁴+X²=X+X²=b modulo f.
Now compute gcd(f,b)=X and gcd(f,b−1)=X²+X+1. In characteristic two, b−1=b+1, so the second gcd uses X²+X+1. The factors have been recovered without trying every monic quadratic.
Verification finishes the job. Their product is X³+X²+X; the quadratic is one at both zero and one, so it is irreducible. The two-dimensional fixed subspace agrees with the two distinct factors. Arithmetic, linear algebra and factor count tell the same story.
14. Equal-degree splitting in odd characteristic
Suppose a monic square-free f is a product of irreducible degree-d factors over Fq, with q odd. Choose a polynomial a of degree below degree(f). First compute gcd(a,f); a nontrivial result already splits the polynomial.
If a is coprime to f, compute b=a^((q^d−1)/2) modulo f. In each degree-d field component, b is either one or minus one. If both signs occur across the factors, gcd(f,b−1) separates one set from the other. This is the basic odd-characteristic equal-degree splitting idea associated with Cantor–Zassenhaus. [1,3]
If the gcd is one or f, the chosen a has not separated the components. That is a retry condition, not a declaration of irreducibility. A different choice may give different local signs. Randomness is used to find a useful split; an exact polynomial division verifies any returned split.
This specific exponent formula is not used unchanged in characteristic two. Binary-field splitting uses trace-type constructions or other methods appropriate to characteristic two. Calling every characteristic case by the same name does not make their internal formulas interchangeable.
15. A complete equal-degree split over F5
Let f=X⁴+1 over F5. Its factors are X²+2 and X²+3. Both are irreducible: the nonzero squares in F5 are one and four, whereas their roots would require squares three and two respectively.
Choose a=X+1. It is coprime to f because f(−1)=2, not zero. Here q=5 and d=2, so the splitting exponent is (25−1)/2=12. Repeated squaring modulo X⁴+1 gives b=(X+1)^12=3X².
The two local signs are easy to inspect. Modulo X²+3, we have X²=2, so b=6=1. Modulo X²+2, we have X²=3, so b=9=−1. The sign test distinguishes the two factors.
gcd(X⁴+1, 3X²−1) = X²+3. gcd(X⁴+1, 3X²+1) = X²+2. (X²+3)(X²+2) = X⁴+5X²+6 = X⁴+1 over F5.
There is also a useful intermediate check: b²=9X⁴=−9=1 modulo f. That confirms the sign-valued behaviour across the components. It does not by itself prove that both signs occur; the nontrivial gcd supplies that information.
16. Why randomized discovery can produce exact answers
A randomized splitting routine does not mean the factors are probabilistically valid. It means random choices affect how quickly a useful factor is found. Once a nonconstant proper divisor G is returned and f/G divides exactly, the split is an exact algebraic fact.
There are several distinct outcomes: a proper divisor, an unhelpful gcd of one, an unhelpful gcd of the entire input, or a resource limit reached before a split. An interface should distinguish them. In particular, no split found is not equivalent to irreducible.
For a bounded demonstration, choose the test polynomials explicitly so readers can reproduce the arithmetic. For a general implementation, document the selection method, retry limit and returned status. An incomplete factorisation should retain its unresolved cofactor rather than quietly presenting that cofactor as prime or irreducible.
This separation between search status and mathematical status is the same one encountered in integer factorisation, though the best algorithms and complexity landscapes differ.
17. Reassemble multiplicities and the leading coefficient
Square-free decomposition may produce several components, each with a different multiplicity label. Factor each component, attach its multiplicity to every terminal factor and restore the original leading coefficient. The multiplicity belongs to the factor’s occurrence in the original polynomial, not to the number of times it happened to appear in a search table.
For f=2(X+1)²(X²+1) over F3, the final unit coefficient is two. Returning (X+1)²(X²+1) without it produces a different polynomial. Monic normalisation simplifies algorithms internally; it does not authorise the loss of the original unit.
The strongest final check is reconstruction. Multiply the reported factors to their reported powers, include the unit and reduce every coefficient in Fq. Compare the entire coefficient vector with the original. Matching degrees or a handful of evaluation values is not an adequate substitute.
Matching evaluations can be particularly misleading over small finite fields. Distinct polynomials may induce the same function on the field; X^q−X vanishes at every field element but is not the zero polynomial in Fq[X]. Polynomial equality concerns coefficients, not just the values sampled at q points.
18. An implementation plan with explicit contracts
First establish the field arithmetic and representation. Then normalise f and handle degree-zero and degree-one cases. Compute the formal derivative, extract square-free components and deal with p-th powers recursively. Apply distinct-degree classification to each square-free component, then equal-degree splitting where a degree group contains more than one factor.
Every module should expose its contract. Polynomial division returns quotient and remainder satisfying the reconstruction identity. Gcd returns a monic common divisor with appropriate maximality evidence. A degree-group routine states the degree of each irreducible constituent. A split routine returns either an exact proper factor or an explicit retry/failure status.
The algorithm should not share mutable modulus data carelessly. Removing a factor changes the quotient algebra used in later modular powers. Reusing an old polynomial object while assuming a new modulus is one way for correct formulas to produce incorrect software.
Do not treat assertions as the only input validation in a distributed teaching program. Assertions are useful internal checks, but a public function should deliberately reject the zero polynomial, an invalid coefficient field or unsupported encodings with meaningful errors.
19. Complexity: count the right operations
There are several sizes in this problem: polynomial degree n, field size q, the bit cost of a field element and the representation of Fq. Counting only polynomial multiplications conceals the cost of their coefficients; counting only bit length conceals useful algebraic structure.
Dense polynomial multiplication by the school algorithm uses a quadratic number of coefficient operations. Modular exponentiation uses a number of such multiplications proportional to the exponent’s bit length. A dense n-by-n nullspace calculation has a different cost and memory profile from an equal-degree splitting routine.
These baseline counts explain tradeoffs without asserting that every library uses the same implementation. Fast multiplication, modular composition, sparse structure and specialised field arithmetic may change practical performance. Author documentation should be consulted before attributing a particular algorithm to a software system. [3]
For a classroom polynomial, transparency usually matters more than shaving a few operations. For a large computation, use a mature exact algebra system and preserve the field specification, factorisation output and reconstruction check so that the result remains reproducible.
20. Practice set
1. Why is no root sufficient for irreducibility in degrees two and three but not four? 2. Expand (X²+1)(X²+X+2) over F3. 3. Show that both factors are irreducible. 4. Differentiate X⁴+2X³+2X²+2X+1 over F3 and find its gcd with the original polynomial.
5. Explain why X³+1 has zero derivative over F3. 6. Completely factor X⁶+2X³+1 over F3. 7. Which irreducible degrees occur in X^(q^6)−X? 8. Why should X^(q^d) be reduced modulo f during computation?
9. For a degree-six irreducibility test, which intermediate exponents occur in the prime-divisor criterion? 10. Find X⁴ modulo X³+X²+X over F2. 11. Find a nonconstant Frobenius-fixed residue for that quotient. 12. Use it to split the cubic.
13. Factor X⁴+1 over F5 and verify the product. 14. Explain why a failed equal-degree split does not prove irreducibility. 15. What information is lost by dropping the leading coefficient? 16. Why can checking all base-field evaluations still fail to prove polynomial equality?
21. Answers and worked checks
1. A proper factorisation of a degree-two or degree-three polynomial includes a degree-one factor. A degree-four polynomial can instead split as two quadratics. 2. The expansion is X⁴+X³+X+2 after coefficient reduction. 3. Substitution at zero, one and two gives no zero for either quadratic.
4. The derivative is X³+X+2. The monic gcd is X+1, exposing the repeated linear factor. 5. The formal derivative is 3X², which is zero in characteristic three. 6. First take the cube root to get X²+2X+1=(X+1)²; the original is (X+1)⁶.
7. The degrees are the positive divisors of six: one, two, three and six. Degree four and degree five do not occur. 8. Only the remainder affects the gcd, and its degree stays below degree(f), avoiding an enormous unreduced polynomial.
9. The prime divisors of six are two and three. In addition to the final q^6 equality, check gcds involving X^(q³)−X and X^(q²)−X. 10. From X³=X²+X, multiply by X to get X⁴=X³+X²=X.
11. b=X²+X is fixed because b²=X⁴+X²=X+X². 12. gcd(f,b)=X and gcd(f,b+1)=X²+X+1. 13. The factors are X²+2 and X²+3. Their product is X⁴+5X²+6=X⁴+1 in F5, and neither quadratic has a root in F5.
14. A choice may give the same sign in every component, yielding gcd one or the entire polynomial. Another choice may split it. 15. The returned product can differ by a nonzero scalar, so it no longer equals the original polynomial. 16. A nonzero polynomial such as X^q−X can vanish at every element of Fq; coefficient comparison is the exact equality check.
22. From factoring to learning
The subject becomes much easier to organise when each intermediate result has a name. Square-free does not mean irreducible. No linear factor does not mean no factor. An equal-degree block is not a terminal factor. A proper divisor is not necessarily irreducible. A random search failure is not a proof of impossibility.
A useful lesson asks students to label every line of a factorisation with the claim it establishes. That makes hidden assumptions visible. The calculation can then be checked in both directions: forward from input to factors and backward from the reported factors to the input.
The deeper connection is to field construction. An irreducible polynomial is not merely a factorisation endpoint; it can become the defining modulus for a new finite field. Conversely, field structure supplies the Frobenius theorem that makes factorisation efficient. Each side supports the other.
Sources and further study
[1] Arne Storjohann, University of Waterloo, Factoring Polynomials over Finite Fields, CS 487/687 notes: square-free structure, Frobenius and splitting. [2] Victor Shoup, A Computational Introduction to Number Theory and Algebra, Chapters 19–20: irreducibility and finite-field algorithms. [3] Victor Shoup, NTL finite-field polynomial factorisation documentation, for an implementation-oriented reference; the formulas and small worked examples above are presented independently of any claim about the fastest current software.
Continue through Batch 03
Return to Guide 9: Finite Fields and Polynomial Arithmetic to rebuild the coefficient arithmetic. Continue to Guide 11: p-Adic Valuations and Hensel Lifting for increasing prime-power precision. Guide 12: Arithmetic Functions, Möbius Inversion and Sieves explains the divisor inversion behind counting irreducible polynomials.