Deterministic polynomial factorization over prime fields

Deterministic polynomial factorization over prime fields asks for an algorithm without random choices that computes the complete factorization of a polynomial over the finite field F_p in time polynomial in its degree and in the bit length of p. A manuscript dated 4 October 2026 in OpenAI's public mathematics collection (github.com/openai/math) claims such an algorithm without assuming the generalized Riemann hypothesis, using an analytic input from a companion manuscript. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.

Background

As recounted in the introduction of the manuscript:
- Berlekamp's algorithms reduce factorization over finite fields to linear algebra, and randomized algorithms such as that of Cantor and Zassenhaus run in expected polynomial time. The difficulty is to make every choice deterministically, with a bound polynomial in both the degree and the bit length of the characteristic.
- Shoup's deterministic algorithm is polynomial in the degree but depends on the characteristic roughly like its square root. Under the generalized Riemann hypothesis, Rónyai obtained polynomial bounds when the number of irreducible factors is bounded, and Evdokimov obtained a bound that is quasipolynomial in the degree for general degree. Altman's unconditional algorithm factors the reductions of one integer polynomial modulo all primes below a bound, with a cost that is small on average over the primes.

The original result

Deterministic factorization (4 October 2026). Theorem 1.1 of the manuscript states that a uniform deterministic algorithm outputs the leading coefficient and the distinct monic irreducible factors, with their multiplicities, of a nonzero dense polynomial of degree n over F_p. Its number of bit operations is at most an absolute constant times ((n + 1)L)^10¹², where L is the bit length of p. The algorithm uses no randomness, no integer-factorization or primitive-root oracle and no assumption of the generalized Riemann hypothesis. The manuscript calls the exponent deliberately generous.
- Reduction, as described: Theorem 1.2 gives a deterministic algorithm whose cost is polynomial in the input size and in the numerical size of auxiliary primes ℓ_q, one for each prime q at most n, with ℓ_q congruent to 1 modulo 12q and p not a q-th power modulo ℓ_q. Section 10 obtains such primes of polynomial size from a zero-free strip. It also notes that the generalized Riemann hypothesis for Hecke L-functions gives the same strip, so that the reduction alone yields deterministic polynomial-time factorization under that hypothesis.
- Method, as described: Berlekamp's algebra reduces the problem to splitting a squarefree polynomial F of degree N whose roots all lie in F_p. Even N is handled by a tournament on the differences of roots, using a generator of the 2-primary part of the multiplicative group. For odd N, the manuscript uses the cyclic curve Y^q = F(X) for an odd prime q dividing N. Classes of ramification points are lifted repeatedly through 1 − σ, where σ multiplies Y by a q-th root of unity, and a lattice of divisors at infinity forces two ramification points to receive different labels. The required divisions are reduced to norm equations, which are solved with maximal orders in a split cyclic algebra.
Analytic input. Section 10 states its only analytic input as Theorem 1.2 of the companion manuscript on primitive roots (see Primitive roots for every admissible integer base). For every cyclotomic field containing the twelfth roots of unity and every finite-order Hecke character of that field, the Hecke L-function has no zero with real part greater than 1 − 10⁻⁶; the principal character is included, with its pole at 1.
Sources. Commit 1581d4c of the openai/math repository, folder Deterministic polynomial factorization over prime fields.
Formalization. The collection has no Lean scope note in lean/docs/ for this family.
- For the analytic input, the README of Yao Xu's Lean formalization of the primitive-root theorem, cadamcat/artin-primitive-roots-lean4 (commit 0c827db), lists the theorem ArtinPrimitiveRoots.HeckeBoundary.thm_hecke_zero_free as one component. As described there, for the cyclotomic field of n-th roots of unity with 12 dividing n and every character of a ray class group of that field, the Hecke L-function continues meromorphically to the half-plane of real part greater than 1 − 10⁻⁶ and has no zeros there, with a width that does not depend on the field or the character. The README states that the proofs are verified by the Lean 4 kernel.

Public follow-up work

Date	Work	Relation	Public claim	Public status (checked 17 October 2026)
2026-10-08	teal-sea, research notes in zeta-lab (GitHub)	Research proposal	Proposes, as a first test, splitting one totally split cubic or quintic over a small prime by the manuscript's odd-degree mechanism, without a factoring oracle. A second note in the same repository defers this route until the full odd-degree dependency chain is available.	Repository notes; no implementation is reported.
2026-10-08	raullenchai/ai-math-kills-crypto (GitHub)	Remark	A survey of the cryptographic consequences of selected OpenAI results. It states that this result factors polynomials over a known prime field and does not factor RSA moduli, and that it removes randomness without a proven speed advantage, so that no attack on deployed cryptography follows.	GitHub page.
2026-10-16	J. Jardine, Lattice24, review of this manuscript in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995)	Review (AI-assisted audit)	Its referee review reports no gap. It states that all eleven sections were read and the geometric core checked by hand, and notes that the unconditional theorem depends on the companion's zero-free theorem. It advises independent expert review of Sections 3 to 7 and reports that no machine experiment on curve and Jacobian arithmetic was run.	Part of a completed audit of the collection's manuscripts without Lean; the reviews are published under CC BY 4.0.

Notes

The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.