← 研踪 PaperTrailarXiv:2611.02280 · v1
Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence
首次提交 2026-11-02 07:17
版本更新 2026-11-02 07:17
雷达观测 2026-11-04 23:42
摘要
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=(\mathbb{Z}/n\mathbb{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=\lceil\log_2 n\rceil$, and verification after constructing $b$ costs $L^{6+o(1)}$. More generally, for a fixed real algebraic $1/2\leθ<1$, a common zero-free boundary $\Re 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)$.
作者备注：12 pages. An earlier version appeared as Revision 2 of ECCC TR23-200: https://eccc.weizmann.ac.il/report/2023/200/#revision2
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-02 07:17 · 最新观测版本
Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence
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=(\mathbb{Z}/n\mathbb{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=\lceil\log_2 n\rceil$, and verification after constructing $b$ costs $L^{6+o(1)}$. More generally, for a fixed real algebraic $1/2\leθ<1$, a common zero-free boundary $\Re 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)$.
查看此版本解读 →查看此版本原文 ↗