Exact quantum factoring over a fixed finite gate set

Proof. Choose a common polynomial bound T on the denominator exponent, and compute A such that q=A/2^T. Apply T Hadamards to fresh zero bits to obtain a uniform label u\in\{0,\ldots,2^T-1\}. Reversibly compute the flag [u<A]. Keep u and all required work bits. Exactly A labels set the flag. Padding to the common T handles a denominator depending on the input label.□

Proof. In place of a basis measurement, copy its outcome by CNOT gates into fresh history bits. Retain this copy and thereafter use it only as a classical control. The branches indexed by different recorded histories remain orthogonal. Induction over the procedure shows that their squared norms and subsequent outcome distributions equal those in the measured procedure. Quantum work not measured in the original procedure remains quantum work; in particular, no label is copied before an intended interference computation.

Run the reversible classical controller for a fixed polynomial number of ticks, keeping its history and using a halted flag after termination. There is no need to list its possible histories. If a bounded-arity instruction selects registers by addresses, enumerate all tuples of addresses in the polynomial workspace. For each tuple, compute whether the controller selects it, apply the corresponding singly controlled primitive, and uncompute this test. The number of tuples is polynomial because the arity is fixed. A polynomial bound on ticks, workspace, and stored records therefore gives a polynomial circuit whose description can be generated in polynomial time. Reverse the gate list and invert each primitive to obtain the inverse.□

Proof. Prepare a b-qubit phase register in the state

This requires Hadamards on its bits, followed by a Z=S^2 phase on the most significant bit and an S phase on the next bit. For D\in\Z, let T_D denote the forward shift \ket y\mapsto\ket{y+D\bmod Q} on this register. We first verify that

Write D=qQ/4+s modulo Q, where 0\le q<4 and 0\le s<Q/4. Among the Q positions, a fraction 1-4s/Q crosses exactly q quarter-bins, and the remaining fraction 4s/Q crosses q+1. The corresponding products of the initial phase with the conjugate final phase are \mathrm i^{-q} and \mathrm i^{-q-1}, respectively. Their average is precisely (2) at D/Q. The sign is fixed by the use of a forward shift: a shift by Q/4 has overlap -\mathrm i.

Number input and output bits from the units bit: x=\sum_{i=0}^{b-1}2^ix_i and k=\sum_{j=0}^{b-1}2^jk_j. For j=0,\ldots,b-1, perform the following operations in order: apply a Hadamard to the physical bit that initially carried x_{b-1-j}, regard its new value as k_j, and, for every i<b-1-j, apply the shift

to the phase register. Both controls are available: k_j is the bit just produced, whereas x_i has not yet been overwritten. The logical output bits are thus in the reverse physical order from the input bits; a wire reversal, or ordinary SWAP gates, puts them in the conventional order.

For fixed input x and output k, each data bit has exactly its specified value before and after its single Hadamard. The product of the Hadamard matrix elements is Q^{-1/2}(-1)^h, and the total phase-register shift is D, where

All omitted terms in the product xk are accounted for by

Using (3) and g(z+1/2)=-g(z) gives the claimed matrix entry after projecting the phase register back onto \ket\chi:

To perform that test, undo the preparation of \ket\chi and designate the all-zero phase-register outcome as success. Its actual probability is retained; there is no instruction to enforce that outcome.

There are O(b^2) controlled shifts. Each is a reversible modular binary addition on b bits, with its scratch bits uncomputed afterwards, and therefore has polynomial cost in the stated finite gate set. All other operations also have polynomial cost.□

Proof. Compute the finite simple continued fraction of k/Q, and let p/v be its last convergent with denominator less than B. If all convergents have denominator less than B, use the terminal one. We have

Indeed, suppose p/v is not terminal. Let (p',v') be the preceding numerator–denominator pair, using the formal pair (1,0) when p/v is the first convergent. The remaining continued-fraction tail \theta gives

