Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence

Introduction

For a prime $n$, the identity

holds in every commutative algebra of characteristic $n$. A primality test based on this identity must choose an algebra small enough to compute in and sufficiently restrictive to exclude composite inputs. We construct such an algebra deterministically, using one shift, one binomial relation, and exponent $n$.

The coefficient ring and the final algebra are

where $r$ is odd and squarefree and $\Phi_r$ is the $r$th cyclotomic polynomial. Thus the test can equally be written in the multivariate quotient

Arithmetic is performed in the full quotient, which may have zero divisors. Field quotients enter only in the proof.

For a suitable auxiliary integer $D$, the acceptance equalities are

The single binomial congruence is (5), evaluated in $\mathcal{A}_n$. The two checks in $C_n$ and elementary integer preprocessing complete the test.

The deterministic parameter construction uses a uniform zero-free theorem. OpenAI proved a common width $10^{-6}$ for finite-order Hecke $L$-functions over cyclotomic fields containing $\mu_{12}$ [11 Theorem 1.2]. Cureton and Thorner extended this approach to all number fields and obtained the following stronger result.

This theorem has a published Lean formalization generated with AxiomProver [3]. We use $\delta= 1/32$ in the main algorithm, so that its search cutoff is computed by integer powering. We retain $\delta$ in the estimates to exhibit the effect of stronger analytic bounds. The uniformity needed below concerns the zero-free boundary; Lemma 4.1 separately makes the effective dependence on field degree and discriminant explicit.

The main result uses Theorem 1.1 as its analytic input. Corollary 6.1 gives the dependence of the running time on a general uniform zero-free boundary. Any stronger boundary satisfying its hypotheses therefore gives the corresponding improved bound by direct substitution, with the same parameter construction and algebraic acceptance criterion. § 6.1 also identifies the $5/6$ threshold and the GRH endpoint.

The proof has three components. A normalized coefficient first produces a cyclic orbit of $r$ linear factors in a field extension. Bernstein’s root-counting and lattice method [4] then excludes inputs with two distinct prime factors. Next, an Odlyzko–Pomerance construction gives $r = L^{2+o(1)}$, with every prime factor of $r$ of size $L^{o(1)}$. Finally, we construct the coefficient by combining Jacobi sums for those small prime factors. Treating the prime degrees separately keeps the number-field degrees in the auxiliary-prime estimate small.

The AKS theorem established deterministic polynomial-time primality testing [2]. Berrizbeitia and Cheng developed tests using binomial extensions and a small number of congruences [6, 7]. Bernstein gave an essentially quartic random-time primality-proving algorithm [4]; its group-size argument is the algebraic foundation used here. Lenstra and Pomerance subsequently obtained an unconditional $L^{6+o(1)}$ deterministic algorithm using Gaussian periods [10]. The present construction concerns the deterministic realization of the particular congruence (5), with a normalized coefficient in the full cyclotomic quotient. Its auxiliary-prime search dominates the stated total bound.

Throughout, $\log$ is the natural logarithm unless a base is displayed. The notation $\widetilde{O}$ suppresses factors polynomial in logarithms. All complexity statements count bit operations; $o(1)$ is as $L \to\infty$, with $\delta$ fixed.

An algebraic acceptance criterion

We first prove that the three acceptance identities force $n$ to be a prime power. This part of the argument depends only on the identities and the sizes of the degrees, not on how the coefficient is constructed.

Let $n>3$ be odd, and choose an odd squarefree integer $r>2$ and a positive integer $D$ such that

In particular, $\lambda(r)\mid D$, so $n^D\equiv1\pmod r$ and the exponent in (3) is integral. For odd $r$, define

Our exact size condition is

This condition uses integer arithmetic only: the logarithm floor is the bit length of $B_r$ minus one.

Proof. Since $\gcd(n,r)=1$, raising a primitive $r$th root to its $n$th power permutes the primitive roots. The integral cyclotomic relation therefore makes the substitution well-defined. An inverse is substitution by $Y^v$ for $nv\equiv1\pmod r$. Also $Y^r=1$ and $n^D\equiv1\pmod r$, which prove $\sigma^D=1$.

