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 Fq\mathbb F_q. A squarefree decomposition separates repeated factors, using gcds with the derivative. If the derivative vanishes, the polynomial is a pp-th power over the finite field and one first takes its pp-th root.

For a squarefree polynomial, gcd⁡(f,xqd−x)\gcd(f,x^{q^d}-x) selects its irreducible factors whose degrees divide dd. 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

Berlekamp's algorithm

Proposition

If ff is squarefree with rr distinct irreducible factors, then

dim⁡Fq{h∈Fq[x]/(f):hq=h}=r.\dim_{\mathbb F_q}\{h\in\mathbb F_q[x]/(f):h^q=h\}=r.

Indeed, the Chinese remainder theorem identifies the quotient with a product ∏i=1rFqdi\prod_{i=1}^r\mathbb F_{q^{d_i}}. The fixed elements of Frobenius on each component are exactly Fq\mathbb F_q. Finding the fixed subspace is linear algebra. A fixed element assumes constant values on the components; gcds gcd⁡(f,h−c)\gcd(f,h-c), for c∈Fqc\in\mathbb F_q, separate components with different values.

Example

Over F2\mathbb F_2, take f=x4+xf=x^4+x. Since f′=1f'=1, it is squarefree. In the quotient, x4=xx^4=x, and solving h2=hh^2=h gives the basis 1,x2+x,x31,x^2+x,x^3. Thus there are three irreducible factors. The gcds from h=x3h=x^3 first split off xx; those from h=x2+xh=x^2+x split the remaining cubic. The result is

x4+x=x(x+1)(x2+x+1).x^4+x=x(x+1)(x^2+x+1).

The quadratic has no root in F2\mathbb F_2, which completes the factorization.

References 1

Modular composition

The operation modular composition takes a,g,f∈K[x]a,g,f\in K[x], with ff monic of degree nn and deg⁡a,deg⁡g<n\deg a,\deg g<n, and computes g(a(x)) mod f(x)g(a(x))\bmod f(x). It avoids storing a composition whose unreduced degree can be nearly n2n^2.

Frobenius as modular composition

In A=Fq[x]/(f)A=\mathbb F_q[x]/(f), put a=xq mod fa=x^q\bmod f. For every h∈Fq[x]h\in\mathbb F_q[x],

h(x)q≡h(a(x))(modf).h(x)^q\equiv h(a(x))\pmod f.

The coefficients are fixed by the qq-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 F2\mathbb F_2, take f=x3+x+1f=x^3+x+1. Since x3=x+1x^3=x+1 in the quotient, applying Frobenius to h=x2+xh=x^2+x gives

h2=x4+x2=(x2+x)+x2=x.h^2=x^4+x^2=(x^2+x)+x^2=x.

Equivalently, compose hh with a=x2a=x^2 and reduce modulo ff.

Brent–Kung's baby-step/giant-step method groups powers of aa into blocks and combines them by matrix multiplication. Later methods encode small algebraic relations between xx and aa in polynomial matrices, or reduce the task to multivariate evaluation. Both approaches avoid forming the full intermediate composition.

References 3

Complexity bounds

A field-operation count charges unit cost for arithmetic in KK. A bit-operation count includes the representation and size of coefficients. Over Fq\mathbb F_q, these are not interchangeable uniformly in qq. Modular composition is one step of a factorization algorithm.

SourcePrecise scopeContribution
Kedlaya–Umans (2011)Modular composition over Fq\mathbb F_q; bit complexityFor each fixed ε>0\varepsilon>0, n1+εlog⁡1+o(1)qn^{1+\varepsilon}\log^{1+o(1)}q 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 complexityA Las Vegas method with expected O(n1.43)O(n^{1.43}) field operations. Small finite fields are handled through a suitably enlarged extension; a failed randomized trial is detected.
Neiger–Salvy–Schost–Villard (2026)Fixed ff, generic inner polynomial aa; arithmetic complexityTwo relation matrices give O~(n(ω+3)/4)\widetilde O(n^{(\omega+3)/4}) field operations. Here ω\omega is a feasible square-matrix multiplication exponent. The genericity requirement is essential.
van der Hoeven–Lecerf (2026)Modular composition over Z/rZ\mathbb Z/r\mathbb Z; bit complexityA 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

O ⁣(n3/2+o(1)log⁡1+o(1)q+n1+o(1)log⁡2+o(1)q).O\!\left(n^{3/2+o(1)}\log^{1+o(1)}q+n^{1+o(1)}\log^{2+o(1)}q\right).

A faster modular-composition subroutine does not by itself turn this exponent into 11. Guo–Narayanan–Umans (2016) organize related algebraic problems through reductions that would transfer an improvement below the factorization exponent 3/23/2. 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 3/23/2. The paper was listed for ISAAC in December 2026 when checked on 12 November; the reference below identifies the available preprint.

References 6

Hensel lifting and recombination

Let f∈Z[x]f\in\mathbb Z[x] be monic and squarefree. Choose a prime where its reduction remains squarefree, factor there, and lift the pairwise coprime factors modulo p,p2,p4,…p,p^2,p^4,\ldots 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 Z[x]\mathbb Z[x]. 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 pp alone gives no rational factor, since the local factors need not descend separately. An irreducible good reduction, however, proves rational irreducibility immediately.

References 2

Local factorization and higher Newton polygons

Local factorization over Qp\mathbb Q_p remains possible when every factor of fˉ\bar f 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 pp-adic precision together with exact structural data; its coefficients need not be rational. Recovering rational factors still requires global recombination and certification.

References 3

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

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

Factorization certificates

The identity f=c∏igieif=c\prod_i g_i^{e_i} proves a factorization, but not its completeness. Completeness additionally requires proof that each gig_i 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

Questions

SettledAlgorithms and certificates

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.

References 1
Discuss this question →
Research directionAlgorithms and certificates

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-nn modulus ff, Theorem 1.3 supplies a nonempty Zariski-open set of coefficient vectors for aa 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
Discuss this question →

Related topics

References

  1. 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
  2. Modern Computer Algebra

    von zur Gathen, Joachim and Gerhard, Jürgen. Edition 3. Cambridge University Press, 2013.

    Read the source
  3. Factoring polynomials over finite fields

    Berlekamp, Elwyn R. Bell System Technical Journal, 46(8), 1853–1859, 1967.

    Read the source
  4. 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
  5. Fast polynomial factorization and modular composition

    Kedlaya, Kiran S. and Umans, Christopher. SIAM Journal on Computing, 40(6), 1767–1802, 2011.

    Read the source
  6. 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
  7. 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
  8. Fast modular composition using spiroids

    van der Hoeven, Joris and Lecerf, Grégoire. Journal of Complexity, 96, 102073, 2026.

    Read the source
  9. 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
  10. 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
  11. On Hensel factorization, I

    Zassenhaus, Hans. Journal of Number Theory, 1(3), 291–311, 1969.

    Read the source
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. Factoring polynomials and the knapsack problem

    van Hoeij, Mark. Journal of Number Theory, 95(2), 167–189, 2002.

    Read the source
  18. 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
  19. FLINT documentation: polynomial factorization algorithms

    The FLINT Team.

    Read the source
  20. Probabilistic algorithms in finite fields

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

    Read the source