{"id":"openai-math/Deterministic-Polynomial-Factorization-over-Prime-Fields","pdf":"https://github.com/openai/math/blob/main/preprints/Deterministic-Polynomial-Factorization-over-Prime-Fields-October-4-2026/Deterministic-Polynomial-Factorization-over-Prime-Fields.pdf","url":"https://github.com/openai/math/tree/main/preprints/Deterministic-Polynomial-Factorization-over-Prime-Fields-October-4-2026","tags":["computational-algebra","polynomial-factorization","algorithms"],"score":0,"title":"Deterministic Polynomial Factorization over Prime Fields","domain":"Theoretical computer science","family":"142","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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*.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-04","reactions":{},"formalized":false,"family_title":"Deterministic polynomial factorization over prime fields"}