Family 142Theoretical computer scienceNo LeanNot yet digested
Deterministic polynomial factorization over prime fields
Gives a uniform deterministic algorithm that completely factors every nonzero dense degree-n polynomial over a prime field 𝔽, including multiplicities, in bit complexity polynomial in . The prime is supplied in binary. No randomness, integer-factorization or primitive-root oracle, or GRH assumption is required.
Manuscripts in this family · 1
Deterministic Polynomial Factorization over Prime Fields
Oct 4, 2026·Deterministic-Polynomial-Factorization-over-Prime-Fields.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 given by its dense coefficient list, the algorithm computes the irreducible factors and their multiplicities using a number of bit operations polynomial in . The proof uses the uniform Hecke zero-free theorem from the companion paper *Primitive roots for every admissible integer base*.