Deterministic polynomial-time factorization of polynomials over prime fields

Berlekamp's algorithms (1967, 1970) reduce factoring $f\in\mathbb F_p[x]$ to finding separating elements of a quotient algebra, and randomized algorithms such as Cantor-Zassenhaus factor in expected time polynomial in $\deg f$ and $\log p$ . Deterministically, Shoup's bound depends on $p^{1/2+o(1)}$ ; under GRH, Ronyai handled a bounded number of factors and Evdokimov obtained $(n^{\log n}\log p)^{O(1)}$ , still quasipolynomial. Altman (2025) surveys the remaining obstacles. Is there a deterministic algorithm that completely factors every polynomial of degree $n$ over $\mathbb F_p$ , with $p$ given in binary, in time polynomial in $n$ and $\log p$ , without GRH?

Result: Proved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Algorithmic number theory, derandomization
Posed by: Long-standing problem in the line of Berlekamp (1967, 1970); the manuscript cites Altman, arXiv:2509.12705 (2025), for a recent account and names no original poser
Year posed: —
Years open: —
Solved: 2026-10-04
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Unreviewed
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 55 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Theorem 1.1: a uniform deterministic algorithm computes the complete factorization (irreducible factors with multiplicities) of any nonzero dense $f\in\mathbb F_p[x]$ in $O(((n+1)\lceil\log_2 p\rceil)^{10^{12}})$ bit operations, with no randomness, oracle or GRH. Theorem 1.2 (proved here, unconditional) does this given small auxiliary primes $\ell\equiv1\pmod{12q}$ with $p$ not a $q$ th power mod $\ell$ ; the odd-degree splitter uses Jacobians of cyclic curves $Y^q=F(X)$ and norm equations in cyclic algebras. Small auxiliary primes are deduced from a uniform zero-free strip $\mathrm{Re}\,s>1-10^{-6}$ for all finite-order Hecke L-functions over cyclotomic fields containing $\mu_{12}$ , imported from the companion on primitive roots and not proved here. The exponent is not practical.

What the AI did

Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems. The release README says the vast majority of results used one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result; this result is not among the README's stated exceptions (the Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscript is authored as OpenAI with no human author named. The README also cautions that unformalized results could have issues.

Verification

No independent mathematician has checked this yet. Checked here: the abstract, introduction, Theorems 1.1 and 1.2 and the statement of the imported analytic input in Section 10, read against the problem as the manuscript frames it. The algebraic construction was not refereed. No Lean main result. The theorem is conditional on another unchecked manuscript in the same release: the uniform Hecke zero-free strip is Theorem 1.2 of Primitive roots for every admissible integer base, which the catalog lists as an unreviewed partial result. That strip is itself an extraordinary claim, far beyond anything known unconditionally; if it fails, what remains is the unconditional reduction (Theorem 1.2) and, as the paper notes, a polynomial bound under GRH.

Deterministic polynomial-time factorization of polynomials over prime fields

What was actually shown

What the AI did

Verification

Sources

Discussion