The next denominator is v c+v'\ge B, where c is the integer part of \theta. Consequently the error is 1/[v(v\theta+v')]\le1/[v(vc+v')]\le1/(vB). The determinant identity follows inductively from the convergent recurrence, which replaces each numerator–denominator pair by c times the latest pair plus the preceding pair. If the convergent is terminal, its error is zero.

Suppose k has a label (d,j). If j/d\ne p/v, integrality of the cross-product gives

For the strict inequality, note that 2Q>vB(B-1) because v<B and Q=B^{16}. This contradicts (5) and |k/Q-j/d|\le1/(2Q). Thus j/d=p/v. It remains only to check 0\le p<v<B and the exact rule (4); these checks accept precisely the valid labels. They also prove uniqueness. When k=0, the terminal convergent is 0/1, so the case d=1 is included. The Euclidean algorithm and all these checks use integers with O(n) bits and take polynomial bit time.□

Proof. Fix d,j, and abbreviate k=k(d,j) and \eta=k-jQ/d. For x\equiv t\pmod d, put u=jt\bmod d, represented in \{0,\ldots,d-1\}. Periodicity gives the exact identity

As x traverses the progression, this last argument moves a distance at most 1/2. Thus it meets only a bounded number of the quarter-integer breakpoints of g. Split the progression at those breakpoints by rational comparisons and integer division. On each resulting part, the real and imaginary coordinates are affine in the progression index, so their sums are obtained from the number of terms and the sum of consecutive integers. This computes P(d,j,t) with a bounded number of arithmetic operations on O(n)-bit integers and rationals. Its dyadic nature is also immediate from the original sum: each g(kx/Q) has real and imaginary denominators dividing Q, so the squared modulus after division by Q has denominator dividing Q^4.

Although each P(d,j,t) is efficiently computable, direct summation over t requires d evaluations, which need not be polynomial in n. To construct a majorant with an efficiently computable total, first define, for real 0\le u<d,

We first record two uniform estimates:

For the first estimate, let h=d/Q<1 and f(v)=g(u/d+\eta v). The function g has magnitude at most one and Lipschitz constant 4\sqrt2, so f has Lipschitz constant less than four. The progression points x/Q are the left endpoints of intervals of length h. Together these intervals start within h of zero and end between 1 and 1+h. Their total length is at most 1+h. The error of the left rectangle rule is at most 2h(1+h), and the two endpoint discrepancies contribute at most 2h. Consequently, writing

we have |A_t-I(u)|\le 6/Q\le8/Q. Since |A_t|\le 1/d+1/Q and |I(u)|\le1/d, this implies the first inequality in (11).

For the lower bound, replace g in (10) by e^{-2\pi i z}. The resulting integral has magnitude

where the quotient is interpreted as one at \eta=0. The inequality follows from concavity of sine on [0,\pi/2]. Linear interpolation on intervals of length 1/4 changes the exponential by at most

This interpolation bound follows by Taylor expansion at the interpolated point and linear averaging of the two endpoint remainders; it applies equally to complex-valued functions. Therefore

For completeness, \pi<2\sqrt3, obtained from \tan(\pi/6)>\pi/6, bounds the parenthesis below by 1/\sqrt3-3/8>1/8. The upper bound follows from |g|\le1.

It remains to construct a dyadic majorant whose sum is accessible. Let G be the continuous primitive of g satisfying G(0)=0. Its real and imaginary parts are quadratic polynomials with rational coefficients on each quarter interval. When \eta\ne0,

The two arguments range in [-1/2,3/2], so only a bounded number of pieces occur. Their boundaries in u arise when either argument is a quarter-integer. On each piece, I is a complex polynomial in u of degree at most two; hence J is a rational polynomial of degree at most four. If \eta=0, the identity I(u)=g(u/d)/d gives the same conclusion. All boundaries and coefficients have O(n) bits and can be computed with a bounded number of rational operations. In particular, \eta=(kd-jQ)/d, so every nonzero \eta has |\eta|\ge1/d; the division in (12) has no hidden precision cost.

On each piece write J(u)=\sum_{q=0}^4a_qu^q, allowing zero coefficients, and set D=QB^8. Replace a_q by \widetilde a_q=\lceil Da_q\rceil/D. Denote the resulting piecewise polynomial by \widetilde J, assigning boundary points consistently to one adjacent piece, and define

Because u\ge0, rounding each coefficient upward increases the value even when that coefficient is negative. Moreover,

Together with (11), this yields 32/Q\le U(d,j,jt\bmod d)-P(d,j,t)\le97/Q, proving (8). It also gives

where the last inequality uses d<B and Q=B^{16}.

Finally, intersect the bounded collection of rational piece intervals with the integers 0,\ldots,d-1, using floors and ceilings and assigning each boundary integer only once. Sum each polynomial by the integer power sums through degree four. These sums are computed, for example, recursively from

Here the zeroth power sum is the count M, with u^0=1 also at zero. These sums have O(n) bits for M\le B, and there are only a bounded number of pieces. This computes S(d,j) in polynomial time without enumerating the residues. Since D is a power of two, both U and S are dyadic with O(n)-bit representations. All operations used to compute them are rational arithmetic, integer division, and rounding.□

Completion of the proof of Proposition 3.1. For each reduced label, the natural scaling coefficient \lambda(d)/S(d,j) need not be dyadic. We round it downward and reserve the remaining mass for the third mode. Define

By (9) and \lambda(d)\le1/(1024d),

Both numbers are exactly computable dyadics of polynomial bit length.

Choose one of the following three modes with probabilities 1/2,1/4,1/4, respectively. In every mode, reject unless

Check the label conditions before evaluating any formula involving it. An invalid label or a failed retention test produces no candidate.

1. 1.

   Run the quantum experiment. Require its phase-register success, recover the reduced label (d,j) from the observed k, and retain the candidate d with probability c(d,j).

2. 2.

   Choose independent uniform n-bit labels d,j,t. Require also t<d, and retain d with probability

   2B^3\bigl(U(d,j,jt\bmod d)-P(d,j,t)\bigr)c(d,j). \tag{16}
3. 3.

   Choose independent uniform n-bit labels d,j, and retain d with probability

   4B^2\rho(d,j). \tag{17}

All retention probabilities are dyadic and belong to [0,1]. Nonnegativity follows from (8) and (15); the last two probabilities are at most

Each retention test can therefore be implemented exactly by comparing fresh fair bits with an integer numerator. The number of bits and all arithmetic and quantum costs are polynomial in n.

To compute the mass of the correct order, fix d=r and a reduced numerator j. By (7), Mode 1 contributes

Each triple in Mode 2 has probability B^{-3} conditional on choosing that mode. Thus Mode 2 contributes

Multiplication by j permutes the residues modulo d, so these two contributions sum to c(d,j)S(d,j). Mode 3 contributes \rho(d,j), making the total exactly \lambda(d). The bin labels are distinct by Lemma 3.3, and there are \varphi(r) reduced numerators. Hence

This includes r=1, whose sole reduced label is j=0.

Every returned candidate satisfies a^d\equiv1\pmod m, so it is a multiple of the true order r. At false labels no identity between the artificial quantity P(d,j,t) and a quantum probability was used. This proves all claims of Proposition 3.1.□

Proof. We construct the process and verify these properties in turn. Each transition uses fresh work registers and fresh randomness. Its classical output is copied to a history register before the controller uses it; earlier quantum work is retained as inactive workspace. Consequently, conditional on any recorded classical prefix, the next transition has exactly the distribution specified by its recorded classical inputs, even if earlier work registers remain entangled.

The information contained in \D. Suppose that a subfactor m is being split while factoring a node M. From \D we can factor m by division from the prime list for M. Moreover, \D supplies the factorization of p-1 for every odd prime p\mid m. Thus it supplies the factorization of

Here the formula follows by counting units modulo a prime power and using the Chinese remainder bijection; the latter follows from Bézout’s identity. The contribution from p=2 needs no child.

Given this factorization and a unit a modulo m, its order is computable exactly. Start with exponent v=\varphi(m). For each prime q in its known factorization, repeatedly replace v by v/q while q\mid v and a^{v/q}\equiv1\pmod m. The order divides \varphi(m) by the coset proof of Lagrange’s theorem. Throughout the procedure it divides v, and at termination no excess prime factor can remain. Hence the final v is the order, and the remaining prime exponents give its factorization. There are polynomially many modular powerings. The same procedure applies to each prime-power component of m. These are retrospective computations: they are used to evaluate recorded transitions once the data have been generated.

We shall use the elementary bound

Indeed, if p_1<\cdots<p_k are the distinct prime divisors of d, then k\le n and p_i\ge i+1, so the product formula gives \varphi(d)/d\ge\prod_{i=1}^k i/(i+1)=1/(k+1). The empty product covers d=1.

The controller and its two transitions. To factor a node, apply the deterministic primality test in Lemma A.1 to each current factor. A prime is recorded; an even composite can be split by 2; and a composite perfect power can be split by finding an integral root. Root searches for exponents at most n take polynomial time. Consequently the remaining case is an odd m having at least two distinct prime divisors. We use the following two kinds of transition for this case.

A list output consists of K fields of b_m=\lceil\log_2m\rceil bits, followed by zero padding to width W; an order output consists of one n-bit integer followed by zero padding to width W. A dummy output is the all-zero W-bit string. The controller rejects malformed padding, and every good-output predicate below requires a valid encoding.

First, a list transition generates K independent uniform b_m-bit integers. Entries outside [0,m) and nonunits are ignored. A list is good if some usable entry a has unequal values of

where \nu_2 denotes the exponent of 2 in a positive integer. We now compute its good probability without enumerating residues.

The nonzero elements of a prime field form a cyclic group. For completeness, let T be the least common multiple of their orders. Lagrange’s theorem gives T\mid p-1, while the root bound for X^T-1 gives p-1\le T. The exponent of a finite abelian group is attained: for each prime power dividing that exponent, take a suitable power of an element whose order contains that prime power, then multiply these elements of pairwise coprime orders. Thus there is an element of order T=p-1.

Write p-1=h2^\ell, with h odd. In this cyclic group the counts at levels 0,1,\ldots,\ell are h,h,2h,\ldots,2^{\ell-1}h. Reduction of units modulo p^e to units modulo p has an odd kernel of size p^{e-1}. The order of an element and the order of its reduction therefore have the same 2-adic level, and each residue has p^{e-1} lifts. The corresponding counts modulo p^e are

No level has more than half the units.

Let c_i(t) be these counts for the prime-power components of m, extended by zero outside their ranges. The Chinese remainder bijection makes the levels independent for a uniform unit. Since there are at least two components, the probability that all levels agree is at most 1/2: for the first two level laws q_1,q_2, \sum_t q_1(t)q_2(t)\le\max_t q_1(t)\le1/2. The number of favorable residues is therefore exactly

There are at most n components and n+1 levels, so this formula is polynomial-time computable from \D. By (20) and 2^{b_m}\le2m, the list’s exact good probability is

A canonical good list has first entry equal to the Chinese remainder residue that is 1 on the component corresponding to the smallest prime and -1 on all others, followed by zeros. Its first entry has levels 0 and 1.

Second, for every usable entry a, an order transition runs K independent order trials. It outputs the smallest returned candidate, or 0 if there was none. If r=\ord_m(a), goodness means that this output is r, which is also the canonical good output. By Proposition 3.1, every nonempty candidate is a positive multiple of r, and the probability of the candidate r in one trial is \varphi(r)\lambda(r), where \lambda(r)=2^{-\lceil\log_2r\rceil-10}. Consequently

The last bound follows from (20) and 2^{\lceil\log_2r\rceil}\le2r, also when r=1.

Equations (22) and (23) give exactly computable dyadics. Their denominator exponents are at most nK and (n+10)K, respectively. For either transition, the lower bound on the one-trial success parameter x gives

Thus (1-x)^K\le e^{-2n}<2^{-2n}, proving the required uniform bound on s. The good predicates, probabilities, and canonical outputs are all computable from \D and the classical inputs m or (m,a).

Why good transitions produce a split. For every positive even order output r', try \gcd(a^{r'/2}-1,m) and accept it only if it is a proper nontrivial divisor. If no entry produces a split, abort. If the list and its order transitions are good, choose an entry with unequal local levels and let r be its true order. By the Chinese remainder bijection,

