Overview
- How does Frobenius separate factors over a finite field?
- How are modular factors lifted and recombined over the rationals?
- What do modular-composition bounds imply for factorization?
Finite-field factorization
Let the polynomial have coefficients in . A squarefree decomposition separates repeated factors, using gcds with the derivative. If the derivative vanishes, the polynomial is a -th power over the finite field and one first takes its -th root.
For a squarefree polynomial, selects its irreducible factors whose degrees divide . Removing the factors already found and repeating the gcd calculation gives a distinct-degree decomposition. Equal-degree splitting then separates factors of the same degree. Cantor–Zassenhaus uses random choices for this splitting step; the output consists of exact polynomial factors whose product and irreducibility can be checked.
References 2
- CantorZassenhaus1981Source
- GathenGerhard2013Squarefree, distinct-degree, and equal-degree factorization.Source
Berlekamp's algorithm
Proposition
If is squarefree with distinct irreducible factors, then
Indeed, the Chinese remainder theorem identifies the quotient with a product . The fixed elements of Frobenius on each component are exactly . Finding the fixed subspace is linear algebra. A fixed element assumes constant values on the components; gcds , for , separate components with different values.
Example
Over , take . Since , it is squarefree. In the quotient, , and solving gives the basis . Thus there are three irreducible factors. The gcds from first split off ; those from split the remaining cubic. The result is
The quadratic has no root in , which completes the factorization.
References 1
- Berlekamp1967Frobenius-fixed algebra and the linear-algebra factorization method.Source
Modular composition
The operation modular composition takes , with monic of degree and , and computes . It avoids storing a composition whose unreduced degree can be nearly .
Frobenius as modular composition
In , put . For every ,
The coefficients are fixed by the -power map. Thus one application of Frobenius is a modular composition. Iterates of this map supply the powers used in distinct-degree factorization and irreducibility tests.
Example
Over , take . Since in the quotient, applying Frobenius to gives
Equivalently, compose with and reduce modulo .
Brent–Kung's baby-step/giant-step method groups powers of into blocks and combines them by matrix multiplication. Later methods encode small algebraic relations between and in polynomial matrices, or reduce the task to multivariate evaluation. Both approaches avoid forming the full intermediate composition.
References 3
- BrentKung1978 · Composition algorithms; see also Neiger–Salvy–Schost–Villard (2024), Section 1.1, for modular compositionSource
- KedlayaUmans2011 · Sections 3 and 7Source
- NeigerSalvySchostVillard2024 · Section 1.1 and Theorem 1.1Source
Complexity bounds
A field-operation count charges unit cost for arithmetic in . A bit-operation count includes the representation and size of coefficients. Over , these are not interchangeable uniformly in . Modular composition is one step of a factorization algorithm.
| Source | Precise scope | Contribution |
|---|---|---|
| Kedlaya–Umans (2011) | Modular composition over ; bit complexity | For each fixed , bit operations in sufficiently large degree. This leads to a randomized finite-field factorization bound, displayed below. |
| Neiger–Salvy–Schost–Villard (2024) | Arbitrary fields of known characteristic; arithmetic complexity | A Las Vegas method with expected field operations. Small finite fields are handled through a suitably enlarged extension; a failed randomized trial is detected. |
| Neiger–Salvy–Schost–Villard (2026) | Fixed , generic inner polynomial ; arithmetic complexity | Two relation matrices give field operations. Here is a feasible square-matrix multiplication exponent. The genericity requirement is essential. |
| van der Hoeven–Lecerf (2026) | Modular composition over ; bit complexity | A sharper nearly linear bound via spiroids and Fourier transforms with proved precision control. Prime finite fields are a special case. |
The Kedlaya–Umans randomized factorization bound is
A faster modular-composition subroutine does not by itself turn this exponent into . Guo–Narayanan–Umans (2016) organize related algebraic problems through reductions that would transfer an improvement below the factorization exponent . These reductions do not establish an optimal lower bound.
Conditional approach. Umans–Wang (2025) propose structured sets of integers with a divisibility-covering property as a route to faster factorization. Their proposed improvement depends on a number-theoretic conjecture; it is not an unconditional algorithm beating . The paper was listed for ISAAC in December 2026 when checked on 12 November; the reference below identifies the available preprint.
References 6
- KedlayaUmans2011 · Corollary 7.2 and finite-field factorization resultsSource
- NeigerSalvySchostVillard2024 · Theorem 1.1 and the following discussion of sampling and small finite fieldsSource
- NeigerSalvySchostVillard2026 · Theorem 1.3 and the paragraph immediately following itSource
- HoevenLecerf2026 · Theorem 1 and Sections 1.3–1.4; author version dated 12 August 2026Source
- GuoNarayananUmans2016 · Introduction and reduction theoremsSource
- UmansWang2025 · Abstract and introduction; conditional strategySource
Hensel lifting and recombination
Let be monic and squarefree. Choose a prime where its reduction remains squarefree, factor there, and lift the pairwise coprime factors modulo by Hensel's lemma. Coprimality permits the correction equations to be solved at each stage.
A rational factor may be a product of several lifted factors. Recombination determines which products descend to . Bounds for the coefficients of a genuine factor turn sufficiently accurate modular coefficients into unique candidate integers. Exact division then accepts or rejects a candidate.
Reducibility modulo alone gives no rational factor, since the local factors need not descend separately. An irreducible good reduction, however, proves rational irreducibility immediately.
References 2
- Zassenhaus1969Source
- GathenGerhard2013Hensel lifting, coefficient bounds, and modular factorization.Source
Local factorization and higher Newton polygons
Local factorization over remains possible when every factor of is repeated. A residual polynomial separates roots that share a Newton slope; higher Newton polygons continue when that residual information is insufficient. The Montes method organizes successive slopes, residue-field extensions, and polynomial representatives into types. Complete types identify irreducible local factors and their ramification indices and residue degrees.
Guàrdia–Montes–Nart give the underlying theory and an algorithm for prime ideal decomposition and discriminants. Poteaux–Weimann's ISSAC 2022 paper improves local factorization through Hensel lifting adapted to these valuations and a divide-and-conquer strategy. Its sharper complexity bound assumes residue characteristic zero or greater than the polynomial degree; residual-field factorization costs are accounted for separately.
A local factor is represented to a stated -adic precision together with exact structural data; its coefficients need not be rational. Recovering rational factors still requires global recombination and certification.
References 3
- GuardiaMontesNart2012Newton · §§2–4Higher-order polygon and residual-polynomial theory.Source
- GuardiaMontesNart2011Montes · §2.2, Theorem 2.2; §3Complete types and the optimized Montes method.Source
- PoteauxWeimann2022Local · Assumption 1; §§4–5, Theorems 3–4Published algorithmic improvements; assumptions and residual-field costs remain explicit.Source
Okutsu approximations
An Okutsu frame records successive polynomial approximations to a local irreducible factor. Guàrdia, Montes, and Nart identify these frames with strongly optimal complete types built from higher Newton polygons. The Montes algorithm computes a frame and an Okutsu approximation for each irreducible factor of a monic separable polynomial over the valuation ring of a local field with perfect residue field.
The approximations can be refined to a prescribed coefficient precision. In the tamely ramified case, an Okutsu approximation defines an isomorphic field extension. That last assertion needs the tame hypothesis; a useful approximation is not, by itself, a proof of equality of wildly ramified extensions.
References 1
- GuardiaMontesNart2010Okutsu · Theorems 3.5 and 3.9; Proposition 4.4; §§4.2–4.3Source
Lattice reduction
The number of subsets of lifted factors is exponential in the number of factors. The Lenstra–Lenstra–Lovász theorem gives a deterministic algorithm for factoring rational polynomials in time polynomial in their degree and coefficient bit size, using lattice reduction. The lattice encodes congruence information; short vectors reveal relations compatible with a genuine factor.
Van Hoeij recasts practical recombination through a structured knapsack problem. Modern variants, including FLINT’s implementation, use logarithmic derivatives to turn products into sums, so a prospective factor corresponds to a vector of choices among local factors. Lattice reduction narrows the possible choice vectors before expensive exact tests. Belabas–van Hoeij–Klüners–Steel (2009) proved polynomial-time complexity for van Hoeij’s original rational-polynomial algorithm and natural variants. This recombination method uses local information to find exact global factors.
References 4
- LLL1982Polynomial-time factorization over Q.Source
- VanHoeij2002Recombination by knapsack and lattice methods.Source
- BHKS2009Polynomial-time analysis of van Hoeij’s original rational-polynomial factorization algorithm and natural variants.Source
- FLINTFactorizationDocumentation · Factoring polynomials over the integers: Van Hoeij’s algorithm and ComplexityImplementation-oriented explanation of modular factorization.Source
Factorization certificates
The identity proves a factorization, but not its completeness. Completeness additionally requires proof that each is irreducible over the stated field. A modular irreducibility witness, a proved algorithm, or a suitable exact criterion can supply that step. A complete certificate specifies the coefficient field, normalization, multiplicities, and irreducibility proofs.
In a Las Vegas algorithm, random choices affect the runtime, while every returned factorization is correct. Numerical methods require exact verification before their output gives a factorization certificate.
References 2
- GathenGerhard2013Source
- Rabin1980Finite-field algorithms and exact irreducibility tests.Source
Questions
Is irreducibility over Q decidable in polynomial time?
Scope. Dense univariate polynomials given by rational coefficients in binary
Yes. LLL gives polynomial-time factorization in the degree and coefficient bit size. The bound applies to dense binary input; it does not give the same complexity for every sparse encoding or extension-field representation.
Can the 2026 generic composition bound be extended to arbitrary input?
Scope. Algebraic modular composition over a field; the two-relation-matrix method
For each degree- modulus , Theorem 1.3 supplies a nonempty Zariski-open set of coefficient vectors for on which the faster bound holds. The algorithm can detect failure of its genericity conditions and fall back on another method. The authors explicitly leave a Las Vegas reduction for arbitrary input to future work. A nonempty Zariski-open set over an algebraic closure need not contain a point over a small finite base field; “generic” must not be silently replaced by “every.”
References 1
- NeigerSalvySchostVillard2026 · Theorem 1.3 and following paragraphSource
Related topics
Connected diagrams
Browse all diagrams →Irreducibility over finite fields
Frobenius tests certify the finite-field factors.
GeneralizesReduction modulo primes
An irreducible good reduction can terminate a rational factorization algorithm.
Applies toAlgorithms for Galois groups
A group computation begins with exact factorization and separability checks.
UsesNewton polygons and Galois groups
Residual polynomials and higher Newton polygons determine local factorization data.
References
- A new algorithm for factoring polynomials over finite fields
Cantor, David G. and Zassenhaus, Hans. Mathematics of Computation, 36(154), 587–592, 1981.
Read the source - Modern Computer Algebra
von zur Gathen, Joachim and Gerhard, Jürgen. Edition 3. Cambridge University Press, 2013.
Read the source - Factoring polynomials over finite fields
Berlekamp, Elwyn R. Bell System Technical Journal, 46(8), 1853–1859, 1967.
Read the source - Fast algorithms for manipulating formal power series
Brent, Richard P. and Kung, Hsiang-Tsung. Journal of the ACM, 25(4), 581–595, 1978.
Read the source - Fast polynomial factorization and modular composition
Kedlaya, Kiran S. and Umans, Christopher. SIAM Journal on Computing, 40(6), 1767–1802, 2011.
Read the source - Faster modular composition
Neiger, Vincent and Salvy, Bruno and Schost, Éric and Villard, Gilles. Journal of the ACM, 71(2), Article 11, 2024.
Read the source - Faster modular composition using two relation matrices
Neiger, Vincent and Salvy, Bruno and Schost, Éric and Villard, Gilles. Proceedings of the 51st International Symposium on Symbolic and Algebraic Computation (ISSAC 2026), 315–324, 2026.
Read the source - Fast modular composition using spiroids
van der Hoeven, Joris and Lecerf, Grégoire. Journal of Complexity, 96, 102073, 2026.
Read the source - Algebraic problems equivalent to beating exponent 3/2 for polynomial factorization over finite fields
Guo, Zeyu and Narayanan, Anand Kumar and Umans, Chris. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), LIPIcs, 58, 47:1–47:14, 2016.
Read the source - A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
Umans, Chris and Wang, Siki. arXiv:2511.10851; listed for ISAAC 2026, 2025.
Read the source - On Hensel factorization, I
Zassenhaus, Hans. Journal of Number Theory, 1(3), 291–311, 1969.
Read the source - Newton polygons of higher order in algebraic number theory
Guàrdia, Jordi and Montes, Jesús and Nart, Enric. Transactions of the American Mathematical Society, 364(1), 361–416, 2012.
Read the source - Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields
Guàrdia, Jordi and Montes, Jesús and Nart, Enric. Journal de théorie des nombres de Bordeaux, 23(3), 667–696, 2011.
Read the source - Local Polynomial Factorisation: Improving the Montes Algorithm
Poteaux, Adrien and Weimann, Martin. Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation (ISSAC ’22), 149–157, 2022.
Read the source - Okutsu invariants and Newton polygons
Guàrdia, Jordi and Montes, Jesús and Nart, Enric. Acta Arithmetica, 145(1), 83–108, 2010.
Read the source - Factoring polynomials with rational coefficients
Lenstra, A. K. and Lenstra, Jr., H. W. and Lovász, L. Mathematische Annalen, 261(4), 515–534, 1982.
Read the source - Factoring polynomials and the knapsack problem
van Hoeij, Mark. Journal of Number Theory, 95(2), 167–189, 2002.
Read the source - Factoring polynomials over global fields
Belabas, Karim and van Hoeij, Mark and Klüners, Jürgen and Steel, Allan. Journal de théorie des nombres de Bordeaux, 21(1), 15–39, 2009.
Read the source - FLINT documentation: polynomial factorization algorithms
The FLINT Team.
Read the source - Probabilistic algorithms in finite fields
Rabin, Michael O. SIAM Journal on Computing, 9(2), 273–280, 1980.
Read the source
Comments
Any comments are welcome. Comments appear after the site owner approves them. Privacy policy.