A maximal ideal of $C_n$ lies over a prime divisor $p$ of $n$. Because $p\nmid r$, the polynomial $X^r-1$ is squarefree in $\mathbb{F}_p[X]$. The roots of $\Phi_r$ are precisely the primitive $r$th roots, whose Frobenius orbits have length $\operatorname{ord}_r(p)$. The quotient fields consequently have the stated degrees. Finally, $p^D\equiv1\pmod r$ implies $e\mid D$. □

Proof. Equation (4) gives $\sigma^i(b)=b^{n^i}$ by induction. Put $F(X)=(1+X)^n-1-X^n$. Equation (5) says $X^r-b\mid F(X)$ in $C_n[X]$. Applying $\sigma^i$ to its coefficients gives $X^r-b^{n^i}\mid F(X)$. Substituting $X^{n^i}$ and using

gives $(1+X^{n^i})^n=1+X^{n^{i+1}}$ in $A_n$. Starting at $j=0$, this proves the assertion by induction. No additivity of $n$th powering for composite $n$ is used. □

Proof. Put $N=n^D$. The element $Y$ is a unit, so (3) makes $b$ a unit. Suppose for a contradiction that $n$ has at least two distinct prime divisors. Choose a field quotient $k=\mathbb{F}_{p^e}$ of $C_n$ as in Lemma 2.1, and put $P=p^e$. We use the same names for the images of $Y$ and $b$. One has $P\mid N$, and $Y$ has order $r$ in $k^\times. Choose a root $\alpha$ of $X^r-b$ in an algebraic closure of $k$. Normalization and Lemma 2.2 imply

For the last identity, substitute $Y^i\alpha$ in $(1+X)^N=1+X^N$ and use $N\equiv1\pmod r$. Each $u_i$ is nonzero: otherwise $\alpha=-Y^{-i}$, so $b=(-1)^r$ and $Y=b^{(N-1)/r}$ would have order at most two. Let $G$ be the finite multiplicative group generated by the $u_i$ in $k(\alpha)^\times$.

We first prove $|G|\ge B_r$, using the signed-product count recorded by Bernstein [4 Section 3]. Consider all integer vectors $a=(a_0,\ldots,a_{r-1})$ for which the positive entries sum to at most $h$ and the absolute values of the negative entries also sum to at most $h$. If exactly $j$ entries are negative, their positions can be chosen in $\binom{r}{j}$ ways, their absolute values in $\binom{h}{j}$ ways, and the remaining nonnegative entries in $\binom{r-j+h}{h}$ ways. This gives exactly $B_r$ vectors.

Their products $\prod_i u_i^{a_i}$ are distinct. Indeed, suppose two such products are equal. Taking successive $N$th powers rotates all indices, so the equality holds with $\alpha$ replaced by each of the $r$ distinct elements $Y^j\alpha$. Clearing denominators produces an equality of two polynomials at all those elements; each polynomial has degree at most $2h=r-1$. Their difference is therefore zero by the field root bound. Unique factorization into the pairwise distinct factors $1+Y^iZ$, whose constant terms are all 1, makes the original exponent vectors equal. Hence

For the upper bound, $r\mid P-1$, and $b\in k$ gives $\alpha^P=Y^t\alpha$ for some integer $t$. Set $H=N/P>1$. Frobenius in characteristic $p$, followed by injectivity of $P$th powering, gives

Consider the lattice

It has determinant $r$, because $1-t$ and $t$ generate the unit ideal in $\mathbb{Z}/r\mathbb{Z}$. The symmetric convex hexagon

has area

since $\log H+\log P=\log N$. Minkowski’s convex body theorem gives a nonzero lattice point in this closed hexagon. The equality case follows by slightly enlarging the hexagon and using discreteness. Change its sign if necessary to make $a\ge0$. If $c\ge0$, put $U=H^aP^c$ and $V=1$; if $c<0$, put $U=H^a$ and $V=P^{-c}$. Equation (10) and the lattice relation give $g^U=g^V$ for every $g\in G$, and

Moreover, $U\ne V$. For $c\ge0$ this follows from $(a,c)\ne(0,0)$. For $c<0$, equality would contradict the fact that $H$ has a prime factor other than $p$ when $a>0$; when $a=0$, it would give $1=P^{-c}>1$. Every element of $G$ is consequently a root of $Z^{|U-V|}-1$ in a field. Thus