The largest local 2-adic level is positive. The local orders at smaller levels divide r/2, whereas at a largest-level component a^{r/2} has order two. The only square roots of 1 modulo an odd prime power are 1 and -1: in (x-1)(x+1)\equiv0\pmod{p^e} the entire odd prime power divides one factor. Hence a^{r/2} equals 1 on the smaller-level components and -1 on the largest-level components. The gcd is a proper nontrivial divisor. This proves that all-good outputs prevent an abort at every split, regardless of how those outputs were obtained.

After completely factoring a node, the controller creates its specified children and factors them in a fixed order. Once all these tasks have finished, it fills unused transition slots with dummy transitions.

Size bounds and verification. The binary splitting tree for one node M has at most \log_2M leaves: all leaf labels are at least two and their product is M. A partial run has at most \log_2M split attempts as well, including a possible final failed attempt. At each auxiliary-tree descent,

Thus the total logarithmic size at any depth is at most \log_2N<n. In two successive descents M\to p-1\to q-1, the intermediate label is even and q>2 divides it, so q-1<(p-1)/2<M/2. There are therefore fewer than 2n+2 levels. Since every node label is at least two, each contributes at least one to the logarithmic size; the tree has at most (2n+2)n node occurrences. Summing the split-attempt bound over the same levels gives at most (2n+2)n split tasks. Each uses at most K+1 transitions, whence

