← All problems

O16 — Factoring polynomials modulo a prime

Let pp be a prime supplied in binary, and let f∈Fp[x]f\in\mathbb F_p[x] be supplied by its coefficients. For nonzero ff of degree nn, the task is to output its complete factorization: a scalar c∈Fp×c\in\mathbb F_p^\times, distinct monic irreducible polynomials g1,…,gt∈Fp[x]g_1,\ldots,g_t\in\mathbb F_p[x], and positive integer multiplicities e1,…,ete_1,\ldots,e_t such that

f=c∏i=1tgiei.f=c\prod_{i=1}^{t}g_i^{e_i}.

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 nn and log⁡p\log p), 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)

References

Progress summary

Never refreshed

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 solutionHide 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

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Deterministic-Polynomial-Factorization-over-Prime-Fields-October-4-2026/Deterministic-Polynomial-Factorization-over-Prime-Fields.pdf

  • OpenAI-142-01-Deterministic-Polynomial-Factorization-over-Prime-Fields.pdf662,250 bytesOpen