The last inequality follows from (8), because $\log_2N\le DL$. This contradicts (9). Therefore $n$ has only one distinct prime divisor.

Remark 2.4. The argument does not require $X^r-b$ to be irreducible modulo every prime divisor of $n$. It takes a root in a field extension and obtains the needed distinct products from the cyclic rotation and the field root bound. Likewise, $C_n$ itself may have zero divisors. Its rank $\varphi(r)$ measures arithmetic cost, whereas the smaller number $e\mid D$ controls the lattice bound.

Choosing the degrees

We first record the size of the signed-product count. The improvement from signed products is due to Voloch and Vaaler, as explained in Bernstein’s analysis [4 Section 3].

Proof. In (7), retain the term with $j=\lfloor(1-1/\sqrt{2})r\rfloor$. Stirling’s formula for its three binomial coefficients gives $\log_2 B_r\ge\kappa r-O(\log r)$. For the upper bound, set $t=\sqrt{2}-1$. The generating function for one signed exponent, recording positive and negative weights separately, is $1+z/(1-z)+w/(1-w)$. Every vector counted by $B_r$ has combined weight at most $2h$, so

Since $2h=r-1$, this has the asserted exponential rate. The asymptotic threshold follows on substituting this estimate in (8). For the simpler bound, the count includes all nonnegative 0–1 vectors of weight at most $h$ and their negatives, with zero counted once. Their number is $2^r-1$. Hence $\lfloor\log_2 B_r\rfloor\ge r-1$, and $3(r-1)^2\ge r^2\ge D^2L^2r$ for the stated range.

To meet the size condition with small $D$, we build $r$ from primes $q$ for which $q-1\mid D$. The following parameter theorem is due to Odlyzko and Pomerance; we use the form in Adleman–Pomerance–Rumely [1 Theorem 3], also used by Bernstein [4]. There is an absolute constant $C$ such that, for every sufficiently large $H$, some positive integer $D$ satisfies

Proof. Enumerate even positive integers $D$. For each, enumerate the primes $q \le D+1$ with $q-1 \mid D$ and $q \nmid D$. Multiply these primes in increasing order, checking (8) after each prefix whose product exceeds 2. If all primes are exhausted without success, continue to the next $D$.

To bound the search, apply (11) with $H=L^3$. The supplied $D$ is $L^{o(1)}$. Deleting the primes dividing $D$ removes a product at most $D$, so the remaining product is at least $H/D \ge D^2L^2$ for sufficiently large $L$. Such a successful $D$ is even: if $D$ were odd, the product in (11) would contain only the prime 2. For even $D$, excluding $q \mid D$ also excludes 2. Proposition 3.1 now guarantees success. For each fixed smaller $L$, applying (11) with $H$ sufficiently large gives the same termination argument.

At the first successful prefix the product obeys

Conversely, Proposition 3.1’s upper estimate and (8) give $r \gg D^2L^2$, establishing the stated asymptotic scale. Each trial has $L^{o(1)}$ small primes and divisibility checks. The exact count $B_r$ can be evaluated from binomial recurrences in $\widetilde{O}(r^2)$ bit operations: there are $O(r)$ terms, each with $O(r)$ bits. The $L^{o(1)}$ trials fit the claimed bound. □

The factorization of $r$ is known from its construction. To enforce $\gcd(n,r)=1$, test its known prime factors against $n$. A common prime factor proves compositeness unless it equals $n$, in which case $n$ is prime.

A uniform auxiliary-prime bound

For each prime $q \mid r$, we seek a prime $\ell$ modulo which $n$ is a $q$th power nonresidue. Such a prime will define the character used in § 5. We prove its existence for prime inputs by applying Theorem 1.1 to Kummer extensions of degree $q$. The following smoothed estimate makes the dependence on the number field explicit.

Proof. This is the smoothed explicit-formula calculation in [11 Section 9.2, especially (9.9)]; we recall the dependence on the field. Mellin inversion applied to $-\zeta_F'/\zeta_F$ and a contour shift from $\Re s=2$ to $\Re s=-1/2$ give