All deterministic work and all K trials within an order transition also have polynomial bounds.

These bounds hold even for bad output sequences. Only genuine gcd splits are accepted, prime leaves are verified, and children are created only from the resulting actual prime factors. An abort only shortens the work. Fixed polynomial caps on work and storage can therefore be imposed without excluding any all-good evolution. Each node’s prime list has at most n entries of polynomial bit length, so the occurrence bound also bounds the storage for the complete data. A list has at most nK unpadded bits, and an order value, including zero, has n bits. Thus the specified encodings fit within W bits and give each canonical output a unique string. The controller depends only on these classical outputs, and internal quantum work can be retained without being treated as part of an output.

Finally, the complete data are polynomially verifiable. Require the root label to be N. Before arithmetic, reject node labels outside [2,B), proposed prime labels outside [2,M] at a node M, exponents outside [1,n], and lists or trees exceeding the preceding polynomial size caps. At a node M, require strictly increasing prime labels, check primality using Lemma A.1, and check the factorization’s product. Then require exactly the ordered children p-1 for the distinct odd primes in that list and apply the same checks recursively. Reject missing or extra children and malformed or oversized records; a partial product may be rejected as soon as it exceeds M. These guards make the verification polynomial even on arbitrary invalid records, and no true data violate them. Unique prime factorization implies that an accepted tree is exactly \D(N); only the operational split history may vary. The all-good splitting argument ensures that every all-good evolution supplies this complete tree. This proves the proposition.□

