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.

Manuscript

Deterministic Polynomial Factorization over Prime Fields

October 4, 2026 · source · cite as \cite{OAI:Deterministic-Polynomial-Factorization-over-Prime-Fields-October-4-2026}

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.

Result 142 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.