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 , A root of an irreducible polynomial of degree belongs to exactly when . The derivative 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 .
References 1
- LidlNiederreiter1997 · Chapter 3, irreducible polynomialsSource
The irreducibility criterion
Theorem (Frobenius-power criterion)
A monic polynomial of degree is irreducible if and only if
The first condition makes squarefree and forces every factor degree to divide . If a proper divisor occurred as a factor degree, some prime would give , 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
- Rabin1980Irreducibility testing in finite-field algorithms.Source
- FLINTFactorizationDocumentation · Irreducibility testing over finite fields, Theorem 1Official documentation states the criterion and its exact algorithmic use.Source
Connections and evidence
ClassicalRabin’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 .
Scope. Let be any prime power and monic of degree . The gcd conditions range over every distinct prime divisor ; for this list is empty.
→ deduction or information flow↔ equivalenceAND joint hypotheses
The complete criterion is
Here is the proof for arbitrary prime powers, extending the identical prime-field argument in Rabin’s original report. The roots of form ; its derivative is . Consequently it is the product, once each, of the monic irreducible polynomials over whose degrees divide . The first congruence therefore makes squarefree with all factor degrees dividing . If a proper factor degree occurred, choose a prime . Then , contradicting that gcd test. Conversely, an irreducible degree- polynomial passes both conditions.
No preliminary squarefreeness assumption is needed. For , the empty gcd list causes no exception. All powers may be reduced modulo throughout.
For over , the relation gives and . The only prime divisor of four is two, and . These computations certify irreducibility and realize the field with sixteen elements as .
Inspect all 8 connections and exact references
| Connection | Statement and source |
|---|---|
| 1Frobenius factor-degree identity → Final Frobenius congruenceConstruction / input | The congruence holds exactly when is squarefree and every irreducible factor degree divides .
|
| 2Frobenius factor-degree identity → Every maximal-divisor gcd is 1Construction / input | The gcd at is one exactly when no irreducible factor degree divides .
|
| 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.
|
| 6f is irreducible over Fq ↔ Quotient is the field FqⁿEquivalence | The quotient is a field exactly when is irreducible, and then it has elements.
|
| 7Modular powering and Euclidean gcd → Final Frobenius congruenceConstruction / input | Repeated modular powering evaluates the final congruence without expanding the enormous Frobenius power.
|
| 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.
|
Sources and scope checked .
Example
Example
Take . Repeated squaring modulo gives
The only prime divisor of is , and . Thus the required gcd is one, and is irreducible. Its splitting field has 16 elements, and the Galois group over has order four.
The congruence alone does not suffice: the reducible quartic also divides . The gcd conditions eliminate smaller-degree factors.
Counting irreducible polynomials
Let count monic irreducibles of degree over . Taking degrees in the Frobenius identity gives
Derivation
The second identity is Möbius inversion; is the Möbius function. Bounding the proper-divisor terms by the geometric sum gives , uniformly for . Thus a uniform monic polynomial is irreducible with probability asymptotic to as , even for fixed .
Example
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
- LidlNiederreiter1997 · Chapter 3, counting irreducible polynomialsSource
Construction algorithms
Choose independent uniform monic polynomials of degree , 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 , asymptotic to . For , sampling only nonzero constant coefficients reduces it to . For binary sextics this is exactly .
If is already represented, choose outside every maximal proper subfield: for each prime . Its minimal polynomial is , of degree .
Shoup develops deterministic construction algorithms and precise complexity bounds. The dependence on the characteristic matters: a bound polynomial in is not necessarily polynomial in its bit length .
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 be odd and let be squarefree of degree , with irreducible factors. Frobenius has cycles on its roots, so its sign is . The discriminant is a square in if and only if this sign is positive. Thus the discriminant determines the parity of , but usually not whether .
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.
Questions
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.
Related topics
Connected diagrams
- How can several local tests prove irreducibility? · Classical
- How do two modular factorizations determine S₅? · Classical
Finite fields and Frobenius
The test follows from the description of Frobenius orbits.
UsesIrreducible polynomials with coefficient restrictions
Construct irreducibles with prescribed coefficients.
UsesPolynomial factorization algorithms
Continue from testing to a complete factorization.
UsesFactorization statistics over finite fields
Count all factorization types.
UsesSparse irreducible polynomials over finite fields
Apply the test to sparse candidates.
Linked from 12 articles
- Field extensions and minimal polynomials
- Reduction modulo primes
- Capelli’s theorem and polynomial composition
- Littlewood polynomials
- Inverse Galois theory and generic polynomials
- Finite fields and Frobenius
- Irreducible polynomials with coefficient restrictions
- Primitive and normal elements
- Factorization statistics over finite fields
- Sparse irreducible polynomials over finite fields
- Polynomial fibers and Bertini’s theorem
- Polynomial factorization algorithms
References
- Finite Fields
Lidl, Rudolf and Niederreiter, Harald. Edition 2. Cambridge University Press, Encyclopedia of Mathematics and its Applications, vol. 20, 1997.
Read the source - Probabilistic algorithms in finite fields
Rabin, Michael O. SIAM Journal on Computing, 9(2), 273–280, 1980.
Read the source - FLINT documentation: polynomial factorization algorithms
The FLINT Team.
Read the source - New algorithms for finding irreducible polynomials over finite fields
Shoup, Victor. Mathematics of Computation, 54, 435–447, 1990.
Read the source - Fast construction of irreducible polynomials over finite fields
Shoup, Victor. Journal of Symbolic Computation, 17, 371–391, 1994.
Read the source - Primitive polynomials over finite fields
Hansen, Tom and Mullen, Gary L. Mathematics of Computation, 59(200), 639–643, 1992.
Read the source - Factorization of polynomials over finite fields
Swan, Richard G. Pacific Journal of Mathematics, 12(3), 1099–1106, 1962.
Read the source - Handbook of Finite Fields
Mullen, Gary L. and Panario, Daniel (editors). CRC Press, 2013.
Read the source - Probabilistic Algorithm in Finite Fields
Rabin, Michael O. MIT Laboratory for Computer Science, MIT-LCS-TR-213, 1979.
Read the source
Comments
Any comments are welcome. Comments appear after the site owner approves them. Privacy policy.