View source for 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'''<sub>''p''</sub> 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 ([https://github.com/openai/math 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'''<sub>''p''</sub>. Its number of bit operations is at most an absolute constant times ((''n'' + 1)''L'')<sup>10<sup>12</sup></sup>, 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 ℓ<sub>''q''</sub>, one for each prime ''q'' at most ''n'', with ℓ<sub>''q''</sub> congruent to 1 modulo 12''q'' and ''p'' not a ''q''-th power modulo ℓ<sub>''q''</sub>. 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'''<sub>''p''</sub>. 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''<sup>''q''</sup> = ''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<sup>−6</sup>; the principal character is included, with its pole at 1.
* '''Sources.''' Commit <code>1581d4c</code> of the openai/math repository, folder [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/Deterministic-Polynomial-Factorization-over-Prime-Fields-October-4-2026 Deterministic polynomial factorization over prime fields].
* '''Formalization.''' The collection has no Lean scope note in <code>lean/docs/</code> for this family.
** For the analytic input, the README of Yao Xu's Lean formalization of the primitive-root theorem, [https://github.com/cadamcat/artin-primitive-roots-lean4 cadamcat/artin-primitive-roots-lean4] (commit <code>0c827db</code>), lists the theorem <code>ArtinPrimitiveRoots.HeckeBoundary.thm_hecke_zero_free</code> 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<sup>−6</sup> 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 ==
{| class="wikitable"
! Date !! Work !! Relation !! Public claim !! Public status (checked 17 October 2026)
|-
| 2026-10-08 || teal-sea, [https://github.com/teal-sea/zeta-lab/blob/33b43c6cdbad6dfe2eca17815d30c6ce4cc19dbc/hunts/oct08_extensions/fresh-opportunities.md 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 [https://github.com/teal-sea/zeta-lab/blob/33b43c6cdbad6dfe2eca17815d30c6ce4cc19dbc/hunts/oct08_extensions/routes/algorithm/RESULTS.md 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 || [https://github.com/raullenchai/ai-math-kills-crypto 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, [https://github.com/JJardine919/openai-math-audit/blob/a06a8c6e77974d4c6021338a55a8e91b634f67f7/reviews/rank_499.json review of this manuscript] in [https://github.com/JJardine919/openai-math-audit JJardine919/openai-math-audit] (archived at [https://doi.org/10.5281/zenodo.23422995 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.

[[Category:OpenAI results]]