Overview

  • How can irreducibility be tested without a complete factorization?
  • How many monic irreducible polynomials have a given degree?
  • How can an irreducible polynomial be constructed and checked?

The Frobenius identity

For every m≥1m\ge1, xqm−x=∏P monic irreducible in Fq[x]deg⁡P∣mP(x).x^{q^m}-x=\prod_{\substack{P\text{ monic irreducible in }\mathbb F_q[x]\\ \deg P\mid m}}P(x). A root of an irreducible polynomial of degree dd belongs to Fqm\mathbb F_{q^m} exactly when d∣md\mid m. The derivative −1-1 ensures that each factor occurs once.

This identity turns factor degrees into polynomial gcd computations. The required powers are computed modulo the polynomial under study; there is no need to write out xqmx^{q^m}.

References 1

The irreducibility criterion

Theorem (Frobenius-power criterion)

A monic polynomial f∈Fq[x]f\in\mathbb F_q[x] of degree n≥1n\ge1 is irreducible if and only if

xqn≡x(modf),gcd⁡(f,xqn/ℓ−x)=1for every prime ℓ∣n.x^{q^n}\equiv x\pmod f,\qquad \gcd\bigl(f,x^{q^{n/\ell}}-x\bigr)=1\quad\text{for every prime }\ell\mid n.

The first condition makes ff squarefree and forces every factor degree to divide nn. If a proper divisor d∣nd\mid n occurred as a factor degree, some prime ℓ∣n/d\ell\mid n/d would give d∣n/ℓd\mid n/\ell, contradicting the corresponding gcd. The reverse implication follows from the same Frobenius identity. The criterion uses modular exponentiation and Euclidean gcds, without expanding the powers as polynomials.

References 2

Connections and evidence

Classical

Rabin’s criterion: a complete finite-field irreducibility certificate

One Frobenius congruence and gcd tests at the maximal proper divisors of the degree give a necessary and sufficient test, and a certified construction of Fqn\mathbb F_{q^n}.

Scope. Let qq be any prime power and f∈Fq[X]f\in\mathbb F_q[X] monic of degree n≥1n\ge1. The gcd conditions range over every distinct prime divisor ℓ∣n\ell\mid n; for n=1n=1 this list is empty.

Rabin’s criterion: a complete finite-field irreducibility certificateOne Frobenius congruence and gcd tests at the maximal proper divisors of the degree give a necessary and sufficient test, and a certified construction of \(\mathbb F_{q^n}\). Connection 1: Frobenius factor-degree identity is an input to Final Frobenius congruence. The congruence \(X^{q^n}\equiv X\pmod f\) holds exactly when \(f\) is squarefree and every irreducible factor degree divides \(n\). Connection 2: Frobenius factor-degree identity is an input to Every maximal-divisor gcd is 1. The gcd at \(n/\ell\) is one exactly when no irreducible factor degree divides \(n/\ell\). Connection 3: Final Frobenius congruence is an input to AND. This condition supplies squarefreeness as well as the allowable factor degrees. Connection 4: Every maximal-divisor gcd is 1 is an input to AND. Every prime divisor of the total degree must be checked, without omitting a gcd test. Connection 5: AND is equivalent to f is irreducible over Fq. The conjunction rules out every proper factor degree, and every irreducible polynomial passes all these tests. Connection 6: f is irreducible over Fq is equivalent to Quotient is the field Fqⁿ. The quotient \(\mathbb F_q[X]/(f)\) is a field exactly when \(f\) is irreducible, and then it has \(q^n\) elements. Connection 7: Modular powering and Euclidean gcd is an input to Final Frobenius congruence. Repeated modular powering evaluates the final congruence without expanding the enormous Frobenius power. Connection 8: Modular powering and Euclidean gcd is an input to Every maximal-divisor gcd is 1. The same modular powers supply each gcd input; the Euclidean algorithm certifies the required coprimality.Frobenius factor-degree identity — related articleFrobenius factor-degreeidentityFinal Frobenius congruence — related articleFinal FrobeniuscongruenceEvery maximal-divisor gcd is 1 — related articleEvery maximal-divisorgcd is 1ANDANDf is irreducible over Fq — related articlef is irreducible over FqQuotient is the field Fqⁿ — related articleQuotient is the field FqⁿModular powering and Euclidean gcd — related articleModular powering andEuclidean gcdConnection 1: The congruence \(X^{q^n}\equiv X\pmod f\) holds exactly when \(f\) is squarefree and every irreducible factor degree divides \(n\).Interpret first test [1]Connection 2: The gcd at \(n/\ell\) is one exactly when no irreducible factor degree divides \(n/\ell\).Interpret exclusion tests[2]Connection 3: This condition supplies squarefreeness as well as the allowable factor degrees.Divisibility condition [3]Connection 4: Every prime divisor of the total degree must be checked, without omitting a gcd test.All exclusion conditions[4]Connection 5: The conjunction rules out every proper factor degree, and every irreducible polynomial passes all these tests.Rabin criterion [5]Connection 6: The quotient \(\mathbb F_q[X]/(f)\) is a field exactly when \(f\) is irreducible, and then it has \(q^n\) elements.Maximal principal ideal[6]Connection 7: Repeated modular powering evaluates the final congruence without expanding the enormous Frobenius power.Compute in the quotient[7]Connection 8: The same modular powers supply each gcd input; the Euclidean algorithm certifies the required coprimality.Residues and gcdcertificates [8]
Linked nodes open articles; numbered connections open the evidence below.Open full-size diagram

