Browse › Theoretical computer science › 142 Deterministic polynomial factorization over prime fields
Deterministic Polynomial Factorization over Prime Fields
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
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\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$. The proof uses the uniform Hecke zero-free theorem from the companion paper *Primitive roots for every admissible integer base*.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Comments and discussion
- DH and Persiflage, comments on A Brief Digest of Some New OpenAI Results, galoisrepresentations.org (blog comments, 9 Oct 2026). The thread discusses the companion paper's zero-free claim for finite-order Hecke L-functions of cyclotomic fields containing ζ₁₂, which is the analytic input this paper imports as Theorem 10.1; it discusses that claim in the context of Artin's conjecture and does not mention factorization.
- Divesh Aggarwal and commenters, Deterministic Polynomial Factorization Over Finite Fields (LinkedIn, October 2026). Aggarwal highlights the manuscript's significance for deterministic versus randomized computation, while Alon Rosen asks whether it is Lean-verified and about polynomial identity testing; the visible thread does not supply a technical review.
Formalization
- Yao Xu (cadamcat), artin-primitive-roots-lean4, file
Hecke/Boundary.lean(GitHub, 2026). This Lean 4 formalization of the companion paper statesthm_hecke_zero_freeforCyclotomicField n ℚwith12 ∣ nand δ₀ = 10⁻⁶, matching the input this paper imports; when accessed, its proof depended on a lemma markedsorry("this is what part A proves"). The factorization algorithm itself is not formalized there. [AI-generated per source]
Possibly relevant literature (found by the agent, not checked)
- B. Poonen, Using zeta functions to factor polynomials over finite fields (arXiv:1710.00970, Oct 2017). Expounds Kayal's idea of using Schoof's point counting, and Pila's algorithm for abelian varieties, for deterministic factoring; related to the paper's geometric odd-degree splitter on Jacobians of curves Y^q = F(X) and its discussion of Schoof and Pila.
- G. Ivanyos, M. Karpinski, L. Rónyai, N. Saxena, Trading GRH for algebra: algorithms for factoring polynomials and related structures (arXiv:0811.3165, Nov 2008; revised Feb 2009). Removes GRH from several deterministic factoring results via cyclotomic and Kummer extensions of semisimple algebras; related to the paper's construction of q-primary generators in K_q = F_p(ζ_q), which replaces the nonresidue input usually supplied by GRH.
- G. Ivanyos, M. Karpinski, N. Saxena, Schemes for Deterministic Polynomial Factoring (arXiv:0804.1974, 11 April 2008). Its GRH-based m-scheme approach, including polynomial-time splitting for certain prime degrees, provides a comparison for the manuscript's claimed uniform polynomial-time splitting reduction and its stated consequence under GRH.
- M. Arora, G. Ivanyos, M. Karpinski, N. Saxena, Deterministic polynomial factoring and association schemes (arXiv:1205.5653; LMS J. Comput. Math. 17 (2014) 123–140). A GRH-conditional deterministic factoring result via m-schemes; relevant to the paper's survey of conditional deterministic bounds (Rónyai, Evdokimov) and its claim that its reduction gives a polynomial bound under GRH.
- A. Roy, Deterministic polynomial factoring under the assumption of the Extended Riemann Hypothesis (ERH) (arXiv:1406.3672, Master's thesis, 2014–2015). Extends Gao's approach of building a graph on the roots, which fails when that graph is regular; related to the paper's even-degree step, where a tournament on root differences is shown to have non-constant vertex scores.
Digests and expositions
- Sankalp Thakur, Speed Limits I: Multiplying, Transforming, Factoring (Deep End Era, episode 81, undated). The episode includes a segment on family 142 beginning at 00:45:54, and its production credits disclose Claude-generated scripts and synthetic narration reviewed by Thakur. [AI-generated per source] [family-level]
- Azmat, Deterministic Polynomial Factorization over Prime Fields: The Extraordinary Geometry Behind OpenAI’s Proof (Binary Verse AI, 14 October 2026). This exposition traces the even- and odd-degree splitting constructions, norm-equation machinery, and complexity accounting, distinguishing the algebraic reduction from its dependence on the primitive-root companion's asserted Hecke zero-free theorem.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 142
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Deterministic-Polynomial-Factorization-over-Prime-Fields-October-4-2026,
author = {{OpenAI}},
title = {{Deterministic Polynomial Factorization over Prime Fields}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Deterministic-Polynomial-Factorization-over-Prime-Fields-October-4-2026/Deterministic-Polynomial-Factorization-over-Prime-Fields.pdf}{OAI:Deterministic-Polynomial-Factorization-over-Prime-Fields-October-4-2026}},
year = {2026}
}Family 142: Deterministic polynomial factorization over prime fields
Gives a uniform deterministic algorithm that completely factors every nonzero dense degree-n polynomial over a prime field 𝔽p, including multiplicities, in bit complexity polynomial in $(n+1)\log p$. The prime is supplied in binary. No randomness, integer-factorization or primitive-root oracle, or GRH assumption is required.
This is the only paper in this family.