betaFeedback

WorksMathematics

Deterministic Polynomial Factorization over Prime Fields

Abstract

We give a uniform deterministic polynomial-time algorithm for complete factorization over prime fields. For a prime p in binary and a nonzero polynomial f∈Fp[x]f\in\mathbf F_p[x] given by its dense coefficient list, the algorithm computes the irreducible factors and their multiplicities using a number of bit operations polynomial in (deg⁡f+1)log⁡p(\deg f+1)\log p. The proof uses the uniform Hecke zero-free theorem from the companion paper Primitive roots for every admissible integer base.

Introduction

Let pp be a prime, given in binary, and let f∈Fp[x]f \in\mathbb{F}_p[x] be a nonzero polynomial, given by its dense coefficient list. Write n=deg⁡fn = \deg f and L=⌈log⁡2p⌉L = \lceil\log_2 p\rceil. Complete factorization means computing the leading coefficient cc and distinct monic irreducible polynomials gig_i, with positive integer multiplicities eie_i, such that

f=c∏igiei.f = c\prod_i g_i^{e_i}.

The empty product is permitted when n=0n = 0. The complexity parameter is (n+1)L(n + 1)L, so an algorithm polynomial in pp does not give a polynomial-time algorithm in the prescribed representation.

Finite-field factorization is a basic constructive problem in algebra. It also exposes a persistent distinction between randomized and deterministic computation: a random element of a product of finite fields often separates its components, whereas constructing a separator uniformly can require additional arithmetic information. The present paper isolates one form of that information and gives a deterministic splitting procedure once it is available. To supply it uniformly, we use the zero-free theorem for finite-order Hecke LL-functions in the companion paper [21], Theorem 1.2. We state that input precisely in Theorem 11.1 and prove its auxiliary-prime consequence here. The analytic theorem itself belongs to the companion.

Theorem 1.1. There is a uniform deterministic algorithm that, given a prime pp in binary and a nonzero dense polynomial f∈Fp[x]f \in\mathbb{F}_p[x] of degree nn, outputs its leading coefficient and its distinct monic irreducible factors with their multiplicities in

O(((n+1)⌈log⁡2p⌉)1012)O\left(((n+1)\lceil\log_2 p\rceil)^{10^{12}}\right)

bit operations, with absolute implied constant. A constant polynomial returns an empty factor list. The algorithm uses no randomness, integer-factorization oracle, primitive-root oracle, or GRH assumption.

The exponent is deliberately generous. The point is one fixed polynomial bound for all degrees and prime characteristics. We separate the algebraic construction from its analytic input in the following reduction.

The auxiliary-prime reduction

Put

B=20+(n+1)(L+1).B = 20 + (n+1)(L+1).

For a prime q≤nq \le n, call a rational prime ℓ\ell an auxiliary prime for (p,q)(p,q) if

ℓ∉{2,3,p,q},ℓ≡1(mod12q),p(ℓ−1)/q≠1(modℓ).(1)\ell\notin\{2,3,p,q\}, \qquad\ell\equiv1 \pmod{12q}, \qquad p^{(\ell-1)/q} \ne1 \pmod{\ell}. \tag*{(1)}

Thus pp is not a qqth power modulo ℓ\ell. The congruence modulo 12q12q is convenient for the analytic construction in Section 11; the algebraic construction only requires the corresponding congruence modulo qq.

Theorem 1.2. There is a uniform deterministic algorithm with the following guarantee. Its input is a prime pp and a nonzero dense polynomial f∈Fp[x]f \in\mathbb{F}_p[x]. If p>B200000p > B^{200000} and n≥2n \ge2, its input also includes one auxiliary prime ℓq\ell_q satisfying (1) for each prime q≤nq \le n. It outputs the complete factorization of ff, including multiplicities. Let E=max⁡(2,max⁡qℓq)E = \max(2,\max_q \ell_q), with E=2E = 2 when no auxiliary primes are required. For an absolute constant CC, the algorithm uses O((B+E)C)O((B+E)^C) bit operations. It uses neither randomness nor an integer factorization or primitive-root oracle.