Proof. Since z/A\le1, we have 0\le C\le1. Downward rounding gives

The two passing masses are AC and

whose sum is z. Although z/A need not be dyadic, computing its scaled floor is an exact integer division. Every probability that is actually sampled is dyadic. The products, subtraction, and denominator exponents have polynomial size.□

Proof. Fix the true mathematical data \D(N) for the purpose of analysis only. Allocate fresh filter coins in advance, with a common polynomial bound on their lengths. Consider the event obtained by testing each slot immediately against these true data, using the same coins that the actual algorithm will use after completion. Declare this analytical event false on a run that aborts before all L slots are recorded. These hypothetical tests only mark an event on the same recorded runs; their outcomes do not alter the controller’s evolution.

Condition on a recorded controller prefix of fewer than L slots together with the coins used by its previous filters, all of which have passed. No later filter coins are exposed. Every output in this prefix is good; choosing canonical good outputs whenever another transition is requested gives an all-good evolution. Proposition 4.1 therefore ensures that the controller reaches the next real or dummy slot.

Its transition inputs are fixed. Its new ordinary transition uses fresh registers, so its good-output probability is s, even if unobserved old quantum work is entangled; this is the consequence of Lemma 2.2 explained in Section 2. The branch choice, uniform guess, and next filter coins are also fresh. Lemma 5.1 therefore gives conditional passing probability exactly z for this prefix. This statement holds separately for every passing prefix and for every dummy slot. Induction over the L slots gives probability z^L for the analytical event.

