Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence
Abstract
We give a deterministic polynomial-time primality test whose main verification is the congruence (1+X)n=1+Xn in Cn[X]/(Xr−b(Y)), where Cn=(ℤ/nℤ)[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 L32+o(1), where L=⌈log2 n⌉, and verification after constructing b costs L6+o(1). More generally, for a fixed real algebraic 1/2≤θ<1, a common zero-free boundary ℜ s>θ for the relevant Dedekind zeta functions gives Lmax{6,(1−θ)−1}+o(1). This bound reaches L6+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 Xr−2 with r the least positive integer not dividing n(n−1).
Related
- The Sufficient Set of Congruences of Binomial Coefficients for Primality
- A Congruence Conjecture of Z.-W. Sun for Reciprocal Central Binomial Sums
- Congruence Jumping in Polynomial Divisibility Systems: Arithmetic Structure and Solution Sets
- Reciprocal Dynamics in Polynomial Congruence Jumping: Integral Orbits and Valuation Cones
- A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
BibTeX
@misc{shunia2026deterministic,
title = {{Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence}},
author = {Joseph M. Shunia},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02280},
eprint = {2611.02280},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02280},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence
AU - Joseph M. Shunia
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.02280
UR - https://arxiv.org/abs/2611.02280
AB - 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=(ℤ/nℤ)[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=⌈log_2 n⌉, and verification after constructing b costs L^6+o(1). More generally, for a fixed real algebraic 1/2≤θ<1, a common zero-free boundary ℜ s>θ for the relevant Dedekind zeta functions gives L^max{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).
ER -