The dependence on EE is on the numerical value of the auxiliary primes, not merely their bit lengths. Consequently Theorem 1.2 becomes a polynomial-time factorization theorem when these primes are bounded by a fixed power of BB. Upward search, trial division, and modular exponentiation then construct them within the same kind of bound. We prove this consequence from the cited zero-free theorem in Section 11. The reduction in Theorem 1.2 does not use that theorem.

History and the role of the construction

Berlekamp’s algorithms put linear algebra at the center of finite-field factorization: Frobenius-fixed elements in the quotient algebra encode its irreducible factors, and polynomial greatest common divisors turn suitable such elements into factors [2, 3]. Randomized algorithms, including Cantor–Zassenhaus [4], obtain expected polynomial running time by finding separating elements with random choices. The difficulty studied here is to make every such choice deterministically, with a bound polynomial in both the degree and the bit length of the characteristic.

Several deterministic results delineate this difficulty. Shoup’s algorithm has polynomial dependence on the degree and a p1/2+o(1)p^{1/2+o(1)} dependence on the characteristic [28]. Under the generalized Riemann hypothesis, Rónyai obtained polynomial bounds when the number of irreducible factors is bounded [25], and Evdokimov obtained a bound (nlog⁡nlog⁡p)O(1)(n^{\log n}\log p)^{O(1)} for general degree [7]. The latter is quasipolynomial in nn. The reduction proved here, combined with the fixed-width zero-free strip that follows immediately from Hecke GRH, already gives a polynomial bound in both parameters under GRH. For Theorem 1.1, the companion supplies that strip without GRH. In particular, the hypotheses and parameters of a deterministic result matter: removing random choices alone does not establish a uniform polynomial bound in (n+1)L(n+1)L.

Geometric methods already have an important place in this history. Schoof’s elliptic-curve method computes a square root of a fixed integer aa modulo a varying prime, when one exists, in time polynomial in log⁡p\log p; the uniform bound in the two parameters is polynomial in ∣a∣|a| and log⁡p\log p, rather than in their binary lengths [27], Section 4. Pila’s computation of Frobenius on abelian varieties yields deterministic construction of roots of unity of fixed odd prime order modulo primes congruent to 1 modulo that order, with a running-time exponent that may depend on the order and on the geometric presentation [22], Theorems A and D. These results motivate careful accounting for the varying curve and prime in the present construction. We must bound the degrees of field extensions, the sizes of divisor representations, and the dimensions of all linear systems by fixed powers of the original input parameters.

For a single prime not dividing the discriminant of an integral lift, Rónyai obtained, under GRH, deterministic bounds involving the degree of that lift’s splitting field [26]. A different kind of uniformity arises when reductions modulo many primes are processed together. Altman’s unconditional algorithm takes a monic irreducible polynomial in Z[x]\mathbb{Z}[x] of coefficient height at most H≥2H \ge2, with splitting-field degree mm, and factors its reductions modulo every prime below XX in total time

π(X)(mlog⁡H)O(1)log⁡5X.\pi(X)(m \log H)^{O(1)} \log^{5} X.

This is an amortized result over primes [1], Theorem 1.1. The parameter mm can be as large as the factorial of the polynomial’s degree. Thus this result does not give the worst-case single-input bound sought here. Altman’s introduction also provides a recent account of the general deterministic problem and its remaining obstacles.

The algebraic techniques used below have substantial precedents. Computation at unknown roots by working in a quotient algebra and splitting it when a zero test distinguishes components is an instance of dynamic evaluation [5, 6]. The digit calculations in primary multiplicative groups are the prime-power part of the Pohlig–Hellman algorithm [23]. Rónyai already proved that a completely split polynomial of even degree can be split in polynomial time when a quadratic nonresidue is supplied [25]; we include an explicit tournament proof suited to our representation. The odd-degree construction uses cyclic curves Yq=F(X)Y^q=F(X). The cyclotomic action on their Jacobians and descriptions of its first torsion layer by ramification divisors are familiar from explicit descent, notably the work of Poonen and Schaefer [24], Sections 4 and 6.