We must identify this event with the one the algorithm implements. Every analytical passing transition has a good output. Proposition 4.1 then guarantees completion of the full true data, without abort or truncation by a cap. Such a run passes the actual data verification, and its deferred thresholds and canonical outputs agree with those in the analytical event. Conversely, if an implemented run passes, its verified complete prime factorizations are precisely the true data, by unique factorization. Every deferred test is consequently the corresponding true-data test on the same output and the same coins. The two events coincide on each recorded run. In particular, the conditional calculation above never conditions on eventual completion, and the implementation never uses data it has not generated.

The retained records also justify the probability calculation in a unitary implementation. Every result used for later classical control has an immutable orthogonal history copy. Distinct histories cannot interfere during the preparation; internal interference within a quantum trial is preserved because its pre-interference labels are not copied. All filtering computations are classical controls and fresh-coin comparisons. Thus Lemma 2.2 preserves the event probability just established.

The underlying process has polynomial caps on every branch. The s values have O(nK) denominator bits, and the rounded filters have polynomial bit length. There are L of them, so evaluating all deferred tests and retaining their histories still has polynomial cost. The dyadic p_* has at most nL denominator bits and can be computed exactly by integer powering. Finally, Bernoulli’s inequality yields

At n=128 the subtracted term is 2^{-58}, and x^{10}2^{-x} decreases for real x\ge128, since its logarithmic derivative is 10/x-\log_e2<0.□

Proof. With probability 1/2, run Proposition 5.2 and retain its success with the further probability

With probability 1/2, guess a uniform J-bit string, require it to be the valid root factor list, and retain with probability

Since 1/2<p_*\le1, we have 0\le c_*\le1. Rounding gives

Thus both retentions are valid polynomial-bit dyadics. The first branch contributes p_*c_*/2, and the unique valid guess contributes

Their sum is exactly 1/4. Place the same fixed-encoding root factor list in the output register on either successful branch. All work and flags are retained when applying Lemma 2.2, which gives the unitary V_N.□

Proof of Theorem 1.1. Let \psi=V_N\ket{0}, let \Pi project onto flag 1, and put g_*=\Pi\psi. By Lemma 5.3, \|g_*\|^2=1/4. First apply the sign flip I-2\Pi, and then the reflection 2\ket{\psi}\bra{\psi}-I. Since

the resulting state is

It has norm one and lies entirely in the successful subspace. Every basis outcome in that subspace has the correct factor list, so measuring the output gives the factorization with certainty.

Both reflections are exact over our finite gates. The success sign is a bit test. For fixed classical input N, the other reflection is

where the middle test concerns all initially zero workspace, and the read-only input is held fixed. Its sign convention may differ by an irrelevant global minus sign from a sign flip on zero. Multi-control signs use the reversible gates and S^2 described in Section 2. A circuit for inputs of a fixed bit length performs these same operations controlled by the unchanged input bits, so its description remains polynomial-time uniform. Inverting V_N includes all of its work and history registers; none needs to be erased separately.

Each use of V_N or its inverse has polynomial size and workspace. Equation (28) is a single amplification step at the exactly known probability 1/4, the corresponding special case of amplitude amplification [4, Section 2]. No arbitrary-angle rotation or unbounded repetition is involved. This proves the asserted worst-case bound and exact output.□

Proof. We first describe the algorithm.

1. 1.

   Reject m if it is a perfect power b^e with integers b,e\ge2.

2. 2.

   Find a prime s\le n^8 such that

   \gcd(s,m)=1, \qquad \ord_s(m)>n^2. \tag{29}
3. 3.

   If m\le8s, decide primality by trial division and stop. Otherwise reject if any integer from 2 through 8s divides m.

4. 4.

   Accept if and only if all the congruences

   (X+a)^m\equiv X^m+a\pmod{m,\,X^s-1}, \qquad 1\le a\le8s, \tag{30}

   hold.

We prove that the search in the second step succeeds, that the algorithm is correct, and that its running time is polynomial.

Existence of s. Let R=2\lfloor n^8/2\rfloor and let P_R be the product of the primes at most R. The central binomial coefficient C=\binom{R}{R/2} satisfies C\ge2^R/(R+1). For every prime \ell, the factorial valuation formula gives

Each summand is zero or one, and it vanishes when \ell^j>R. Consequently, if \pi(R) denotes the number of primes at most R, then