where $\rho$ runs over nontrivial zeros with multiplicity and $(r_1,r_2)$ is the signature. The functional equation bounds the integral on the left line with the displayed dependence. The uniform zero count in a unit interval at height $T$ is $O(\log\Delta_F + d_F \log(2 + |T|))$. The Mellin transform decays faster than every inverse power of $|T|$ in bounded vertical strips. Since $\Re\rho\le1-\delta$, the zero sum is absolutely convergent and is bounded by $O_w(x^{1-\delta}(\log\Delta_F + d_F))$. The residue at zero and the left-line integral are absorbed in the same bound. These estimates have effective absolute constants for fixed $w$.

Proof. Set $K = \mathbb{Q}(\mu_{12q})$ and $M = K(n^{1/q})$. The prime $n$ is unramified in $K$, so $X^q-n$ is Eisenstein at a prime of $K$ above $n$. Thus $[M:K] = q$, and $M/K$ is cyclic because $\mu_q \subset K$. By hypothesis, both $\zeta_K$ and $\zeta_M$ are zero-free in $\Re s > 1-\delta$. For the stated algorithm, Theorem 1.1 supplies this hypothesis with $\delta= 1/32$.

The cyclotomic discriminant bound and the discriminant of $X^q-n$ give

More explicitly, the relative discriminant divides $(q^q n^{q-1})\mathcal{O}_K$, and the discriminant tower formula gives the second bound. Lemma 4.1 therefore yields

Consider an unramified degree-one prime of $K$. If it splits in $M$, its first-power contribution cancels against the contributions of the $q$ primes above it, after the factor $1/q$. Otherwise it is inert, since the extension has prime degree, and its positive first-power contribution remains. A surviving prime lies above a rational prime $\ell\equiv1 \pmod{12q}$ for which $n$ is not a $q$th power in $\mathbb{F}_\ell$. This is exactly the last condition in (15).

All terms of prime-ideal residue degree at least two, and all higher prime powers, contribute in absolute value at most $O_w(q\sqrt{x}\log^2(2x))$ to (16). To see the field dependence, a field of degree $d$ contributes at most $O_w(d\sqrt{x}\log^2(2x))$; the weighted total degree here is $[K:\mathbb{Q}]+[M:\mathbb{Q}]/q=O(q)$. Ramified degree-one first powers contribute at most $O_w(q\log(6qn))$, since the ramified rational primes divide $6qn$.

Take $x=T_\delta\left(q(L+\log q+2)\right)^{1/\delta}$. For an effectively large constant $T_\delta$, the error in (16) is less than half its main term. The discarded terms are smaller as well, uniformly in $q$ and $n$, because $\delta< 1/2$. Some surviving prime lies in $(x,2x)$. Absorbing $2T_\delta$ in $C_\delta$ proves the lemma.

All primes $q\mid r$ are at most $D+1$. Hence a common search bound, increased by rounding if needed, is

For the search itself it suffices to test primes $\ell\equiv1\pmod q$; Lemma 4.2 supplies a prime even in the smaller progression. Only prime-input existence is needed. If a search fails within the bound, the algorithm rejects.

Constructing the normalized coefficient

Characters defined by the input

For each prime $q \mid r$, choose a prime $\ell_q \le B$ with $q \mid\ell_q-1$, $\ell_q \nmid n$, and $n^{(\ell_q-1)/q} \not\equiv1 \pmod{\ell_q}$. Put

Its order in $\mathbb{F}_{\ell_q}^{\times}$ is exactly $q$. For $u \ne0$ define $j_q(u) \in\{0,\ldots,q-1\}$ by

This is a multiplicative-group homomorphism to $\mathbb{Z}/q\mathbb{Z}$, written additively, and $j_q(n \bmod\ell_q)=1$. Its values are computed by a table of the $q$ powers of $t_q$.

Choose $s_q \in\{1,\ldots,q-1\}$ satisfying

The inverse exists by (6) and squarefreeness. In $R_q=(\mathbb{Z}/n\mathbb{Z})[Z]/(\Phi_q(Z))$, define the order-$q$ character

In particular, $\chi_q(n)=Z^{s_q}$ and $\chi_q(-1)=1$, since $q$ is odd. This construction needs neither a primitive root modulo $\ell_q$ nor a factorization of $\ell_q-1$.

Jacobi sums and a binary recurrence

For positive integers $a,c$, set

