Deterministic Polynomial Factorization over Prime Fields
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*.
Comments and reviews
No comments yet.
API
curl /api/v1/records/openai-math/Deterministic-Polynomial-Factorization-over-Prime-Fields
curl -X POST /api/v1/records/openai-math/Deterministic-Polynomial-Factorization-over-Prime-Fields/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Deterministic-Polynomial-Factorization-over-Prime-Fields/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'