142. Deterministic polynomial factorization over prime fields

Deterministic polynomial factorization over prime fields

1 paper

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.

Papers 1

Deterministic Polynomial Factorization over Prime Fields

OpenAI · 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*.

Read PDF Download Source

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

Deterministic polynomial factorization over prime fields

Watch

Papers 1

Deterministic Polynomial Factorization over Prime Fields

Formal verification