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]/(\Phi_r(Y))$. Two identities in the coefficient ring normalize $b$ and ensure compatibility with the main congruence. A finite-field root count...