Our effective treatment of divisors also builds on established computational geometry. Ideal representations on superelliptic curves, Riemann–Roch algorithms, and finite-dimensional linear algebra for Jacobian arithmetic appear in [8, 13, 16]. For norm equations, we use the relation between cyclic algebras and norms, and the approach through maximal orders and minimal left ideals developed in explicit matrix-algebra computations [9, 15, 14]. The general function-field algorithm of Ivanyos, Kutas, and Rónyai uses a finite-field polynomial-factorization oracle. Here the cyclic presentation gives explicit local orders, and evaluation of their global sections at a rational point gives a rank-one idempotent by linear algebra. The structural explanation uses the splitting of vector bundles on the projective line [10, 12].

The substantive step of the present reduction is the odd-degree separator, together with a uniform implementation of the divisor-class divisions it requires. A filtration of lifted ramification classes keeps the necessary field extensions of polynomial degree. A lattice of divisors at infinity then forces two ramification points to receive different labels. We prove this mechanism and its algorithms directly; the earlier results just discussed provide their mathematical context. The separate step of finding sufficiently small auxiliary primes is isolated in Section 11, which is the only place the companion’s analytic theorem enters.

Proof strategy

The Berlekamp algebra reduces complete factorization to splitting a monic square-free polynomial FF all of whose roots already belong to Fp\mathbb{F}_p. Write N=deg⁡F≥2N = \deg F \ge2. The unknown roots are represented simultaneously by the finite algebra Fp[T]/(F)\mathbb{F}_p[T]/(F); an operation whose outcomes differ between components immediately produces a factor by a greatest common divisor. We can therefore describe computations at an unspecified root and carry them out without first finding that root.

The auxiliary primes construct the multiplicative information needed in these computations. For each odd prime qq, they give a field Kq=Fp(ζq)K_q = \mathbb{F}_p(\zeta_q) and a generator of the full qq-primary subgroup of Kq∗K_q^*. The entry for q=2q = 2 is a generator of the full 2-primary subgroup of Fp∗\mathbb{F}_p^*. Here the qq-primary subgroup consists of the elements whose orders are powers of qq. These entries permit extraction of promised qqth roots in finite algebras by small-prime discrete logarithms. Their construction proceeds in increasing qq: the only factorization needed to make the entry for qq has degree q−1q - 1.

When NN is even, differences between pairs of roots and the 2-primary entry orient the complete graph on the roots. Opposite differences have opposite orientations. The vertex scores cannot all be equal when NN is even, so they provide a separator. The more substantial construction handles odd NN.

Choose an odd prime q∣Nq \mid N, and write r=vq(N)r = v_q(N). Over an explicitly constructed field kk of degree at most N(q−1)N(q - 1) over Fp\mathbb{F}_p, consider the smooth projective curve with affine equation

C:Yq=F(X).C : Y^q = F(X).

Its ramification points are Pi=(xi,0)P_i = (x_i, 0), where the xix_i are the unknown roots of FF. There are qq rational points at infinity. The automorphism σ(X,Y)=(X,ζqY)\sigma(X,Y) = (X,\zeta_qY) acts on degree-zero divisor classes; write λ=1−σ\lambda= 1 - \sigma. Degree-zero divisors supported at infinity form a lattice on which λ\lambda is injective. In contrast, λ\lambda is surjective on the geometric Jacobian.

This difference is the source of the splitting argument. We lift each class [Pi−∞0][P_i - \infty_0] repeatedly through λ\lambda, keeping track of an infinity divisor at every stage. A filtration argument shows that all the classes required for these lifts are rational over the field kk; the extension degree stays polynomial even though the number of possible classes is large. Summing the lifted classes and applying explicit label tests forces a distinction between ramification points. If every test gave one common label, a fixed nonzero infinity divisor would become divisible by one more power of λ\lambda than its lattice valuation allows.

