Factoring polynomials over prime fields without random choices

← All digests

Family 142 · Theoretical computer science
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

Factoring a polynomial means breaking it into pieces that cannot be factored further over the chosen coefficient field. Over the real numbers, $x^2+1$ is irreducible; over the complex numbers it becomes $(x-i)(x+i)$. Over the field of integers modulo five, it instead becomes $(x-2)(x+2)$, since $-4=1$ modulo five. The field is part of the problem.

For a prime $p$, the field $\mathbb F_p$ consists of the residues modulo $p$, with addition and multiplication performed modulo $p$. Given a polynomial over this field, can we compute its complete factorization efficiently without making random choices?

Randomized polynomial-time methods have long made finite-field factorization a basic tool of computer algebra. The difficult deterministic target asks for one algorithm whose bit cost is polynomial in both the degree and the number of bits specifying $p$. Enumerating all $p$ field elements is affordable for a tiny field but exponential in the bit length of a large prime.

Family 142 contains one manuscript, M1, claiming this deterministic bound over prime fields. Its result combines an algebraic splitting procedure with an analytic number-theory theorem supplied by a separate companion manuscript. Both parts matter to the claim.

2. Background and essential definitions

What the algorithm must output

Let $f\in\mathbb F_p[x]$ be nonzero, of degree $n$. Its dense representation lists all $n+1$ coefficients, including zeros. Complete factorization means producing

$$f=c\prod_{i=1}^{t}g_i^{e_i},$$

where $c$ is the nonzero leading coefficient, the $g_i$ are distinct monic irreducible polynomials, and the $e_i$ are positive integer multiplicities. Monic means leading coefficient one; irreducible means having no factorization into two positive-degree polynomials over $\mathbb F_p$. A nonzero constant has an empty factor list.

With $L=\lceil\log_2p\rceil$, the natural size parameter is $(n+1)L$. A uniform polynomial-time algorithm has a single fixed polynomial bound in this parameter, with no input-dependent advice or degree-dependent exponent.

A polynomial is square-free when no irreducible factor repeats. Its derivative and its greatest common divisor with that derivative reveal repeated factors, with additional care when the derivative vanishes in characteristic $p$. A polynomial is totally split when all its irreducible factors are linear. Splitting a square-free, totally split polynomial into two nonconstant factors is a central subproblem, even though its roots already belong to the base field.

Computing at roots we have not found

If $F$ is square-free and totally split with unknown roots $a_1,\ldots,a_N$, then

$$\mathbb F_p[T]/(F)\cong\prod_{i=1}^{N}\mathbb F_p.$$

On the left, calculations use polynomials modulo $F$. On the right, the same calculation evaluates at every root simultaneously. We need not know the roots to use the left-hand representation.

An element that is zero at some roots and nonzero at others separates the components: taking its polynomial greatest common divisor with $F$ extracts a proper factor. Random choices often create such a distinction. The deterministic challenge is to force one constructively.

3. Development history and previous partial results

Berlekamp’s algorithms of 1967 and 1970 brought linear algebra into finite-field factorization. In a quotient algebra, the elements fixed by the Frobenius map $a\mapsto a^p$ contain information about the irreducible components. Suitable fixed elements can be converted into factors using greatest common divisors.

Cantor and Zassenhaus’s 1981 algorithm is a landmark randomized approach. Randomness makes it comparatively easy to find elements whose behavior differs across components. The remaining question is not whether factorization is computationally useful, but whether those choices can always be replaced by a deterministic procedure with the desired worst-case bound.

M1’s historical discussion distinguishes several partial answers. Shoup obtained deterministic bounds polynomial in degree but with a $p^{1/2+o(1)}$ dependence on the characteristic. This is not polynomial in $\log p$. Under the generalized Riemann hypothesis, Rónyai obtained polynomial bounds for a bounded number of irreducible factors, and Evdokimov obtained a general bound of the form $(n^{\log n}\log p)^{O(1)}$, which remains quasipolynomial in degree. Their original papers are identified in M1’s references 28, 25, and 7, respectively.

