Shor factoring with verified output and bounded outer retries

Inputs. A composite integer $N\ge 4$, encoded in binary, and a rational target failure probability $\delta =u\mathrm{/}v$ with coprime integers $0<u<v$. Use the modular-order-finding procedure on the earlier A page with its explicit reversible modular-multiplication circuit. Output is a verified proper divisor of $N$ or FAIL.

Arithmetic subroutines. For $c\ge 1$ and exponent $e\ge 0$, CappedPower(c,e) returns $\min \{c^e,N+1\}$: initialize $(r,d,k)=(1,c,e)$; while $k>0$, replace $r$ by $\min \{rd,N+1\}$ if $k$ is odd, then replace $k$ by $\lfloor k\mathrm{/}2\rfloor$ and, if the new $k>0$, replace $d$ by $\min \{d^2,N+1\}$. For any integer $c$ and exponent $e\ge 0$, ModPower(c,e) returns $c^e<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$: initialize $(r,d,k)=(1,c<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N,e)$; while $k>0$, replace $r$ by $rd<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$ if $k$ is odd, then replace $k$ by $\lfloor k\mathrm{/}2\rfloor$ and, if the new $k>0$, replace $d$ by $d^2<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$. In both routines, parity, quotient, product, comparison, and remainder operations are exact integer operations.

1. Set $n=\lceil {\log }_{2}N\rceil$. If $N$ is even, set $d=2$, check $1<d<N$ and $N<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>d=0$, and return $d$ if both checks pass.

2. For each integer exponent $e=2,3,\dots ,n$, initialize $L=2$ and $R=N$. While $L\le R$, set $b=\lfloor (L+R)\mathrm{/}2\rfloor$ and $y=\mathtt{\text{CappedPower}}(b,e)$. If $y<N$, set $L=b+1$. If $y>N$, set $R=b-1$. If $y=N$, verify $1<b<N$ and $N<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>b=0$; return $b$ if both checks pass, and otherwise set $R=b-1$. If the loop ends without a return, continue to the next exponent.

3. Initialize $T=1$, $A=5$, and $B=8$. While $Av>Bu$, replace $(T,A,B)$ by $(T+1,5A,8B)$. Continue to instruction 4 with this $T$; it is the least positive integer satisfying $5^{T}v\le 8^{T}u$, equivalently $T=\lceil \ln (1\mathrm{/}\delta )\mathrm{/}(-\ln (5\mathrm{/}8))\rceil$.

4. For attempts $i=1,\dots ,T$, obtain a fresh independent sample $a$ by running Exact uniform sampling from the nonzero residue representatives on $N$ with a fresh independent countable fair-bit tape. Compute $g=\gcd (a,N)$. If $1<g<N$ and $N<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>g=0$, return $g$. If $g\mathrm{\ne }1$, start the next attempt; the case $g=N$ is rejected as an invalid sample and also starts the next attempt.

5. When $g=1$, run modular order finding on $(N,a)$ with target parameter $b=2$, so its target failure is $2^{-2}=1\mathrm{/}4$. Use fresh measurement randomness independent of the sampler tape and all previous attempts. If it returns FAIL, start the next attempt. Otherwise let $q$ be its candidate. Reject the candidate unless $2\le q\le N$, $q$ is even, and $\mathtt{\text{ModPower}}(a,q)=1$. Set $z=\mathtt{\text{ModPower}}(a,q\mathrm{/}2)$, the standard representative of $a^{q\mathrm{/}2}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$. Compute $d_{-}=\gcd (z-1,N)$ and $d_{+}=\gcd (z+1,N)$. Return the first of these satisfying $1<d_{\pm }<N$ and $N<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>d_{\pm }=0$; if neither passes, start the next attempt.

6. If all $T$ attempts finish without returning a divisor, return FAIL.

The residue sampler's exact uniformity, almost-sure termination, and expected-bit bound are proved separately. The outer attempt count, root search, modular exponentiation, and divisor checks have the finite bounds stated above. Correctness, success probability, and costs are separate claims.

The odd-composite branch reaches order finding only after the gcd test establishes $\gcd (a,N)=1$, so the residue class of $a$ is a unit by For $n\ge 1$, $[a{]}_n$ is a unit if and only if $\gcd (a,n)=1$. A returned candidate period is rechecked even though the order-finding contract also verifies candidates. Its fair-bit tapes use countable choice and dependent choice through the sampler's countable product model; the number-theoretic and output-verification branches use finite arguments. Order-finding success and cost are separate claims.