Here $\chi=\chi_q$ and $\ell=\ell_q$. The terms for $u=0,1$ vanish. The other terms are powers of $Z$, so the sum is computed by counting $q$ possible exponents before reduction modulo $(n,\Phi_q(Z))$. Define

Proof. For this proof only, work in $R_q[T]/(\Phi_{\ell}(T))$ and put $\tau_a=\sum_{u\ne0}\chi(u)^aT^u$. The integral Gauss–Jacobi identities give

These follow by grouping the two summation indices according to their sum; the zero-sum terms vanish in (21) because the product character is nontrivial. They are identities in integral cyclotomic rings and remain valid after reduction modulo $n$; see also [8 Theorem 2.4]. Iteration gives $\tau_1^q=\beta_q$.

For a shorter computation, maintain $a<q$ and $A\in R_q$ with $\tau_1^a=A\tau_a$, starting at $a=1$, $A=1$. Follow the binary expansion of $q-1$ after its leading bit. On a doubling, set

If the next bit is 1, then set

Every resulting index is at most $q-1$, so no step uses a trivial product character. At the end, $\tau_1^{q-1}=A\tau_{q-1}$; multiplying by $\tau_1$ gives $\beta_q=\ell A$. The coefficient ring embeds in the displayed extension, since its defining polynomial is monic, so this is an identity in $R_q$. There are $O(\log q)$ steps and no divisions.

Combining the prime degrees

Substitution $Z \mapsto Y^{r/q}$ defines a homomorphism $R_q \to C_n$: the polynomial $\Phi_q(Y^{r/q})$ is divisible by $\Phi_r(Y)$ over $\mathbb{Z}$. Form

Each computation in $Z$ takes place in a ring of rank $q-1$; the substitution combines its result with the other prime degrees in the common coefficient ring $C_n$.

Proof. Put $N=n^D$. In $R_q$, $N$th powering fixes every coefficient, because $n^D\equiv1\pmod q$ and the scalar field is $\mathbb{F}_n$. For the Gauss sum from Lemma 5.1, Frobenius and reindexing give

The scalar $\ell_q$ is invertible modulo $n$, so (22) makes $\tau_1$ a unit. Since $\beta_q=\tau_1^q$ and $q\mid N-1$, cancellation gives

This identity holds in $R_q$, by its injection into the monic extension used in the proof. Substituting into (23),

Indeed, modulo each prime $q\mid r$, all but its own summand vanish, and (18) makes the remaining exponent $1$. The Chinese remainder theorem gives the exponent $1$ modulo $r$. This proves (3). Finally, $n$th powering is Frobenius in every commutative algebra of characteristic the prime $n$. It gives $b(Y)^n=b(Y^n)$ and $(1+X)^n=1+X^n$, proving the other two equalities.

The algorithm and its bit complexity

Here is the complete algorithm, with $\delta=1/32$ and an effective constant $C_\delta$ from Lemma 4.2 fixed in advance. One may take $C_\delta$ to be an integer, so the search bound (17) is computed by integer powering.

1. Reject integers below 2; accept 2 and 3; reject even inputs greater than 2. Reject nontrivial perfect powers.

2. Construct $D,r$ as in Proposition 3.2. For every prime $q\mid r$, if $q\mid n$, accept when $q=n$ and otherwise reject. Construct $\Phi_r(Y)$ modulo $n$.

3. Sieve the primes up to $B$ in (17). If a prime in the sieve divides $n$, accept when it equals $n$ and otherwise reject. For every $q \mid r$, select a prime $\ell_q \le B$ with $\ell_q \nmid n$, $q \mid\ell_q - 1$, and $n^{(\ell_q-1)/q} \not\equiv1 \pmod{\ell_q}$. Reject if any such search fails.

4. Compute the tables $j_q$, the residues $s_q$, and the Jacobi-sum coefficients $\beta_q$ using the binary recurrence. Form $b$ by (23).

5. Check (3), (4), and (5). Accept if and only if all three hold.

Proof of Theorem 1.2. If the input is prime, preprocessing cannot reject it. Lemma 4.2, using Theorem 1.1, ensures all searches succeed, and Proposition 5.2 proves acceptance. A composite input accepted at the last step would be a prime power by Theorem 2.3, contrary to the preprocessing. The earlier acceptance branches identify the input with a known prime. This proves correctness on every input.