Geometric methods also supplied restricted deterministic constructions. Schoof used elliptic curves to compute square roots of a fixed integer modulo varying primes. The dependence on the integer itself is not polynomial in its binary length, so the fixed-input restriction matters. Pila’s work on Frobenius maps of abelian varieties similarly motivates geometric constructions while leaving questions of uniformity when geometric parameters vary.

More recently, Altman’s factorization modulo many primes gives an unconditional amortized result for reductions of one integer polynomial. Processing many primes together, with dependence on the degree of a splitting field, is different from a polynomial worst-case bound for one arbitrary input over $\mathbb F_p$.

Against this background, M1 claims a uniform algebraic separator, including the harder odd-degree case, together with a way to supply the arithmetic information it needs. Its unconditional headline invokes the companion’s analytic theorem; the algebraic reduction is stated separately.

4. What the new manuscripts claim

Theorem 1.1 of M1 states that one deterministic algorithm outputs the complete factorization, including multiplicities, in

$$O\!\left(\bigl((n+1)\lceil\log_2p\rceil\bigr)^{10^{12}}\right)$$

bit operations, with an absolute implied constant. The exponent is deliberately generous. The substantive assertion is one fixed polynomial for all degrees and prime characteristics. The algorithm uses no randomness, integer-factorization oracle, primitive-root oracle, or GRH assumption.

The separate arithmetic input

Set $B=20+(n+1)(L+1)$. For each prime $q\leq n$, the construction may need an auxiliary rational prime $\ell$ satisfying

$$\ell\notin\{2,3,p,q\},\qquad \ell\equiv1\pmod{12q},\qquad p^{(\ell-1)/q}\not\equiv1\pmod\ell.$$

The last condition says that $p$ is not a $q$-th power modulo $\ell$. Theorem 1.2 gives a deterministic factorization reduction with cost polynomial in $B+E$, where $E$ is the largest supplied auxiliary prime, or two if none is needed. Auxiliary primes are required only in the large-characteristic branch $p>B^{200000}$, for degree at least two.

Dependence on $E$ means dependence on its numerical value, not just its bit length. The manuscript therefore needs polynomially small auxiliary primes. Section 11 states the following input from Primitive roots for every admissible integer base: for cyclotomic number fields containing the twelfth roots of unity, the specified finite-order Hecke L-functions have no zeros in

$$\operatorname{Re}s>1-10^{-6}.$$

The principal character is included, with its pole at one permitted; there is no conductor or height restriction. These L-functions are analytic objects encoding arithmetic of number fields. The role of the statement here is to guarantee a sufficiently uniform supply of small auxiliary primes. M1 derives a bound $\ell\leq c_0B^{20000000}$, for an absolute constant $c_0$, allowing deterministic search within polynomial time.

Thus the full factorization claim uses a theorem from the companion, whose proof is not part of M1. GRH would also supply a sufficient strip; M1 invokes the companion to state the result without assuming GRH.

5. Why the advance matters

Importance: 5/5, provisional. Deterministic finite-field factorization is a central question in algorithmic algebra and in understanding the role of randomness. A uniform polynomial bound in degree and characteristic bit length addresses the longstanding general prime-field target, rather than a restriction to small characteristic, bounded factor count, or average performance over primes.

The algebraic reduction also has significance of its own: it identifies concrete arithmetic data sufficient to drive deterministic splitting, then connects those data to analytic number theory. This separates two sources of difficulty that can otherwise be hidden in an oracle or an unspecified search.

The enormous displayed exponent makes clear that the claim is foundational. It does not establish a competitive implementation or suggest replacing existing computer-algebra routines on practical grounds.

6. The main idea

Reduce factorization to forced separation

