O16 — Factoring polynomials modulo a prime
Let be a prime supplied in binary, and let be supplied by its coefficients. For nonzero of degree , the task is to output its complete factorization: a scalar , distinct monic irreducible polynomials , and positive integer multiplicities such that
For a nonzero constant, this is the trivial factorization with no irreducible factors; the zero polynomial is excluded because it has no finite irreducible factorization. The question is whether a deterministic algorithm can perform this task in time polynomial in the input length (equivalently, polynomial in and ), without an unproved number-theoretic hypothesis. Arora, Ivanyos, Karpinski, and Saxena (2012) Gao (1999)
Background
Polynomial factorization over finite fields has randomized polynomial-time algorithms, making the deterministic question a derandomization problem. A standard reduction converts general factoring to finding a proper factor of a squarefree polynomial that splits completely over a prime field. This reduction focuses attention on extracting structure from the roots, rather than merely testing whether a proposed factorization is correct. Gao (1999)
Gao’s 1999 work pursued this route under the extended Riemann hypothesis. It introduced stringent balance conditions on the root set of a completely splitting polynomial and conjectured that no set of more than one element satisfies the strongest, “super square balanced,” conditions. That conjecture was presented as a possible route from conditional factoring results to deterministic polynomial-time factoring without the hypothesis. Gao (1999)
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 1
Claimed by OpenAI.See full solution
Claims a uniform deterministic algorithm computing complete irreducible factorization, with multiplicities, of a nonzero dense polynomial over a binary-encoded prime field in bit complexity polynomial in (deg f + 1) log p; the manuscript uses its companion uniform Hecke zero-free theorem.
Repository: https://github.com/openai/math
- OpenAI-142-01-Deterministic-Polynomial-Factorization-over-Prime-Fields.pdfOpen