We give the cost bounds in some detail, including the construction of the coefficient. The degree search costs $L^{4+o(1)}$ by Proposition 3.2. Elementary integer-root methods for exponents up to $L$ detect nontrivial perfect powers within $L^{4+o(1)}$ as well.

The sieve up to $B$ uses $\widetilde{O}(B)$ bit operations. Compute $n$ modulo all its primes with a product tree and a remainder tree [5]. The total bit length $S$ of these moduli is at most $O(B \log B)$. With fast multiplication and division, the trees cost $\widetilde{O}(S+L)=\widetilde{O}(B+L)$: at every tree level the node lengths sum to $O(S)$, and there are $O(\log B)$ levels. This avoids an extra factor $L$ from reducing $n$ separately for each candidate.

Each small-prime modular exponentiation costs a polynomial in $\log B$. There are $O(\log r)$ primes $q \mid r$, all of size $L^{o(1)}$. Testing the candidates for all $q$ consequently costs $L^{1/\delta+o(1)}$ in total. The character tables $j_q(u)$ are computed by modular exponentiation and lookup among $q$ possibilities. Each needed Jacobi sum is accumulated by scanning $u=2,\ldots,\ell_q-1$ and counting its exponent modulo $q$. These counts have $O(\log\ell_q)$ bits; the scan does not require an $L$-bit modular addition for each term. All scans, including the $O(\log q)$ sums for each $q$, therefore fit the same $L^{1/\delta+o(1)}$ bound. Arithmetic in the local rings of rank $q-1=L^{o(1)}$, after reduction of the counts, costs at most $L^{2+o(1)}$ over all $q$.

Put $m=\varphi(r)\le r=L^{2+o(1)}$. Fast polynomial multiplication and monic reduction give multiplication costs

These bounds apply over $\mathbb{Z}/n\mathbb{Z}$ without assuming it is a field. For the second, polynomial multiplication in $X$ over $C_n$, followed by $X^r=b$, gives the stated bound; equivalently one may use bivariate Kronecker substitution and monic reductions. Forming (23) costs $L^{3+o(1)}$. The coefficient checks cost $L^{4+o(1)}$, because the exponents have at most $O(DL)$ bits. Substitution $Y\mapsto Y^n$ is performed using $Y^r=1$ followed by reduction modulo $\Phi_r$.

The main congruence needs $O(L)$ multiplications in $A_n$, for total cost

Finally, $\Phi_r$ is constructible by exact monic divisions from the polynomials $Y^d-1$ for the known divisors $d\mid r$. There are $r^{o(1)}$ such divisors. Even classical polynomial division with elementary $L$-bit coefficient arithmetic costs at most $r^{2+o(1)}L^2=L^{6+o(1)}$. This also shows that no polynomial-factorization subroutine is hidden in the construction. Combining the bounds gives

which proves the theorem.

The auxiliary-prime search determines the exponent in the stated bound. The construction does not factor $n-1$, $n^D-1$, or any $\ell_q-1$.

Dependence on the zero-free boundary

We now record conditional improvements under stronger analytic hypotheses. The proof of Theorem 1.2 is complete without these additional inputs. For the refinements, it suffices to have a common zero-free boundary for the fields $\mathbb{Q}(\mu_{12q})$ and $\mathbb{Q}(\mu_{12q},n^{1/q})$, for prime inputs $n>3$ and odd primes $q\ne n$; a theorem over all number fields supplies this uniformly.

Proof. For $1/2<\theta<1$, put $\delta=1-\theta$ in Lemma 4.2. Its proof uses only the two stated fields, so the weaker hypothesis of this corollary suffices. Since all $q\mid r$ satisfy $q\le D+1=L^{o(1)}$, the common cutoff is $B=L^{1/(1-\theta)+o(1)}$. The sieve, remainder trees, character tables, and local Jacobi-sum computations have this same bound; the remaining work costs $L^{6+o(1)}$.

For completeness, the cutoff is effective even when the exponent is not an integer. If $A$ denotes the integer base in (17), approximate $1/(1-\theta)$ from above by a dyadic rational within $1/\log_2 A$. This increases its power of $A$ by at most a factor of 2. Since $\theta$ is fixed and algebraic, such an approximation is computable in time polynomial in $\log A$. Its denominator can be $O(\log A)$, so integer powering and integer-root extraction compute an upper-rounded cutoff in time polynomial in $\log A$. This cost is negligible in the displayed bound.

