Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence

arXiv:2611.02280 · math.NT, cs.CC · Submitted 2026-11-01 · Read on arXiv

math.NT, cs.CC

Submitted: 2026-11-01

Updated: 2026-11-01

Comments: 12 pages. An earlier version appeared as Revision 2 of ECCC TR23-200: https://eccc.weizmann.ac.il/report/2023/200/#revision2

Code: https://github.com/AxiomMath/DedekindZetaZeroFree

License: http://creativecommons.org/licenses/by/4.0/

The gist: We give a deterministic polynomial-time primality test whose main verification is the congruence (1+X) n=1+X n in C n[X]/(X r-b(Y)), where C n=(Z/n Z)[Y]/(Φ r(Y)).

Abstract

We give a deterministic polynomial-time primality test whose main verification is the congruence (1+X) n=1+X n in C n[X]/(X r-b(Y)), where C n=(Z/n Z)[Y]/(Φ r(Y)). Two identities in the coefficient ring normalize b and ensure compatibility with the main congruence. A finite-field root count and a lattice bound show that an accepted input is a prime power; elementary preprocessing excludes nontrivial perfect powers. We construct b deterministically using Jacobi sums and the uniform Dedekind-zeta zero-free theorem of Cureton and Thorner, which extends OpenAI's Hecke zero-free theorem. The total bit complexity is L 32+o(1), where L= 2 n, and verification after constructing b costs L 6+o(1). More generally, for a fixed real algebraic 1/2 at mostθ<1, a common zero-free boundary s>θ for the relevant Dedekind zeta functions gives L 6,(1-θ)-1+o(1). This bound reaches L 6+o(1) at θ=5/6, and hence under GRH. We state a fixed-base modification of Agrawal's conjecture for odd integers passing the base- 2 Fermat test, using the modulus X r-2 with r the least positive integer not dividing n(n-1).

Sources

Related papers