The geometric existence argument is accompanied by a constructive division algorithm. A promised λ\lambda-division reduces to a norm equation in k(C)/k(X)k(C)/k(X). We solve that equation by constructing maximal orders in a split cyclic algebra and computing their global sections on the projective line. A rank-one idempotent in this algebra yields the norm solution. All computations use polynomial and matrix arithmetic; Riemann–Roch reduction controls divisor sizes, and arithmetic circuits store principal functions arising from large infinity multiplicities. Figure 1 records the roles of these ingredients.

Proof structure showing auxiliary-prime existence, finite fields and primary generators, norm equations and divisor-class division, rational lifts and the infinity-lattice obstruction, a factor of a totally split polynomial, and complete factorization with multiplicities

Figure 1. The proof separates auxiliary-prime existence from the algebraic reduction. The dashed implication uses the cited analytic theorem; the remaining constructions are proved in the paper. The two middle branches are the effective and geometric parts of the odd-degree splitter.

The technical results are uniform in the degree of the curve and the prime qq. This uniformity is essential: a running-time exponent depending on the genus would not suffice for Theorem 1.2. We give the finite-field tools first, then the auxiliary table, the geometry, and the effective divisor and norm calculations. The splitter and the factorization driver assemble these ingredients. The final two sections prove the bit bounds and the analytic implication.

Finite-field computations without known roots

The splitting procedures will manipulate all roots of a polynomial at once. Two elementary tools make this possible. First, a computation over a field can be executed in a product of fields until a zero test distinguishes two components. Second, a supplied generator of a primary multiplicative subgroup permits logarithms and root extraction by short digit calculations. We develop both tools explicitly, and then use them to split every totally split polynomial of even degree.

Finite fields are represented by a basis over their prime field and a multiplication table, or by an equivalent tower of polynomial quotients. Field arithmetic, binary powering, polynomial Euclidean algorithms, and linear algebra are therefore deterministic procedures with polynomial bit complexity in the representation lengths. All basis choices and pivot choices below use a fixed ordering. For a prime qq and a positive integer mm, write vq(m)v_q(m) for its qq-adic valuation. If kk has cardinality QQ and q∣Q−1q \mid Q-1, its full qq-primary subgroup is the unique subgroup of k∗k^* of order qvq(Q−1)q^{v_q(Q-1)}.

Simultaneous execution and zero tests

Let kk be an explicitly represented finite extension of Fp\mathbb{F}_p, and let F∈Fp[T]F \in\mathbb{F}_p[T] be monic, square-free, and totally split, of degree NN. Write its roots as x1,…,xNx_1,\ldots,x_N for the proof; the algorithm does not know these roots. The algebra

A=k[T]/(F)≃∏i=1Nk,a(T)↦(a(x1),…,a(xN))(2)A = k[T]/(F) \simeq\prod_{i=1}^{N} k,\qquad a(T) \mapsto\left(a(x_1),\ldots,a(x_N)\right) \tag*{(2)}

lets us carry out arithmetic on all components simultaneously.

Lemma 2.1 (Simultaneous execution). Suppose a deterministic field procedure uses arithmetic, zero tests, and integer control, and its scalar input at component ii is obtained by specializing given elements of AA at T=xiT=x_i. Assume the procedure is defined for each specialized input. One can either execute the procedure on all components with a common sequence of decisions, or return a nontrivial proper monic divisor of FF in Fp[T]\mathbb{F}_p[T]. The extra cost of each scalar operation or zero test is polynomial in NN, [k:Fp][k:\mathbb{F}_p], and log⁡p\log p.