At the endpoint $\theta=1/2$, Lemma 4.1 remains valid with $\delta=1/2$. The proof of Lemma 4.2 gives an error $O(q(L+\log q+2)\sqrt{x})$ in (16), and discarded prime-power and higher-degree terms $O(q\sqrt{x}\log^2(2x))$. Choosing a sufficiently large absolute constant $T$ and taking

makes their sum, together with the ramified contribution, smaller than the main term. Thus a suitable prime satisfies

Replacing the logarithms by upper-rounded binary logarithms changes only an absolute factor. The common cutoff is consequently $L^{2+o(1)}$. The sieve, tables, and local coefficient arithmetic fit this bound. Forming $b$ from the local coefficients costs $L^{3+o(1)}$, and the remaining algebraic work costs $L^{6+o(1)}$. GRH for these Dedekind zeta functions supplies the endpoint hypothesis. Finally, $1/(1-5/6)=6$ gives the stated threshold. $\square$

The exponent supplied by (25) reaches 6 at $\theta= 5/6$ and stays 6 throughout $1/2 \le\theta\le5/6$. Thus 6 is the best exponent obtained by improving the zero-free input alone in the present construction and cost analysis. It is an upper-bound threshold, not a lower bound for every implementation of this test. A smaller exponent would require a faster algebraic stage or a different parameter construction. In particular, the present argument does not yield a bound below the $L^{6+o(1)}$ Gaussian-period algorithm of Lenstra and Pomerance [10].

The RH hypothesis here concerns the Dedekind zeta functions of the varying cyclotomic and Kummer fields. RH for $\zeta_{\mathbb{Q}}$ alone does not supply that hypothesis. Table 1 records the resulting exponents; the $o(1)$ terms tend to zero as $L \to\infty$, with the analytic boundary fixed.

Analytic input	Boundary $\theta$	Search exponent	Total exponent
Cureton–Thorner [9]	$31/32$	$32$	$32$
Assumed $5/6$ boundary	$5/6$	$6$	$6$
GRH for the relevant fields	$1/2$	$2$	$6$

Remark 6.3 (A two-equality form). If retaining the exponent $n$ is unnecessary, one may replace (4) and (5) by

Together with (3), this gives the rotation used in Theorem 2.3 directly. Prime inputs satisfy it, and the same proof applies. Its asymptotic verification bound is unchanged because $D=L^{o(1)}$, although its exponent is longer.

A fixed-base conjecture

The coefficient $b(Y)$ in the proved construction enforces the normalization needed for the cyclic rotation. A simpler possibility is to fix the coefficient at 2 and choose the degree directly from the input. The following conjecture proposes such a test for odd inputs, including a preliminary base-2 Fermat check.

Agrawal’s conjecture, as recorded in [2 Conjecture 6.1], asserts that if $r$ is prime, $r \nmid n$, and $(X-1)^n \equiv X^n-1 \pmod{n,X^r-1},$ then $n$ is prime or $n^2 \equiv1 \pmod r$. The conjecture below is a modification of that proposal: it uses roots of 2 in place of roots of unity, the shift $+1$, and the least nondivisor of $n(n-1)$ as the degree. The two conjectures are not asserted to be equivalent.

The base-2 Fermat congruence is an explicit condition of the test. The degree $r$ need not be prime. It is necessarily a prime power: otherwise it would be the least common multiple of its proper prime-power factors, each of which divides $n(n-1)$ by minimality.

The open step is to obtain a comparable restriction on composite inputs from the fixed coefficient 2 and this degree rule. The normalization and cyclic rotation used in Theorem 2.3 are supplied by our coefficient construction; they have not been deduced from the congruence in Conjecture 7.1.

AI Assistance Disclosure

OpenAI’s GPT-6 Astra developed and wrote the proofs, including the deterministic parameter construction and complexity analysis, through an extended mathematical dialogue with the author. The author supplied the fixed-base test, conjectural framework, research notes, and references; proposed applying OpenAI’s recent analytic number-theoretic results to deterministic parameter selection; and directed the investigation of Jacobi sums, power nonresidues, composite degrees, multivariate quotient rings, and finite-field root counting.

References