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.
released 2026-10-04 | 4 theorems · 16 lemmas · 26 proofs · 22,529 words |
PLAY LEVEL 1 »(pdf)
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*.