deduction or information flow equivalenceAND joint hypotheses

The complete criterion is

f irreducible⟺{Xqn≡X(modf),gcd⁡ ⁣(f,Xqn/ℓ−X)=1for every prime ℓ∣n.f\text{ irreducible}\quad\Longleftrightarrow\quad\begin{cases}X^{q^n}\equiv X\pmod f,\\[2pt]\gcd\!\left(f,X^{q^{n/\ell}}-X\right)=1&\text{for every prime }\ell\mid n.\end{cases}

Here is the proof for arbitrary prime powers, extending the identical prime-field argument in Rabin’s original report. The roots of Xqm−XX^{q^m}-X form Fqm\mathbb F_{q^m}; its derivative is −1-1. Consequently it is the product, once each, of the monic irreducible polynomials over Fq\mathbb F_q whose degrees divide mm. The first congruence therefore makes ff squarefree with all factor degrees dividing nn. If a proper factor degree d∣nd\mid n occurred, choose a prime ℓ∣n/d\ell\mid n/d. Then d∣n/ℓd\mid n/\ell, contradicting that gcd test. Conversely, an irreducible degree-nn polynomial passes both conditions.

No preliminary squarefreeness assumption is needed. For n=1n=1, the empty gcd list causes no exception. All powers may be reduced modulo ff throughout.

For f=X4+X+1f=X^4+X+1 over F2\mathbb F_2, the relation X4≡X+1X^4\equiv X+1 gives X8≡X2+1X^8\equiv X^2+1 and X16≡XX^{16}\equiv X. The only prime divisor of four is two, and X4−X≡1(modf)X^4-X\equiv1\pmod f. These computations certify irreducibility and realize the field with sixteen elements as F2[X]/(f)\mathbb F_2[X]/(f).

Inspect all 8 connections and exact references
Evidence for each connection
ConnectionStatement and source
1Frobenius factor-degree identity → Final Frobenius congruenceConstruction / input

The congruence Xqn≡X(modf)X^{q^n}\equiv X\pmod f holds exactly when ff is squarefree and every irreducible factor degree divides nn.

  • R1 · Rabin (1979)§1, Lemma 1 and proof, printed pp. 7–8; quotient construction p. 6The report states the lemma over a prime field. The same subfield argument gives the displayed prime-power version; the proof is included below.Primary source
2Frobenius factor-degree identity → Every maximal-divisor gcd is 1Construction / input

The gcd at n/ℓn/\ell is one exactly when no irreducible factor degree divides n/ℓn/\ell.

  • R1 · Rabin (1979)§1, Lemma 1 and proof, printed pp. 7–8; quotient construction p. 6The report states the lemma over a prime field. The same subfield argument gives the displayed prime-power version; the proof is included below.Primary source
3Final Frobenius congruence → ANDConstruction / input

This condition supplies squarefreeness as well as the allowable factor degrees.

4Every maximal-divisor gcd is 1 → ANDConstruction / input

Every prime divisor of the total degree must be checked, without omitting a gcd test.

5AND ↔ f is irreducible over FqEquivalence

The conjunction rules out every proper factor degree, and every irreducible polynomial passes all these tests.

  • R1 · Rabin (1979)§1, Lemma 1 and proof, printed pp. 7–8; quotient construction p. 6The report states the lemma over a prime field. The same subfield argument gives the displayed prime-power version; the proof is included below.Primary source
6f is irreducible over Fq ↔ Quotient is the field FqⁿEquivalence

The quotient Fq[X]/(f)\mathbb F_q[X]/(f) is a field exactly when ff is irreducible, and then it has qnq^n elements.

  • R1 · Rabin (1979)§1, Lemma 1 and proof, printed pp. 7–8; quotient construction p. 6The report states the lemma over a prime field. The same subfield argument gives the displayed prime-power version; the proof is included below.Primary source
7Modular powering and Euclidean gcd → Final Frobenius congruenceConstruction / input

Repeated modular powering evaluates the final congruence without expanding the enormous Frobenius power.

  • R2 · Rabin (1979)§1, discussion following Lemma 1, printed pp. 8–9Earlier author report of the work published as Rabin (1980), SIAM Journal on Computing 9, 273–280.Primary source
8Modular powering and Euclidean gcd → Every maximal-divisor gcd is 1Construction / input

The same modular powers supply each gcd input; the Euclidean algorithm certifies the required coprimality.

  • R2 · Rabin (1979)§1, discussion following Lemma 1, printed pp. 8–9Earlier author report of the work published as Rabin (1980), SIAM Journal on Computing 9, 273–280.Primary source

Sources and scope checked .

Example

Example

Take f=x4+x+1∈F2[x]f=x^4+x+1\in\mathbb F_2[x]. Repeated squaring modulo ff gives

x4≡x+1,x8≡x2+1,x16≡x.x^4\equiv x+1,\qquad x^8\equiv x^2+1,\qquad x^{16}\equiv x.

The only prime divisor of n=4n=4 is 22, and x4−x≡1(modf)x^4-x\equiv1\pmod f. Thus the required gcd is one, and ff is irreducible. Its splitting field has 16 elements, and the Galois group over F2\mathbb F_2 has order four.

The congruence x16≡x(modf)x^{16}\equiv x\pmod f alone does not suffice: the reducible quartic x4+x=x(x+1)(x2+x+1)x^4+x=x(x+1)(x^2+x+1) also divides x16−xx^{16}-x. The gcd conditions eliminate smaller-degree factors.

References 1
  • Rabin1980Application of the exact criterion; the displayed remainders are direct calculations.Source

Counting irreducible polynomials

Let Nq(n)N_q(n) count monic irreducibles of degree nn over Fq\mathbb F_q. Taking degrees in the Frobenius identity gives

Derivation

qm=∑d∣mdNq(d),Nq(n)=1n∑d∣nμ(d)qn/d.q^m=\sum_{d\mid m}dN_q(d),\qquad N_q(n)=\frac1n\sum_{d\mid n}\mu(d)q^{n/d}.

The second identity is Möbius inversion; μ\mu is the Möbius function. Bounding the proper-divisor terms by the geometric sum ∑j=1⌊n/2⌋qj≤2qn/2\sum_{j=1}^{\lfloor n/2\rfloor}q^j\le2q^{n/2} gives Nq(n)=qn/n+O(qn/2/n)N_q(n)=q^n/n+O(q^{n/2}/n), uniformly for q≥2q\ge2. Thus a uniform monic polynomial is irreducible with probability asymptotic to 1/n1/n as n→∞n\to\infty, even for fixed qq.

Example

N2(6)=64−8−4+26=9.N_2(6)=\frac{64-8-4+2}{6}=9.

Thus nine of the 64 monic binary sextics are irreducible. All nine have constant coefficient one, so nine of the 32 constant-one sextics are irreducible.

References 1

Construction algorithms

Choose independent uniform monic polynomials of degree nn, and apply the Frobenius test until one is irreducible. The output is always correct; only the running time is random. The expected number of trials is qn/Nq(n)q^n/N_q(n), asymptotic to nn. For n≥2n\ge2, sampling only nonzero constant coefficients reduces it to (q−1)qn−1/Nq(n)(q-1)q^{n-1}/N_q(n). For binary sextics this is exactly 32/932/9.

If Fqn\mathbb F_{q^n} is already represented, choose α\alpha outside every maximal proper subfield: αqn/ℓ≠α\alpha^{q^{n/\ell}}\ne\alpha for each prime ℓ∣n\ell\mid n. Its minimal polynomial is ∏i=0n−1(x−αqi)\prod_{i=0}^{n-1}(x-\alpha^{q^i}), of degree nn.

Shoup develops deterministic construction algorithms and precise complexity bounds. The dependence on the characteristic matters: a bound polynomial in pp is not necessarily polynomial in its bit length log⁡p\log p.

References 3

Further conditions

An irreducible polynomial gives a field extension. Requiring its roots to generate the multiplicative group is an additional condition: such a polynomial is called primitive. Normality is another condition, concerning a basis of Frobenius conjugates. See primitive and normal elements.

Prescribing coefficients or requiring few nonzero terms restricts the candidates before the test is applied. Existence theorems for these restrictions are treated in coefficient restrictions and sparse polynomials.

References 2

Parity of the number of factors

Let qq be odd and let f∈Fq[x]f\in\mathbb F_q[x] be squarefree of degree nn, with rr irreducible factors. Frobenius has rr cycles on its roots, so its sign is (−1)n−r(-1)^{n-r}. The discriminant is a square in Fq×\mathbb F_q^\times if and only if this sign is positive. Thus the discriminant determines the parity of rr, but usually not whether r=1r=1.

In characteristic two, every element of the ground field is a square. Swan's theorem instead uses a discriminant calculation after lifting to characteristic zero. It gives useful obstructions to irreducibility of binary trinomials; see the sparse-polynomial examples.

References 1
  • Swan1962 · Theorem 1 and added-in-proof attribution, pp.1099–1100The basic theorem is credited by Swan to Stickelberger, with Dalen’s prior proof noted.Source

Questions

Research directionFinite fields

Which prescribed supports admit irreducibles over a fixed finite field?

Scope. A specified finite field, degree, and support

The counting formula proves existence without coefficient restrictions. A prescribed support or coefficient pattern may force factors, and existence must then be studied for that pattern. Exact certificates can establish individual cases; a general result requires a uniform argument.

References 3
Discuss this question →

Related topics

References

  1. Finite Fields

    Lidl, Rudolf and Niederreiter, Harald. Edition 2. Cambridge University Press, Encyclopedia of Mathematics and its Applications, vol. 20, 1997.

    Read the source
  2. Probabilistic algorithms in finite fields

    Rabin, Michael O. SIAM Journal on Computing, 9(2), 273–280, 1980.

    Read the source
  3. FLINT documentation: polynomial factorization algorithms

    The FLINT Team.

    Read the source
  4. New algorithms for finding irreducible polynomials over finite fields

    Shoup, Victor. Mathematics of Computation, 54, 435–447, 1990.

    Read the source
  5. Fast construction of irreducible polynomials over finite fields

    Shoup, Victor. Journal of Symbolic Computation, 17, 371–391, 1994.

    Read the source
  6. Primitive polynomials over finite fields

    Hansen, Tom and Mullen, Gary L. Mathematics of Computation, 59(200), 639–643, 1992.

    Read the source
  7. Factorization of polynomials over finite fields

    Swan, Richard G. Pacific Journal of Mathematics, 12(3), 1099–1106, 1962.

    Read the source
  8. Handbook of Finite Fields

    Mullen, Gary L. and Panario, Daniel (editors). CRC Press, 2013.

    Read the source
  9. Probabilistic Algorithm in Finite Fields

    Rabin, Michael O. MIT Laboratory for Computer Science, MIT-LCS-TR-213, 1979.

    Read the source