Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence
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
- K ab has the Bogomolov property for canonical heights
- Quasi-Jacobi forms, Appell-Lerch functions, and false theta functions as q-brackets of functions on partitions
- Wasserstein rates of all orders for the Sato-Tate law of Kloosterman sums
- Completing the classification of torsion over sextic fields for elliptic curves defined over Q
- Riemann functions for almost primes and their counting errors
- Topological flatness of orthogonal spin local models