\documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage{lmodern,microtype} \usepackage[margin=1in]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools,enumitem,booktabs,xcolor} \usepackage[colorlinks=true,linkcolor=blue!40!black,citecolor=blue!40!black,urlcolor=blue!40!black]{hyperref} \usepackage{xurl} \hypersetup{pdftitle={Deterministic Polynomial-Time Primality Testing with a Single Binomial Congruence},pdfauthor={Joseph M. Shunia},pdfsubject={Deterministic primality testing in cyclotomic and binomial quotient algebras}} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\F}{\mathbb F} \newcommand{\ord}{\operatorname{ord}} \newcommand{\softO}{\widetilde O} \newcommand{\A}{\mathcal A} \setlength{\emergencystretch}{2em} \setlist[enumerate]{itemsep=4pt,topsep=5pt} \title{Deterministic Polynomial-Time Primality Testing\\with a Single Binomial Congruence} \author{Joseph M. Shunia} \date{October 30, 2026} \begin{document} \maketitle \begin{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=(\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 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\theta<1$, a common zero-free boundary $\Re s>\theta$ for the relevant Dedekind zeta functions gives $L^{\max\{6,(1-\theta)^{-1}\}+o(1)}$. This bound reaches $L^{6+o(1)}$ at $\theta=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)$. \end{abstract} \section{Introduction} For a prime $n$, the identity \begin{equation}\label{eq:frobenius-intro} (1+X)^n=1+X^n \end{equation} 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 \begin{equation}\label{eq:rings-intro} C_n=(\Z/n\Z)[Y]/(\Phi_r(Y)),\qquad \A_n=C_n[X]/(X^r-b(Y)), \end{equation} 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 \[ (\Z/n\Z)[X,Y]/\bigl(\Phi_r(Y),X^r-b(Y)\bigr). \] 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 \begin{align} b(Y)^{(n^D-1)/r}&=Y &&\text{in } C_n,\label{eq:normalize}\\ b(Y)^n&=b(Y^n) &&\text{in } C_n,\label{eq:compat}\\ (1+X)^n&=1+X^n &&\text{in }\A_n.\label{eq:main} \end{align} The single binomial congruence is \eqref{eq:main}, evaluated in $\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}$ \cite[Theorem 1.2]{openai-artin}. Cureton and Thorner extended this approach to all number fields and obtained the following stronger result. \begin{theorem}[Cureton--Thorner {\cite[Theorem 1.1]{cureton-thorner}}] \label{thm:zero-free} For every number field $F$, its Dedekind zeta function satisfies \[ \zeta_F(s)\ne0\qquad \left(\Re s>\frac{31}{32},\ s\ne1\right). \] \end{theorem} This theorem has a published Lean formalization generated with AxiomProver \cite{axiom-lean}. 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~\ref{lem:explicit} separately makes the effective dependence on field degree and discriminant explicit. The main result uses Theorem~\ref{thm:zero-free} as its analytic input. Corollary~\ref{cor:analytic-complexity} 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. Section~\ref{sec:conditional-bounds} also identifies the $5/6$ threshold and the GRH endpoint. \begin{theorem}[Main result]\label{thm:main} There is a deterministic primality algorithm using \eqref{eq:normalize}--\eqref{eq:main} with total bit complexity \[ L^{32+o(1)},\qquad L=\lceil\log_2 n\rceil. \] Its parameters satisfy \[ D=L^{o(1)},\qquad r=L^{2+o(1)},\qquad \varphi(r)\le r. \] Verification after constructing $b$ costs $L^{6+o(1)}$ bit operations. \end{theorem} 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 \cite{bernstein} 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 \cite{aks}. Berrizbeitia and Cheng developed tests using binomial extensions and a small number of congruences \cite{berrizbeitia,cheng}. Bernstein gave an essentially quartic random-time primality-proving algorithm \cite{bernstein}; 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 \cite{lenstra-pomerance}. The present construction concerns the deterministic realization of the particular congruence \eqref{eq:main}, 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 $\softO$ suppresses factors polynomial in logarithms. All complexity statements count bit operations; $o(1)$ is as $L\to\infty$, with $\delta$ fixed. \section{An algebraic acceptance criterion}\label{sec: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 \begin{equation}\label{eq:degrees} \gcd(n,r)=\gcd(D,r)=1,\qquad q-1\mid D \quad\text{for every prime }q\mid r. \end{equation} In particular, $\lambda(r)\mid D$, so $n^D\equiv1\pmod r$ and the exponent in \eqref{eq:normalize} is integral. For odd $r$, define \begin{equation}\label{eq:B} h=\frac{r-1}{2},\qquad B_r=\sum_{j=0}^{h}\binom rj\binom hj\binom{r-j+h}{h}. \end{equation} Our exact size condition is \begin{equation}\label{eq:size} 3\bigl\lfloor\log_2 B_r\bigr\rfloor^2\ge D^2L^2r, \qquad L=\lceil\log_2 n\rceil. \end{equation} This condition uses integer arithmetic only: the logarithm floor is the bit length of $B_r$ minus one. \begin{lemma}[Cyclotomic coefficient ring]\label{lem:ring} Under \eqref{eq:degrees}, substitution $Y\mapsto Y^n$ defines an automorphism $\sigma$ of $C_n$ with $\sigma^D=1$. Each field quotient of $C_n$ is $\F_{p^e}$ for some prime $p\mid n$, where $e=\ord_r(p)\mid D$. In every such quotient the image of $Y$ has order exactly $r$. \end{lemma} \begin{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 $\F_p[X]$. The roots of $\Phi_r$ are precisely the primitive $r$th roots, whose Frobenius orbits have length $\ord_r(p)$. The quotient fields consequently have the stated degrees. Finally, $p^D\equiv1\pmod r$ implies $e\mid D$. \end{proof} \begin{lemma}[Iteration of the main congruence]\label{lem:iteration} If \eqref{eq:compat} and \eqref{eq:main} hold, then \[ (1+X)^{n^j}=1+X^{n^j}\quad\text{in }\A_n \qquad(j\ge0). \] \end{lemma} \begin{proof} Equation \eqref{eq:compat} gives $\sigma^i(b)=b^{n^i}$ by induction. Put $F(X)=(1+X)^n-1-X^n$. Equation \eqref{eq:main} 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 \[ X^r-b\mid X^{rn^i}-b^{n^i} \] 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. \end{proof} \begin{theorem}[Acceptance criterion]\label{thm:criterion} Suppose \eqref{eq:degrees} and \eqref{eq:size} hold. If \eqref{eq:normalize}--\eqref{eq:main} hold, then $n$ is a prime power. If $n$ is not a nontrivial perfect power, it is prime. \end{theorem} \begin{proof} Put $N=n^D$. The element $Y$ is a unit, so \eqref{eq:normalize} makes $b$ a unit. Suppose for a contradiction that $n$ has at least two distinct prime divisors. Choose a field quotient $k=\F_{p^e}$ of $C_n$ as in Lemma~\ref{lem:ring}, 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~\ref{lem:iteration} imply \[ \alpha^N=Y\alpha,\qquad u_i:=1+Y^i\alpha,\qquad u_i^N=u_{i+1}\quad(i\bmod r). \] 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 \cite[Section 3]{bernstein}. 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 rj$ ways, their absolute values in $\binom hj$ 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^i Z$, whose constant terms are all $1$, makes the original exponent vectors equal. Hence \begin{equation}\label{eq:lower-group} |G|\ge B_r. \end{equation} 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 \begin{equation}\label{eq:rotations} u_i^P=u_{i+t},\qquad u_i^H=u_{i+1-t}. \end{equation} Consider the lattice \[ \Lambda=\{(a,c)\in\Z^2:(1-t)a+tc\equiv0\pmod r\}. \] It has determinant $r$, because $1-t$ and $t$ generate the unit ideal in $\Z/r\Z$. The symmetric convex hexagon \[ \max\{|a\log H|,|c\log P|,|a\log H+c\log P|\} \le \sqrt{r/3}\log N \] has area \[ \frac{r(\log N)^2}{\log H\log P}\ge4r, \] 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 \eqref{eq:rotations} and the lattice relation give $g^U=g^V$ for every $g\in G$, and \[ \max(U,V)\le N^{\sqrt{r/3}}. \] 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 \[ |G|\le |U-V|0$, \[ r>(c_0+\epsilon)D^2L^2,\qquad c_0=\frac1{3\kappa^2}=0.051540616989\ldots, \] implies \eqref{eq:size} for sufficiently large $r$. A simpler sufficient condition valid for odd $r\ge7$ is $r\ge D^2L^2$. \end{proposition} \begin{proof} In \eqref{eq:B}, retain the term with $j=\lfloor(1-1/\sqrt2)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=\sqrt2-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 \[ B_r t^{2h}\le \left(1+\frac{2t}{1-t}\right)^r=t^{-r}. \] Since $2h=r-1$, this has the asserted exponential rate. The asymptotic threshold follows on substituting this estimate in \eqref{eq:size}. 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. \end{proof} 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 \cite[Theorem 3]{apr}, also used by Bernstein \cite{bernstein}. There is an absolute constant $C$ such that, for every sufficiently large $H$, some positive integer $D$ satisfies \begin{equation}\label{eq:OP} D\le\exp(C\log\log H\log\log\log H),\qquad \prod_{\substack{q-1\mid D\\q\text{ prime}}}q\ge H. \end{equation} \begin{proposition}\label{prop:degrees} There is a deterministic search for $D$ and odd squarefree $r>2$ satisfying $\gcd(D,r)=1$, $q-1\mid D$ for every prime $q\mid r$, and \eqref{eq:size}, with \begin{equation}\label{eq:parameter-sizes} D=L^{o(1)},\qquad r=L^{2+o(1)},\qquad q\le D+1=L^{o(1)}\quad(q\mid r). \end{equation} Its cost is at most $L^{4+o(1)}$ bit operations. \end{proposition} \begin{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 \eqref{eq:size} after each prefix whose product exceeds $2$. If all primes are exhausted without success, continue to the next $D$. To bound the search, apply \eqref{eq:OP} 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 \eqref{eq:OP} would contain only the prime $2$. For even $D$, excluding $q\mid D$ also excludes $2$. Proposition~\ref{prop:count} now guarantees success. For each fixed smaller $L$, applying \eqref{eq:OP} with $H$ sufficiently large gives the same termination argument. At the first successful prefix the product obeys \[ r\le(D+1)\max\{6,D^2L^2\}=L^{2+o(1)}. \] Conversely, Proposition~\ref{prop:count}'s upper estimate and \eqref{eq:size} 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 $\softO(r^2)$ bit operations: there are $O(r)$ terms, each with $O(r)$ bits. The $L^{o(1)}$ trials fit the claimed bound. \end{proof} 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. \section{A uniform auxiliary-prime bound}\label{sec:analytic} 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 Section~\ref{sec:coefficient}. We prove its existence for prime inputs by applying Theorem~\ref{thm:zero-free} to Kummer extensions of degree $q$. The following smoothed estimate makes the dependence on the number field explicit. \begin{lemma}[Smoothed prime-ideal estimate]\label{lem:explicit} Fix $0<\delta\le1/2$ and a nonzero nonnegative smooth function $w$ supported in $(1,2)$. Let $F$ be a number field of degree $d_F$ and absolute discriminant $\Delta_F$, and suppose its Dedekind zeta function has no zeros in $\Re s>1-\delta$. Put \[ \Psi_F(x)=\sum_{\mathfrak p}\sum_{a\ge1} \log N\mathfrak p\;w((N\mathfrak p)^a/x). \] Then, uniformly in $F$ and $x\ge2$, \begin{equation}\label{eq:explicit} \Psi_F(x)=x\widehat w(1) +O_w\bigl(x^{1-\delta}(\log\Delta_F+d_F)\bigr), \qquad \widehat w(s)=\int_0^\infty w(u)u^{s-1}\,du. \end{equation} The implied constant is effective. \end{lemma} \begin{proof} This is the smoothed explicit-formula calculation in \cite[Section 9.2, especially (9.9)]{openai-artin}; 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 \[ \Psi_F(x)=x\widehat w(1) -\sum_\rho x^\rho\widehat w(\rho) -(r_1+r_2-1)\widehat w(0) +O_w\bigl(x^{-1/2}(\log\Delta_F+d_F)\bigr), \] 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$. \end{proof} \begin{lemma}[Auxiliary prime for one prime degree]\label{lem:aux} Fix $0<\delta<1/2$, and suppose that for every number field $F$, $\zeta_F(s)$ has no zeros in $\Re s>1-\delta$. There is an effective constant $C_\delta$ such that, for every prime $n>3$ and every odd prime $q\ne n$, there is a prime $\ell$ satisfying \begin{gather} \ell\le C_\delta\bigl(q(L+\log q+2)\bigr)^{1/\delta}, \label{eq:aux-bound}\\ \ell\equiv1\pmod{12q},\qquad \ell\nmid n,\qquad n^{(\ell-1)/q}\not\equiv1\pmod\ell. \label{eq:aux-properties} \end{gather} \end{lemma} \begin{proof} Set $K=\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~\ref{thm:zero-free} supplies this hypothesis with $\delta=1/32$. The cyclotomic discriminant bound and the discriminant of $X^q-n$ give \begin{align*} [K:\Q]&=O(q),& \log\Delta_K&=O(q\log q),\\ [M:\Q]&=O(q^2),& \log\Delta_M&=O(q^2(L+\log q)). \end{align*} More explicitly, the relative discriminant divides $(q^q n^{q-1})\mathcal O_K$, and the discriminant tower formula gives the second bound. Lemma~\ref{lem:explicit} therefore yields \begin{equation}\label{eq:difference} \Psi_K(x)-\frac1q\Psi_M(x) =\left(1-\frac1q\right)x\widehat w(1) +O_w\bigl(q(L+\log q+2)x^{1-\delta}\bigr). \end{equation} 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 $\F_\ell^\times$. This is exactly the last condition in \eqref{eq:aux-properties}. 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 \eqref{eq:difference}. 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:\Q]+[M:\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\bigl(q(L+\log q+2)\bigr)^{1/\delta}$. For an effectively large constant $T_\delta$, the error in \eqref{eq:difference} 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. \end{proof} All primes $q\mid r$ are at most $D+1$. Hence a common search bound, increased by rounding if needed, is \begin{equation}\label{eq:search-bound} B=\left\lceil C_\delta \bigl((D+1)(L+\lceil\log_2(D+1)\rceil+3)\bigr)^{1/\delta} \right\rceil=L^{1/\delta+o(1)}=L^{32+o(1)}. \end{equation} For the search itself it suffices to test primes $\ell\equiv1\pmod q$; Lemma~\ref{lem:aux} supplies a prime even in the smaller progression. Only prime-input existence is needed. If a search fails within the bound, the algorithm rejects. \section{Constructing the normalized coefficient}\label{sec:coefficient} \subsection{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 \[ t_q=n^{(\ell_q-1)/q}\bmod\ell_q. \] Its order in $\F_{\ell_q}^\times$ is exactly $q$. For $u\ne0$ define $j_q(u)\in\{0,\ldots,q-1\}$ by \[ u^{(\ell_q-1)/q}=t_q^{j_q(u)}\pmod{\ell_q}. \] This is a multiplicative-group homomorphism to $\Z/q\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 \begin{equation}\label{eq:sq} s_q\equiv-\bigl(D(r/q)\bigr)^{-1}\pmod q. \end{equation} The inverse exists by \eqref{eq:degrees} and squarefreeness. In $R_q=(\Z/n\Z)[Z]/(\Phi_q(Z))$, define the order-$q$ character \begin{equation}\label{eq:chi} \chi_q(u)=Z^{s_qj_q(u)}\quad(u\ne0),\qquad \chi_q(0)=0. \end{equation} 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$. \subsection{Jacobi sums and a binary recurrence} For positive integers $a,c$, set \[ J(\chi^a,\chi^c)= \sum_{u\in\F_\ell}\chi(u)^a\chi(1-u)^c. \] 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 \begin{equation}\label{eq:beta} \beta_q(Z)=\ell_q\prod_{j=1}^{q-2}J(\chi_q,\chi_q^j) \quad\text{in }R_q. \end{equation} \begin{lemma}\label{lem:jacobi} The element $\beta_q$ is the $q$th power of its Gauss sum in a cyclotomic extension of $R_q$. It can be computed in $R_q$ using only $O(\log q)$ Jacobi sums, without constructing that extension. \end{lemma} \begin{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 \begin{align} \tau_a\tau_c&=J(\chi^a,\chi^c)\tau_{a+c} &&(a,c,a+c\not\equiv0\pmod q),\label{eq:gauss-jacobi}\\ \tau_1\tau_{q-1}&=\ell.\label{eq:gauss-unit} \end{align} These follow by grouping the two summation indices according to their sum; the zero-sum terms vanish in \eqref{eq:gauss-jacobi} because the product character is nontrivial. They are identities in integral cyclotomic rings and remain valid after reduction modulo $n$; see also \cite[Theorem 2.4]{conrad}. Iteration gives $\tau_1^q=\beta_q$. For a shorter computation, maintain $a