Proof. For a zero test on a∈Aa \in A, compute d=gcd⁡(F,a)d=\gcd(F,a) over kk using its representative of degree less than NN. If d=1d=1, every component is nonzero; if d=Fd=F, every component is zero. In the remaining case, dd is a proper factor and the procedure stops. Although computed over kk, its monic form belongs to Fp[T]\mathbb{F}_p[T]: it is the product of T−xiT-x_i over the components where a(xi)=0a(x_i)=0.

Addition and multiplication take place in AA. A nonzero scalar is inverted only after the zero test has shown it nonzero in every component; the extended Euclidean algorithm then gives its inverse modulo FF. Thus, until a split occurs, every field instruction and decision is valid in every component. Polynomial degree tests and choices of pivots reduce to successive zero tests on coefficients, so the same argument applies inside polynomial arithmetic and linear algebra. The usual dense implementations give the cost bound.

This is the dynamic-evaluation principle [5]; we call its use here simultaneous execution. In particular, a divergent pivot or a divergent polynomial degree is useful information: it already supplies the required factor. The convention also applies to nested procedures whose coefficient field is being simulated by AA.

Logarithms in primary subgroups

Let qq be a prime, and suppose uu generates a cyclic group of order qsq^s. For a∈⟨u⟩a \in\langle u\rangle, its logarithm ℓ∈[0,qs)\ell\in[0,q^s) can be recovered one base-qq digit at a time, as in the prime-power logarithm algorithm of Pohlig and Hellman [23]. If ℓj≡ℓ(modqj)\ell_j \equiv\ell\pmod{q^j} is already known, the next digit is the unique c∈{0,…,q−1}c \in\{0,\ldots,q-1\} satisfying

(au−ℓj)qs−j−1=(uqs−1)c,0≤j<s.(3)\left(au^{-\ell_j}\right)^{q^{s-j-1}} = \left(u^{q^{s-1}}\right)^c,\qquad0 \leq j < s. \tag*{(3)}

Set ℓj+1=ℓj+cqj\ell_{j+1}=\ell_j+cq^j and begin with ℓ0=0\ell_0=0. Indeed, if ℓ−ℓj=qj(c+qv)\ell-\ell_j=q^j(c+qv), raising to qs−j−1q^{s-j-1} removes the term qvqv and leaves exactly (3). This uses qq equality tests per digit, rather than an enumeration of qsq^s group elements.

The same calculation works in a product of fields when uu has order qsq^s in every component. When the product is presented as k[X]/Hk[X]/H with HH square-free, gcds with HH partition the components at each digit according to the equality in (3); retain each nonempty piece and its current digit string. There are at most deg⁡H\deg H pieces at every level. Keep each final integer logarithm together with its polynomial modulus. Algebra elements subsequently computed from these logarithms can be recombined by polynomial Chinese remaindering. Alternatively, when zero components are represented by idempotent masks, perform the same partitions using those masks. These two implementations will be used below.

Root extraction in a finite reduced algebra

We next give the root procedure used in the norm equations later in the paper. Its input already includes a generator over the constant field, but it does not include generators in extension fields, nor a factorization of the modulus.