Thus

For the last inequality, 8\log_2 n+1<n for n\ge128; the difference is positive at 128 and increasing thereafter. Since R\ge n^8-1 and R+1\le2n^8, the displayed quotient is larger than (n^8-1-n)/n, which is larger than n^6. On the other hand,

It follows from (31) that some prime s\le R divides neither m nor any m^j-1 with 1\le j\le n^2. This is precisely (29).

Correctness. Primes pass the perfect-power and trial-division checks. If m is prime, the binomial theorem in characteristic m gives (X+a)^m=X^m+a^m=X^m+a, so they also pass (30).

Suppose, conversely, that a composite m is accepted. It is not a perfect power, and every prime p dividing it satisfies p>8s. Choose one such p. In an algebraic extension of \mathbb F_p, choose a root w of 1+X+\cdots+X^{s-1}. Its value at 1 is s\ne0 in \mathbb F_p, so w\ne1. Since s is prime, w has multiplicative order exactly s.

For any product f of the tested linear factors X+a, reduction of (30) modulo p gives f(X)^m\equiv f(X^m)\pmod{X^s-1}. Frobenius gives the same identity with exponent p. These identities compose: substitution X\mapsto X^b preserves the ideal (X^s-1), so identities for exponents b,c imply the identity for bc. Hence, for all nonnegative integers u,v,

Let H be the subgroup of (\Z/s\Z)^\times generated by the residues of m and p, and put h=|H|. By (29),

The nonnegative powers m^u p^v already range over H, because inverses in a finite group are nonnegative powers. We now obtain incompatible lower and upper bounds on the number of values f(w). These bounds adapt the root-counting arguments in [1, Lemmas 4.7–4.8 and their footnotes], which credit the lower-bound argument to Lenstra and independently Macaj, and the upper-bound formulation to Kalai, Sahai, and Sudan.

For the lower bound, take all products of h-1 distinct factors from X+1,\ldots,X+8s. The factors are pairwise distinct over \mathbb F_p because p>8s, so different subsets give different monic polynomials. If two such polynomials f_1,f_2 had the same value at w, then (32) would give f_1(w^k)=f_2(w^k) for every k\bmod s\in H. This would give h distinct roots of the nonzero polynomial f_1-f_2, whose degree is at most h-1. Thus all these values are distinct, and their number is at least

Here \binom{M}{t}\ge(M/t)^t follows by comparing each factor (M-i)/(t-i) with M/t. No division by f(w) has been used. Indeed f(w)=0 is itself impossible, since (32) would give h roots of the nonzero polynomial f, of degree h-1.

For the upper bound, put q=\lfloor\sqrt h\rfloor. The (q+1)^2>h pairs 0\le u,v\le q give two distinct pairs for which the corresponding integers k_1=m^u p^v and k_2=m^{u'}p^{v'} agree modulo s. They are different as integers: since m is composite and not a perfect power, it has a prime divisor p'\ne p. Equality of k_1 and k_2 would force u=u' by taking p'-adic valuations, and then v=v'. Now w^{k_1}=w^{k_2}, so (32) makes every value counted in (33) a root of the nonzero polynomial T^{k_1}-T^{k_2}. Its degree is at most

But (33) is at least 8^{h-1}=2^{3h-3}>2^{2h}, since h>n^2\ge128^2. This contradiction proves correctness.

Running time. Every exponent in a representation m=b^e with b\ge2 satisfies e<n, so binary search for integer roots with exponents 2,\ldots,n implements the first step in polynomial time. The search for s uses trial division to recognize primes up to n^8, followed by gcd and successive modular powers to test (29). These operations are polynomial in n and do not use the primality test under construction. The trial divisions involving m are also bounded by a polynomial in n. Finally, elements of (\Z/m\Z)[X]/(X^s-1) are represented by s coefficients of at most n bits. Schoolbook cyclic multiplication and repeated squaring test each of the 8s congruences using polynomially many bit operations, since s\le n^8 and the exponent m has at most n bits. The prime factor p, the extension field, and the exponents in the root count are used only in the correctness proof and need not be computed. All loops have uniform polynomial bounds, completing the proof.□