HEXAGONbeta

Deterministic Polynomial-Time Factorization over Finite Fields

A mix of human-written and AI-generated textHuman understanding: some partscs.SC — Symbolic Computationmath.NT — Number Theory

Contributed by Qiyue Tang

Version 1 / Nov 06, 2026 / CC BY 4.0

Abstract

Using prime-field factorization and a Dedekind zeta zero-free theorem, we obtain deterministic polynomial-time algorithms for complete factorization over finite fields and for constructing their presentations from their orders.

Provenance statement

GPT-6-Pro was used to develop the arguments within a seven-hour research window. Codex was used to review the internal reasoning and revise the exposition.

References

  1. E. R. Berlekamp, Factoring polynomials over finite fields , Bell System Tech. J. 46 (1967), 1853--1859.
  2. E. R. Berlekamp, Factoring polynomials over large finite fields , Math. Comp. 24 (1970), 713--735.
  3. D. G. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields , Math. Comp. 36 (1981), 587--592.
  4. D. Cureton and J. Thorner, A quasi-Riemann hypothesis for Dedekind zeta functions , Hexagon 2610.00200v2 (https://hexagonmath.org/2610.00200v2), 2026.hexagon
  5. S. Evdokimov, Factorization of polynomials over finite fields in subexponential time under GRH , Algorithmic Number Theory, Lecture Notes in Comput. Sci. 877 , Springer, 1994, 209--219.
  6. H. W. Lenstra, Jr., Finding isomorphisms between finite fields , Math. Comp. 56 (1991), 329--347.
  7. OpenAI, Deterministic polynomial factorization over prime fields , preprint (https://github.com/openai/math/blob/main/preprints/Deterministic-Polynomial-Factorization-over-Prime-Fields-October-4-2026/Deterministic-Polynomial-Factorization-over-Prime-Fields.pdf), October 4, 2026.link
  8. V. Shoup, New algorithms for finding irreducible polynomials over finite fields , Math. Comp. 54 (1990), 435--447.
  9. V. Shoup, On the deterministic complexity of factoring polynomials over finite fields , Inform. Process. Lett. 33 (1990), 261--267.
  10. J. M. Shunia, Deterministic polynomial-time primality testing with a single binomial congruence , arXiv:2611.02280v1 (https://arxiv.org/abs/2611.02280v1), 2026.arXiv
Show all 11 referencesShow fewer references
  1. P.-J. Spaenlehauer, Deterministic root-finding over finite fields with elliptic curves , 2026. arXiv:2610.32508v1 (https://arxiv.org/abs/2610.32508v1).arXiv

Version history

  1. v1 · 7 pagesSubmitted by Qiyue TangInitial depositSupersededNov 05, 2026
  2. v2 · 8 pagesSubmitted by Qiyue TangSubmitted as a new versionCurrentNov 06, 2026