References

  1. [1]D. Altman, Deterministic polynomial factorisation modulo many primes, arXiv:2509.12705, 2025.arxiv.org/abs/2509.12705
  2. [2]E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), no. 8, 1853–1859.DOI
  3. [3]E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), no. 111, 713–735.
  4. [4]D. G. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587–592.
  5. [5]J. Della Dora, C. Dicrescenzo, and D. Duval, About a new method for computing in algebraic number fields, in EUROCAL ’85, Vol. 2: Research Contributions, B. F. Caviness (ed.), Lecture Notes in Computer Science 204, Springer, Berlin, 1985, 289–290.DOI
  6. [6]D. Duval, Algebraic numbers: an example of dynamic evaluation, J. Symbolic Comput. 18 (1994), no. 5, 429–445.DOI
  7. [7]S. Evdokimov, Factorization of polynomials over finite fields in subexponential time under GRH, in Algorithmic Number Theory, L. M. Adleman and M.-D. Huang (eds.), Lecture Notes in Computer Science 877, Springer, Berlin, 1994, 209–219.DOI
  8. [8]S. D. Galbraith, S. M. Paulus, and N. P. Smart, Arithmetic on superelliptic curves, Math. Comp. 71 (2002), no. 237, 393–405.
  9. [9]P. Gille and T. Szamuely, Central Simple Algebras and Galois Cohomology, Cambridge Studies in Advanced Mathematics 101, Cambridge University Press, Cambridge, 2006.
  10. [10]A. Grothendieck, Sur la classification des fibrés holomorphes sur la sphère de Riemann, Amer. J. Math. 79 (1957), no. 1, 121–138.DOI
  11. [11]E. Hasanალიზade, Q. Shen, and P.-J. Wong, Counting zeros of Dedekind zeta functions, Math. Comp. 91 (2022), no. 333, 277–293.
  12. [12]M. Hazewinkel and C. F. Martin, A short elementary proof of Grothendieck’s theorem on algebraic vectorbundles over the projective line, J. Pure Appl. Algebra 25 (1982), no. 2, 207–211.DOI
  13. [13]F. Hess, Computing Riemann–Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425–445.
  14. [14]G. Ivanyos, P. Kutas, and L. Rónyai, Computing explicit isomorphisms with full matrix algebras over F_q(x), Found. Comput. Math. 18 (2018), no. 2, 381–397.
  15. [15]G. Ivanyos, L. Rónyai, and J. Schicho, Splitting full matrix algebras over algebraic number fields, J. Algebra 354 (2012), 211–223.arxiv.org/abs/1106.6191
  16. [16]K. Khuri-Makdisi, Linear algebra algorithms for divisors on an algebraic curve, Math. Comp. 73 (2004), no. 245, 333–357.
  17. [17]R. Lidl and H. Niederreiter, Finite Fields, second edition, Encyclopedia of Mathematics and its Applications 20, Cambridge University Press, Cambridge, 1997.DOI
  18. [18]J. S. Milne, Abelian varieties, in Arithmetic Geometry, G. Cornell and J. H. Silverman (eds.), Springer, New York, 1986, 103–150.DOI
  19. [19]J. S. Milne, Jacobian varieties, in Arithmetic Geometry, G. Cornell and J. H. Silverman (eds.), Springer, New York, 1986, 167–212.DOI
  20. [20]J. Neukirch, Algebraic Number Theory, translated by N. Schappacher, Grundlehren der mathematischen Wissenschaften 322, Springer, Berlin, 1999.DOI
  21. [21]OpenAI, Primitive roots for every admissible integer base, OpenAI Math Release preprint OAI:Primitive-roots-for-every-admissible-integer-base-October-4-2026, 2026.
  22. [22]J. Pila, Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comp. 55 (1990), no. 192, 745–763.
  23. [23]S. C. Pohlig and M. E. Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. Inform. Theory 24 (1978), no. 1, 106–110.
  24. [24]B. Poonen and E. F. Schaefer, Explicit descent for Jacobians of cyclic covers of the projective line, J. Reine Angew. Math. 488 (1997), 141–188.
  25. [25]L. Rónyai, Factoring polynomials over finite fields, J. Algorithms 9 (1988), no. 3, 391–400.
  26. [26]L. Rónyai, Galois groups and factoring polynomials over finite fields, SIAM J. Discrete Math. 5 (1992), no. 3, 345–365.
  27. [27]R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44 (1985), no. 170, 483–494.
  28. [28]V. Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), no. 5, 261–267.DOI
  29. [29]The Stacks Project Authors, The Stacks Project, 2026, https://stacks.math.columbia.edu.

Paper details

vlnc:W_6w7kf29p
Version
v1 · latest
Published
License
LicenseRef-OpenAI-public
Usage

views · 33

downloads · 3

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

unreleased internal OpenAI model

View statement
Looking for related papers…
Contents