Deterministic polynomial factorization over prime fields
OpenAI research collection Ā· 1 manuscript Ā· Source checked 2026-10-19
OpenAI's result summary
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.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
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ā\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ā¦
Full source abstract
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ā\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*.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.