Berlekamp’s fixed algebra reduces the general square-free problem to a totally split polynomial. Dynamic evaluation then performs calculations at all unknown roots simultaneously. Whenever a zero test distinguishes components, a greatest common divisor already supplies a factor; otherwise the computation continues uniformly across the components.

The auxiliary primes provide generators for certain primary multiplicative subgroups: elements whose orders are powers of a chosen prime $q$. These generators support extraction of promised $q$-th roots. Their construction proceeds in increasing $q$, needing factorization only in smaller degree, so the recursive organization avoids assuming the full factorization algorithm as an unexplained subroutine.

When the number of roots is even, the manuscript uses pairwise root differences to orient the complete graph on the roots. An orientation chooses one direction for each edge. The resulting vertex scores cannot all be equal for an even number of vertices, because their common score would have to be $(N-1)/2$, a noninteger. That difference provides a separator.

Use a curve when the number of roots is odd

For odd degree $N$, choose an odd prime divisor $q$ of $N$ and consider the curve

$$Y^q=F(X)$$

over a controlled finite extension of $\mathbb F_p$. Each unknown root $a_i$ determines a special point $(a_i,0)$ on the curve. The construction uses a symmetry $\sigma$ multiplying $Y$ by a $q$-th root of unity.

A divisor is a formal integer combination of points. Degree-zero divisors have total coefficient zero; identifying divisors that differ by the zeros and poles of a rational function gives divisor classes. These classes form the curve’s Jacobian group. This language lets the algorithm compare root points through global geometry rather than their unavailable numerical coordinates.

The operation $\lambda=1-\sigma$ behaves differently on divisor classes and on the lattice of divisors supported at infinity. The manuscript repeatedly lifts classes through $\lambda$, recording accompanying infinity data. If every root kept receiving the same label, a fixed nonzero infinity divisor would have to be divisible too many times in that lattice. The contradiction forces different labels for at least two roots, which dynamic evaluation converts into a factor.

Make the geometric steps computational

Existence of a dividing class is not yet an algorithm. M1 implements the required divisions through norm equations, which ask for an element with a specified multiplicative norm in a field extension. It describes these equations using cyclic algebras and solves the promised cases through polynomial and matrix calculations, including finite linear systems.

The running-time accounting controls extension degrees, divisor representations, and linear-system dimensions by fixed powers of the original parameters. Large multiplicities are stored compactly, and polynomial greatest common divisors drive the final recursion. Derivatives and characteristic-$p$ power extraction recover multiplicities. This uniform accounting is essential: an exponent depending on the curve’s complexity would not prove the headline bound.

7. Scope, limitations, and open questions

The stated input is a prime in binary and a nonzero univariate polynomial in dense form. Zero polynomials, sparse encodings with exponentially large degree, and arbitrary finite extension-field representations are not the input specification of Theorem 1.1. The construction uses extension fields internally, but that does not by itself state every possible extension-field version of the theorem.

Polynomial factorization over a prime field is also different from integer factorization. The absence of an integer-factorization oracle is part of the algorithmic claim, not a claimed polynomial-time algorithm for factoring integers.

The dependency on the companion’s uniform zero-free theorem is substantive. The algebraic reduction can be read separately, while the unconditional final bound uses both contributions as stated. Improving the vast exponent, simplifying the geometric separator, and obtaining practical deterministic implementations are distinct questions beyond this result.

8. Sources and further reading

M1’s Theorems 1.1 and 1.2 separate complete factorization from the auxiliary-prime reduction. Its introduction explains the history and geometric strategy; Sections 8–10 assemble the splitter, recursive driver, and bit bounds. Section 11 states the companion input and its small-prime consequence.

The historical papers linked above give the classical algebraic and randomized background. For further geometry, M1 cites Poonen–Schaefer on explicit descent for cyclic covers and Khuri-Makdisi on linear algebra for divisors. Understanding their full machinery is unnecessary for following the division-of-labor description here.

Source manuscripts

• M1. OpenAI, Deterministic Polynomial Factorization over Prime Fields (October 4, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.