Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Shor’s Factoring Algorithm

1 · Prerequisites

2 · Summary

This page gives a bounded-error factoring procedure for a promised composite integer $N \geq 4$ . It returns $2$ immediately for even inputs. For odd inputs, it searches for exact perfect powers by integer roots and returns a proper factor when it finds one. In the remaining odd-composite case, it samples uniformly from $1, \dots, N - 1$ by exact rejection sampling. A nonunit sample yields its gcd factor immediately; a unit is passed to the order-finding procedure of quantum-order-finding-and-rational-reconstruction with internal failure target $1 / 4$ .

Every proposed period is checked directly: it must lie between $2$ and $N$ , be even, and satisfy $a^{q} \equiv 1 (m o d N)$ . The reduction then computes $z = a^{q / 2} m o d N$ and tests $\gcd (z - 1, N)$ and $\gcd (z + 1, N)$ . It returns only a divisor checked to lie strictly between $1$ and $N$ . Minimality of a candidate period is not required for output correctness; a nonminimal candidate can only miss a factor and cause a retry.

For a true order, the CRT proof identifies success through the two-adic valuations of the local prime-power orders. Each possible local valuation has probability at most $1 / 2$ ; with $k$ distinct prime factors, the probability that all valuations agree is at most $2^{- (k - 1)}$ . Thus the true-order reduction succeeds with probability at least $1 / 2$ on every odd composite that remains after perfect-power preprocessing. The order finder is exact with probability at least $3 / 4$ for each fixed unit, so each outer attempt succeeds with probability at least $3 / 8$ . With $T = \min {t \geq 1 : 5^{t} v \leq 8^{t} u} = ⌈ \frac{\ln (1 / δ)}{- \ln (5 / 8)} ⌉$ for $δ = u / v$ , the total failure probability is at most $(5 / 8)^{T} \leq δ$ .

The random-bit sampler uses countable choice and dependent choice only to supply countably many independent fair bits; the CRT and number-theoretic success proofs use finite products and finite choices. Under supplied explicit reversible arithmetic and an ideal exact-angle QFT, the stated gate, multiplier-call and expected arithmetic/post-processing bit-operation bounds are kept separate. No circuit-description generation-time, finite-alphabet or uniform-family bound is asserted. The bare controlled-unitary query branch costs $O (n T (Q - 1))$ queries and carries no polynomial query claim.

3 · Logical flowchart

4 · Definitions, theorems and proofs

AlgorithmAlgorithm: AI-adaptedProof: Not applicableOpen item page →

Exact uniform sampling from the nonzero residue representatives

Definition

Input. An integer $N \geq 3$ . The random tape is a countable sequence of independent bits, each taking $0$ and $1$ with probability $1 / 2$ . Its countable product law is supplied by Assuming countable and dependent choice, countable products of arbitrary probability spaces under countable choice and dependent choice (The Axiom of Countable Choice ( ${A C}_{ω}$ ), The axiom of dependent choice: a relation in which every element is related to something admits an $N$ -indexed chain).

Set $M = N - 1$ and let $h$ be the binary length of $M - 1$ , equivalently the least integer with $M \leq 2^{h}$ . For each block, read its bits in order as $β_{0}, \dots, β_{h - 1}$ , with the first bit most significant, and set $b = \sum_{j = 0}^{h - 1} 2^{h - 1 - j} β_{j} \in {0, \dots, 2^{h} - 1}$ . If $b \geq M$ , discard this block and read the next $h$ bits. Otherwise output $a = b + 1$ and halt.

Whenever it halts, the procedure returns an element of ${1, \dots, N - 1}$ because an accepted block has $0 \leq b < M = N - 1$ and the output is $b + 1$ .

LemmaStatement: AI-adaptedProof: AI-generatedOpen item page →

Mixed CRT signs yield proper gcd factors

Statement

Let $N = \prod_{i < k} p_{i}^{e_{i}}$ , where $k \geq 1$ , the $p_{i}$ are distinct odd primes, and every $e_{i} \geq 1$ . If $z^{2} \equiv 1 (m o d N)$ but $z \equiv̸ 1, - 1 (m o d N)$ , then both $\gcd (z - 1, N)$ and $\gcd (z + 1, N)$ are proper nontrivial divisors of $N$ . When $k = 1$ , the hypotheses cannot hold, because the proof below shows the only roots are the two global signs.

Facts & Assumptions

Given: The stated factorization of odd $N$ , an integer $z$ with $z^{2} \equiv 1 (m o d N)$ , and $z \equiv̸ \pm 1 (m o d N)$ .

[F1]

The Chinese remainder map is a bijection preserving multiplication, and it restricts to the product isomorphism of the corresponding unit groups for pairwise-coprime moduli (Chinese remainder theorem for a finite pairwise-coprime list: simultaneous residues determine one class modulo the product, and the resulting bijection preserves addition and multiplication, For pairwise coprime positive moduli, the Chinese remainder bijection restricts to an isomorphism of unit groups).

[F2]

For odd prime $p$ and $e \geq 1$ , $(Z / p^{e})^{\times}$ is cyclic of even order $p^{e - 1} (p - 1)$ (For every odd prime $p$ and $k \geq 1$ , $(Z / p^{k} Z)^{\times}$ is cyclic of order $p^{k - 1} (p - 1)$ ).

[F3]

For a generator $g$ of a cyclic group of order $M$ , $g^{t} = 1$ exactly when $M ∣ t$ (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[F4]

For a nonzero pair, gcd is a common divisor and is greatest in the usual order (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ); divisibility is transitive (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[F5]

Every odd prime is at least $3$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ , The integers form a totally ordered ring). If $d ∣ a$ and $a \neq 0$ , then $d \leq ∣ a ∣$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ).

[F6]

Congruence classes multiply by multiplying representatives, and equal classes are equivalent to congruence (The congruence class $[a]_{n}$ and the quotient set $Z / n$ , For every natural $n$ , $(Z / n, +)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold).

Proof

1.1givenF1F2F3F5F6choosealgebra

By [F1], $z$ has components $z_{i} = [z]_{p_{i}^{e_{i}}}$ . Each satisfies $z_{i}^{2} = 1$ , hence is a unit. Choose a generator $g_{i}$ of its cyclic unit group of even order $M_{i}$ by [F2], and write $z_{i} = g_{i}^{t_{i}}$ . By [F3], $z_{i}^{2} = 1$ exactly when $M_{i} ∣ 2 t_{i}$ . Among residues $t_{i}$ modulo even $M_{i}$ , this gives only $t_{i} = 0$ or $t_{i} = M_{i} / 2$ , so $z_{i}$ is one of the two roots $1, - 1$ : the second is $- 1$ because $- 1$ is a root and it is distinct from $1$ modulo $p_{i}^{e_{i}} > 2$ (otherwise $p_{i}^{e_{i}} ∣ 2$ , contrary to [F5]). To see the two exponent classes explicitly, write $M_{i} = 2 s_{i}$ ; $M_{i} ∣ 2 t_{i}$ is equivalent to $s_{i} ∣ t_{i}$ , which has the two residue classes $0, s_{i}$ modulo $2 s_{i}$ .

2.1givenstep 1.1F1choose

The signs cannot all be $+ 1$ , since CRT injectivity would then give $z \equiv 1 (m o d N)$ , and they cannot all be $- 1$ , since it would give $z \equiv - 1 (m o d N)$ . Choose indices $i_{+}$ and $i_{-}$ with signs $+ 1$ and $- 1$ , respectively. This also shows that when $k = 1$ the hypotheses are impossible.

3.1givenstep 2.1F4F5F6algebra

Since $p_{i_{+}}^{e_{i_{+}}} ∣ z - 1$ and $p_{i_{+}}^{e_{i_{+}}} ∣ N$ , it is a common divisor, so $\gcd (z - 1, N) \geq p_{i_{+}}^{e_{i_{+}}} > 1$ . Since $z \equiv - 1 (m o d p_{i_{-}}^{e_{i_{-}}})$ , that prime power divides $z + 1$ ; it cannot divide $z - 1$ because then it would divide $2 = (z + 1) - (z - 1)$ , whereas $p_{i_{-}}^{e_{i_{-}}} > 2$ . Thus $N ∤ z - 1$ and $\gcd (z - 1, N) < N$ .

4.1step 3.1step 2.1F4∎

Interchanging the two signs in step 3.1 gives $1 < \gcd (z + 1, N) < N$ . Hence both gcds are proper nontrivial divisors.

LemmaStatement: AI-adaptedProof: AI-generatedOpen item page →

Half an even order gives a square root of one

Statement

Let $N \geq 2$ , let $x$ be a unit modulo $N$ , and let $q \geq 2$ be an even integer with $x^{q} \equiv 1 (m o d N)$ . Then $z = x^{q / 2} m o d N$ satisfies $z^{2} \equiv 1 (m o d N)$ . If $q = {ord}_{N} (x)$ , then additionally $z \equiv̸ 1 (m o d N)$ .

Facts & Assumptions

Given: $N \geq 2$ , an integer $x$ with $[x]_{N} \in (Z / N)^{\times}$ , an even integer $q \geq 2$ with $x^{q} \equiv 1 (m o d N)$ , and $z = [x^{q / 2}]_{N}$ . Here ${ord}_{N} (x)$ means the order of $[x]_{N}$ in the unit group.

[F1]

Multiplication makes $(Z / N)^{\times}$ a group, and congruence classes multiply by multiplying representatives (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ , The congruence class $[a]_{n}$ and the quotient set $Z / n$ , For every natural $n$ , $(Z / n, +)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold).

[F2]

For an element of finite order $r$ , $x^{t} = 1$ exactly when $r ∣ t$ (The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity, If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

Proof

1.1givenF1algebra

Write $q = 2 h$ with $h = q / 2 \geq 1$ . Then $z^{2} = [x^{h}]_{N} [x^{h}]_{N} = [x^{2 h}]_{N} = [x^{q}]_{N} = [1]_{N}$ , so $z$ is a square root of one.

2.1givenF1F2step 1.1algebra

If $q = {ord}_{N} (x)$ and $z = [1]_{N}$ , then $[x]_{N}^{h} = [1]_{N}$ in the unit group. By [F2], $q ∣ h$ , which is impossible because $0 < h < q$ . Thus $z \neq [1]_{N}$ .

3.1step 1.1step 2.1∎

The square relation holds for every accepted even exponent, and step 2.1 supplies the additional nonidentity conclusion when it is the true order.

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Two-adic order distribution in odd prime-power unit groups

Statement

Let $p$ be an odd prime and $e \geq 1$ . If $A$ is uniform in $(Z / p^{e})^{\times}$ , then for every possible integer $j$ ,

$P (v_{2} ({ord}_{p^{e}} (A)) = j) \leq \frac{1}{2} .$

Here $v_{2} (r)$ is the greatest $s \in N$ such that $2^{s} ∣ r$ , for the positive integer order $r$ .

Facts & Assumptions

Given: An odd prime $p$ , an integer $e \geq 1$ , and the uniform finite probability law on $(Z / p^{e})^{\times}$ .

[F1]

The unit group is cyclic of order $M = p^{e - 1} (p - 1)$ (For every odd prime $p$ and $k \geq 1$ , $(Z / p^{k} Z)^{\times}$ is cyclic of order $p^{k - 1} (p - 1)$ , The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[F2]

For a finite-order group element, its powers equal the identity exactly at multiples of its order (The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity, Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ , If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[F3]

For a positive integer $r$ , $v_{2} (r)$ is the greatest $s$ with $2^{s} ∣ r$ (The $p$ -adic valuation $v_{p} (a)$ of a nonzero integer: the greatest $k \in N$ with $p^{k} ∣ a$ , with prime $2$ ).

[F4]

A finite uniform probability space assigns each outcome equal weight (Finite probability spaces, outcome weights, events, and event probabilities).

[F5]

The gcd is a greatest common divisor in the divisibility order and $\gcd (M, 0) = M$ for $M > 0$ (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , $\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$ ); Bézout's identity characterizes coprimality, and if $c, d$ are coprime and $c ∣ d x$ , then $c ∣ x$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ , Coprime integers: $\gcd (a, b) = 1$ , $a$ and $b$ are coprime if and only if $a x + b y = 1$ for some integers $x, y$ ; and in that case the only common divisors of $a$ and $b$ are $1$ and $- 1$ , If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ , Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution).

[F6]

Integer multiplication is associative and cancellation by a nonzero factor is valid (The integers form a commutative ring, The integers have no zero divisors; multiplicative cancellation).

Proof

1.1givenF1F2choose

Since $p$ is odd, $M = p^{e - 1} (p - 1)$ is even; write $M = 2^{s} u$ with $s \geq 1$ and $u$ odd. Choose a generator $g$ by [F1]. The map $t \mapsto g^{t}$ for $0 \leq t < M$ is a bijection onto the unit group, by the order statement in [F2], so a uniform unit corresponds to a uniform such exponent $t$ .

1.2givenF2F5F6algebra

Put $d = \gcd (M, t)$ . For $t > 0$ , write $M = d M_{0}$ and $t = d t_{0}$ . Bézout's identity for $M, t$ divides through by $d$ to give $M_{0} x + t_{0} y = 1$ , so $M_{0}, t_{0}$ are coprime by [F5]. For every $h \geq 1$ , [F2] gives $(g^{t})^{h} = 1$ exactly when $M ∣ t h$ , equivalently $M_{0} ∣ t_{0} h$ ; [F5] makes this equivalent to $M_{0} ∣ h$ . Hence the least such $h$ is $M_{0} = M / d$ . If $t = 0$ , then $d = M$ and $g^{t} = 1$ has order $1 = M / d$ .

2.1step 1.1step 1.2F3F4F5algebra

The exponent of $2$ in $d = \gcd (M, t)$ is $s$ exactly when $2^{s} ∣ t$ : if $2^{s} ∣ t$ , then $2^{s}$ is a common divisor and hence divides $d$ ; if $2^{s}$ divides $d$ , it divides $t$ . Since $2^{s}$ is the full power of $2$ dividing $M$ , this is equivalent to $v_{2} (M / d) = 0$ . There are $M / 2^{s} = u$ such residues among $0, \dots, M - 1$ , so this probability is $u / M = 2^{- s} \leq 1 / 2$ .

3.1step 1.1step 1.2F3F4F5algebra

For $1 \leq j \leq s$ , $v_{2} (M / d) = j$ exactly when the exponent of $2$ in $d$ is $s - j$ . As in step 2.1, this is exactly when $2^{s - j} ∣ t$ and $2^{s - j + 1} ∤ t$ . The number of such residues is $\frac{M}{2^{s - j}} - \frac{M}{2^{s - j + 1}} = 2^{j - 1} u,$ so their probability is $2^{j - 1} u / M = 2^{j - s - 1} \leq 1 / 2$ . No other valuation occurs because $M / d$ divides $M$ .

4.1step 2.1step 3.1∎

The cases $j = 0$ and $1 \leq j \leq s$ exhaust all possible valuations, and each has probability at most $1 / 2$ by steps 2.1 and 3.1.

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Random residue gcd branch for factoring

Statement

Let $N \geq 2$ and choose $a$ uniformly from the integers $1, \dots, N - 1$ . If $\gcd (a, N) > 1$ , then $\gcd (a, N)$ is a proper factor of $N$ . Conditional on $\gcd (a, N) = 1$ , the residue class $[a]_{N}$ is uniformly distributed in the unit group $(Z / N)^{\times}$ .

Facts & Assumptions

Given: An integer $N \geq 2$ and the uniform finite sample space $Ω_{N} = {1, \dots, N - 1}$ .

[F1]

Each residue class modulo $N$ has a unique standard representative in ${0, \dots, N - 1}$ (For $n \geq 1$ , every class in $Z / n$ has one representative $r$ with $0 \leq r < n$ , so $∣ Z / n ∣ = n$ ; while $Z / 0$ is in bijection with $Z$ , The congruence class $[a]_{n}$ and the quotient set $Z / n$ ).

[F2]

A residue $[a]_{N}$ is a unit exactly when $\gcd (a, N) = 1$ (For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ , The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ ).

[F3]

In a finite uniform probability space, each outcome has equal weight; event probability is the sum of those weights (Finite probability spaces, outcome weights, events, and event probabilities), and $P (A ∣ B) = P (A \cap B) / P (B)$ when $P (B) > 0$ (Conditional probability $P (A ∣ B)$ for $P (B) > 0$ ).

[F4]

The gcd is a positive common divisor and is greatest in the usual order (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ ); $\gcd (0, N) = N$ for $N \geq 1$ ( $\gcd$ is symmetric and unchanged by signs: $\gcd (a, b) = \gcd (b, a) = \gcd (∣ a ∣, ∣ b ∣)$ ; moreover $\gcd (a, 0) = ∣ a ∣$ , $\gcd (a, 1) = 1$ , $\gcd (a, a) = ∣ a ∣$ , and $\gcd (a, b) \geq 1$ unless $a = b = 0$ ).

[F5]

If $d ∣ a$ and $a \neq 0$ , then $∣ d ∣ \leq ∣ a ∣$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ).

Proof

1.1givenF4F5algebra

If $g = \gcd (a, N) > 1$ , then $g ∣ a$ and $g ∣ N$ by [F4]. Since $g$ is positive and divides the nonzero $a$ , [F5] gives $g \leq a < N$ ; hence $1 < g < N$ and $g$ is a proper factor.

1.2givenF1F2F4choose

The event $U = {a \in Ω_{N} : \gcd (a, N) = 1}$ is nonempty because $a = 1$ belongs to it. By [F1] and [F2], the map $a \mapsto [a]_{N}$ is a bijection from $U$ to $(Z / N)^{\times}$ : every unit has its unique standard representative, and the zero class is not a unit because [F2] and [F4] give $\gcd (0, N) = N \neq 1$ .

2.1step 1.2F3algebra

Every $a \in U$ has probability $1 / (N - 1)$ , so $P (U) = ∣ U ∣ / (N - 1) > 0$ . For any fixed unit representative $a \in U$ , its conditional probability is $(1 / (N - 1)) / P (U) = 1 / ∣ U ∣$ . By [F2], this is the uniform law on the unit group.

3.1step 1.1step 2.1∎

Step 1.1 proves the immediate proper-factor branch, and step 2.1 proves conditional uniformity of the unit branch.

TheoremStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Classical randomized order-to-factor success bound

Statement

Let $N$ be an odd composite that is not a perfect power, and write its prime-power factorization $N = \prod_{i < k} p_{i}^{e_{i}},$ where the $p_{i}$ are distinct odd primes, $e_{i} \geq 1$ , and $k$ is their number. Choose $a$ uniformly from $(Z / N)^{\times}$ and let $r = {ord}_{N} (a)$ . The true-order reduction sets $z = a^{r / 2} m o d N$ when $r$ is even and succeeds when $r$ is even and $z \equiv̸ \pm 1 (m o d N)$ ; on that event both gcds give proper factors. This event has probability at least $1 - 2^{- (k - 1)} \geq \frac{1}{2} .$

Facts & Assumptions

Given: The stated odd composite $N$ , its prime-power factorization, a uniform unit $a$ , and the true order $r = {ord}_{N} (a)$ .

[F1]

Every integer $N \geq 2$ has a finite prime factorization unique up to order (The fundamental theorem of arithmetic: every integer $n \geq 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i < r} p_{i} = \prod_{j < s} q_{j}$ with every $p_{i}$ and $q_{j}$ prime, then $r = s$ and $q_{i} = p_{π (i)}$ for some $π \in Sym (r)$ , For $n \geq 1$ and any injective list $p : r \to Z$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i < r} p_{i}^{v_{p_{i}} (n)}$ ; the exponents are determined by $n$ , and $v_{q} (n) = 0$ for every prime $q$ outside the list).

[F2]

The CRT map restricts to an isomorphism from the unit group modulo $N$ to the product of the unit groups modulo the pairwise-coprime prime powers (For pairwise coprime positive moduli, the Chinese remainder bijection restricts to an isomorphism of unit groups).

[F3]

The uniform product law has independent coordinates (Finite probability spaces, outcome weights, events, and event probabilities, The finite product of finite probability spaces, Product weights normalize, and coordinate events are mutually independent).

[F4]

For each odd prime power, every possible value of $v_{2}$ of a uniform unit's order has probability at most $1 / 2$ (Two-adic order distribution in odd prime-power unit groups).

[F5]

The half-power of a true even order is a nonidentity square root of one; in each odd prime-power component the only square roots are $\pm 1$ , and mixed CRT signs give proper gcd factors (Half an even order gives a square root of one, Mixed CRT signs yield proper gcd factors).

[F6]

The order of a unit is the least positive exponent giving the identity; its powers equal the identity exactly at multiples of that order (The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity, Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ , If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ).

[F7]

The exponent of $2$ in a positive integer is the greatest $s$ with $2^{s}$ dividing that integer (The $p$ -adic valuation $v_{p} (a)$ of a nonzero integer: the greatest $k \in N$ with $p^{k} ∣ a$ ); cancellation by a nonzero integer is valid (The integers have no zero divisors; multiplicative cancellation), and Bézout and Euclid's lemma justify cancellation of coprime factors (Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ , Coprime integers: $\gcd (a, b) = 1$ , $a$ and $b$ are coprime if and only if $a x + b y = 1$ for some integers $x, y$ ; and in that case the only common divisors of $a$ and $b$ are $1$ and $- 1$ , If $\gcd (a, b) = 1$ and $a ∣ b c$ then $a ∣ c$ ; and if $a ∣ c$ , $b ∣ c$ and $\gcd (a, b) = 1$ then $a b ∣ c$ , Bézout's identity: for integers $a, b$ not both zero, $\gcd (a, b)$ is the least positive element of ${a x + b y : x, y \in Z}$ ; in particular $a x + b y = \gcd (a, b)$ has an integer solution).

[F8]

Each unit group modulo a positive integer is finite, so a unit in it has a finite positive order (The unit group $(Z / n)^{\times}$ and Euler's totient $φ (n) = ∣ (Z / n)^{\times} ∣$ for $n \geq 1$ , The order of every element of a finite group divides the order of the group).

Proof

1.1givenF1algebra

By [F1], $N$ has a factorization into distinct prime powers. Since $N$ is odd, every prime factor is odd. If there were only one distinct prime $p$ , then $N = p^{e}$ ; $e = 1$ would make $N$ prime, while $e \geq 2$ would make it a perfect power. Both contradict the hypotheses, so $k \geq 2$ .

1.2givenF2F3algebra

Under the CRT isomorphism [F2], a uniform unit corresponds to a uniform tuple $(a_{i})_{i < k}$ in the product of the local unit groups: the map is a bijection and preserves equal weights. By [F3], the local components, and hence their orders $r_{i} = {ord}_{p_{i}^{e_{i}}} (a_{i})$ and valuations $j_{i} = v_{2} (r_{i})$ , are independent. Each local unit group is finite, so only finitely many valuation values occur.

2.1step 1.2F2F6F7F8algebra

By [F8], $r$ is finite and positive. Since $a^{r} = 1$ modulo $N$ , CRT and [F6] give $r_{i} ∣ r$ for each $i$ . Let $J = \max_{i} j_{i}$ and $m = v_{2} (r)$ . Since $2^{j_{i}} ∣ r_{i} ∣ r$ , the definition of $m$ gives $j_{i} \leq m$ for every $i$ , so $J \leq m$ . If $m > J$ , write $r = 2^{m} s$ and $r_{i} = 2^{j_{i}} s_{i}$ with $s, s_{i}$ odd; here $m \geq 1$ . From $r_{i} ∣ r$ , canceling the nonzero factor $2^{j_{i}}$ gives $s_{i} ∣ 2^{m - j_{i}} s$ . Since $s_{i}$ is odd, it is coprime to $2^{m - j_{i}}$ , so Euclid's lemma gives $s_{i} ∣ s$ . Also $j_{i} \leq J < m$ , so $2^{j_{i}} ∣ 2^{m - 1}$ . Thus every $r_{i} ∣ r / 2$ , so every local component and therefore $a^{r / 2}$ equals the identity by [F2,F6]. This contradicts the minimality of $r$ , since $0 < r / 2 < r$ . Therefore $m = J$ .

2.2step 1.2F3F4algebra

Write $p_{i} (j) = P (j_{i} = j)$ . By independence [F3], the probability that all valuations agree is $\sum_{j} \prod_{i < k} p_{i} (j)$ . For every possible $j$ , [F4] bounds each of $p_{1} (j), \dots, p_{k - 1} (j)$ by $1 / 2$ , so $\prod_{i < k} p_{i} (j) \leq 2^{- (k - 1)} p_{0} (j)$ . Summing over the finite set of possible $j$ gives probability at most $2^{- (k - 1)}$ , since $\sum_{j} p_{0} (j) = 1$ .

3.1step 2.1F5F6F7choosealgebra

If the $j_{i}$ are not all equal, then $J \geq 1$ ; choose indices $i, h$ with $j_{i} = J$ and $j_{h} < J$ . Write $r = 2^{J} s$ and $r_{h} = 2^{j_{h}} s_{h}$ with $s, s_{h}$ odd. Since $r_{h} ∣ r$ , cancellation gives $s_{h} ∣ 2^{J - j_{h}} s$ ; because $s_{h}$ is odd, it is coprime to $2^{J - j_{h}}$ , so Euclid's lemma gives $s_{h} ∣ s$ . As $j_{h} < J$ , $2^{j_{h}} ∣ 2^{J - 1}$ , hence $r_{h} ∣ 2^{J - 1} s = r / 2$ . By [F6], $a_{h}^{r / 2} = 1$ . For the maximum index, $r_{i} ∤ r / 2$ because its two-adic valuation is $J$ while $v_{2} (r / 2) = J - 1$ ; hence [F6] gives $a_{i}^{r / 2} \neq 1$ . Its square is $1$ because $r_{i} ∣ r$ . By [F5], this local root is $- 1$ , while the $h$ component is $+ 1$ . Thus the global square root is neither global sign, and [F5] gives proper gcd factors.

4.1step 1.1step 2.2step 3.1algebra∎

By step 2.2, the valuations differ with probability at least $1 - 2^{- (k - 1)}$ ; step 3.1 shows that every such outcome gives a proper factor. Since $k \geq 2$ by step 1.1, this probability is at least $1 / 2$ .

AlgorithmAlgorithm: AI-adaptedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Shor factoring with verified output and bounded outer retries

Definition

Inputs. A composite integer $N \geq 4$ , encoded in binary, and a rational target failure probability $δ = u / 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 \geq 1$ and exponent $e \geq 0$ , CappedPower(c,e) returns $\min {c^{e}, N + 1}$ : initialize $(r, d, k) = (1, c, e)$ ; while $k > 0$ , replace $r$ by $\min {r d, N + 1}$ if $k$ is odd, then replace $k$ by $⌊ k / 2 ⌋$ and, if the new $k > 0$ , replace $d$ by $\min {d^{2}, N + 1}$ . For any integer $c$ and exponent $e \geq 0$ , ModPower(c,e) returns $c^{e} m o d N$ : initialize $(r, d, k) = (1, c m o d N, e)$ ; while $k > 0$ , replace $r$ by $r d m o d N$ if $k$ is odd, then replace $k$ by $⌊ k / 2 ⌋$ and, if the new $k > 0$ , replace $d$ by $d^{2} m o d N$ . In both routines, parity, quotient, product, comparison, and remainder operations are exact integer operations.

Set $n = ⌈ \log_{2} N ⌉$ . If $N$ is even, set $d = 2$ , check $1 < d < N$ and $N m o d d = 0$ , and return $d$ if both checks pass.
For each integer exponent $e = 2, 3, \dots, n$ , initialize $L = 2$ and $R = N$ . While $L \leq R$ , set $b = ⌊ (L + R) / 2 ⌋$ and $y = 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 m o d 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.
Initialize $T = 1$ , $A = 5$ , and $B = 8$ . While $A v > B u$ , replace $(T, A, B)$ by $(T + 1, 5 A, 8 B)$ . Continue to instruction 4 with this $T$ ; it is the least positive integer satisfying $5^{T} v \leq 8^{T} u$ , equivalently $T = ⌈ \ln (1 / δ) / (- \ln (5 / 8)) ⌉$ .
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 m o d g = 0$ , return $g$ . If $g \neq 1$ , start the next attempt; the case $g = N$ is rejected as an invalid sample and also starts the next attempt.
When $g = 1$ , run modular order finding on $(N, a)$ with target parameter $b = 2$ , so its target failure is $2^{- 2} = 1 / 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 \leq q \leq N$ , $q$ is even, and $ModPower (a, q) = 1$ . Set $z = ModPower (a, q / 2)$ , the standard representative of $a^{q / 2} m o d 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 m o d d_{\pm} = 0$ ; if neither passes, start the next attempt.
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.

Remarks

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 \geq 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.

DefinitionDefinition: AI-adaptedProof: Not applicableOpen item page →

Shor factoring cost-accounting branches

Definition

Fix a promised input integer $N \geq 4$ , set $n = ⌈ \log_{2} N ⌉$ , and let an order-finding phase register have width $m \geq 1$ and size $Q = 2^{m}$ . A work wire is an auxiliary circuit wire outside the stated input and output registers; its presence and use are charged as part of the supplied circuit. Classical bit transitions use the convention of Classical bit-operation cost. The cost report for Shor factoring keeps the following branches separate.

Explicit reversible arithmetic. A supplied reversible circuit for multiplication by a fixed residue modulo $N$ is charged by its actual gate occurrences and work wires. Each use of that circuit is also counted in a separate modular-multiplier-call coordinate. The circuit, its inverse, and any controlled version must be supplied; this definition assigns none of them zero cost. It asserts no finite circuit-description generator or generation-time bound.
Ideal exact-angle QFT. In this named ideal submodel, each Hadamard, exact controlled-phase rotation, and swap in the supplied $m$ -bit QFT circuit counts as one ideal gate. The standard exact cyclic QFT has $m$ Hadamards, $m (m - 1) / 2$ controlled-phase rotations, and $⌊ m / 2 ⌋$ swaps, hence $O (m^{2})$ ideal gates. This submodel permits exact real angles as unit-cost gates. It supplies no finite gate alphabet, finite binary description, approximation, compiler, or uniform-family claim.
Bare controlled-unitary access. If only a controlled call to $U_{x} : ∣ z ⟩ \mapsto ∣ x z m o d N ⟩$ is supplied, implementing the controlled power $U_{x}^{2^{j}}$ by repetition costs $2^{j}$ oracle calls. Across $j = 0, \dots, m - 1$ this is $\sum_{j} 2^{j} = Q - 1$ calls per phase-estimation sample. These oracle-query counts are separate from gate counts.
Classical bit work. Integer inputs are binary, elementary arithmetic is charged in bit operations, and schoolbook multiplication of two $b$ -bit integers costs $O (b^{2})$ . A rejection sampler's random-bit cost is reported in expectation separately from deterministic bit operations.

The four coordinates used by the factoring cost theorem are ideal or explicit quantum gates, modular-multiplier calls, bare controlled-unitary oracle queries, and classical bit operations. An inapplicable branch is not reported as a zero-cost implementation.

Remarks

This is a cost convention for the stated algorithmic comparison. In particular, the ideal exact-angle QFT count is not a finite-alphabet or uniform-circuit theorem.

LemmaStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Even and perfect-power preprocessing returns a proper factor

Statement

For a promised composite $N \geq 4$ , the even branch and the finite integer-root precheck in Shor factoring with verified output and bounded outer retries return a proper factor whenever they return. If $N$ is even, the even branch returns $2$ . If $N = b^{e}$ for integers $b \geq 2$ and $e \geq 2$ and $N$ is odd, the root-search branch is reached, detects an exact-power representation $N = c^{f}$ with $c \geq 2$ and $f \geq 2$ , and returns its base $c$ as a proper factor. Writing $n = ⌈ \log_{2} N ⌉$ , its schoolbook bit cost is $O (n^{5})$ .

Facts & Assumptions

Given: A composite integer $N \geq 4$ , $n = ⌈ \log_{2} N ⌉$ , and the even/perfect-power preprocessing instructions in Shor factoring with verified output and bounded outer retries.

[F1]

Divisibility means $d ∣ N$ exactly when $N = d q$ for an integer $q$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ); integer powers are natural monoid powers with $b^{0} = 1$ and $b^{e + 1} = b^{e} b$ (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ ).

[F2]

Integer order is translation invariant, products of positive integers are positive, and the natural embedding preserves order (The integers form a totally ordered ring, The integers form a commutative ring, The naturals embed in the integers).

[F3]

The binary search and exponent range are those in Shor factoring with verified output and bounded outer retries; its capped repeated-squaring powers use integers at most $N + 1$ . Schoolbook multiplication of two $n$ -bit integers costs $O (n^{2})$ bit operations (Shor factoring cost-accounting branches).

Proof

1.1givenF1F2algebra

If $N$ is even, $2 ∣ N$ . Since $N \geq 4$ , $1 < 2 < N$ , so the returned integer is a proper factor.

1.2givenF1F2algebra

Suppose the precheck finds $N = b^{e}$ with $2 \leq b \leq N$ and $e \geq 2$ . Then $N = b b^{e - 1}$ , so $b ∣ N$ by [F1]. The power $b^{e - 1} \geq 2$ , so $N = b b^{e - 1} \geq 2 b > b$ ; hence $1 < b < N$ and its explicit divisibility verification returns a proper factor.

2.1givenF1F2algebra

Conversely, suppose $N = b^{e}$ with $b \geq 2$ and $e \geq 2$ . If $N$ is even, step 1.1 shows that the earlier even branch returns $2$ , so the root search is not reached. Now suppose $N$ is odd. Then the root-search branch is reached, and $2^{e} \leq b^{e} = N \leq 2^{n}$ , so $e \leq n$ and the loop includes this exponent. If the algorithm has not already returned on an earlier exact-power match in this root search, then for this fixed $e$ , if $2 \leq x < y$ , $y^{e} - x^{e} = (y - x) \sum_{j = 0}^{e - 1} y^{e - 1 - j} x^{j} > 0,$ because the factor and every summand are positive by [F2]. Hence $x \mapsto x^{e}$ is strictly increasing, so binary search on $[2, N]$ finds $b$ ; capping values above $N$ at $N + 1$ preserves each comparison with $N$ . If the algorithm already returned on an earlier root-search match, that match was itself an exact-power representation of $N$ , and step 1.2 shows that its returned base is a proper factor. Thus the odd perfect-power input returns a proper factor through the root search, while the even case is handled by step 1.1.

3.1givenF3algebra∎

There are at most $n$ exponents and at most $n$ binary-search comparisons per exponent because $N \leq 2^{n}$ . Each comparison uses at most $O (\log n)$ capped multiplications of $O (n)$ -bit integers, hence $O (n^{2} \log n)$ bit operations by [F3]. The total is $O (n^{4} \log n) = O (n^{5})$ for $n \geq 2$ , proving the claimed bound.

TheoremStatement: AI-adaptedProof: AI-generatedOpen item page →

Rejection sampling is uniform, almost surely terminating, and has expected linear bit cost

Statement

For every $N \geq 3$ , the procedure in Exact uniform sampling from the nonzero residue representatives halts almost surely and returns each $a \in {1, \dots, N - 1}$ with probability exactly $1 / (N - 1)$ . If $h = ⌈ \log_{2} (N - 1) ⌉$ , its expected random-bit use is at most $2 h$ and its expected total classical bit transitions are $O (h)$ .

Facts & Assumptions

Given: $N \geq 3$ , $M = N - 1$ , $h = ⌈ \log_{2} M ⌉$ , and the rejection procedure in Exact uniform sampling from the nonzero residue representatives.

[A1]

Countable choice and dependent choice are assumed only to form the countable product of fair-bit probability spaces used by the random tape (The Axiom of Countable Choice ( ${A C}_{ω}$ ), The axiom of dependent choice: a relation in which every element is related to something admits an $N$ -indexed chain, Assuming countable and dependent choice, countable products of arbitrary probability spaces). The finite probability branches of the number-theoretic proofs do not use this axiom branch.

[F1]

Each bit has probability $1 / 2$ for both values, finite blocks have their product law under the countable product measure, and disjoint blocks are independent (Assuming countable and dependent choice, countable products of arbitrary probability spaces, Finite probability spaces, outcome weights, events, and event probabilities, Coordinate random elements of a countable product are independent).

[F2]

For a decreasing sequence of events in a probability space, the probability of the intersection is the limit of the probabilities (Continuity from above when one set has finite measure).

[F3]

For a nonnegative random variable, expectation is the tail integral (Expectation of a nonnegative or integrable random variable, Layer-cake formulas for random variables).

[F4]

The multitape bit-cost convention charges random-bit generation, binary arithmetic, comparisons and output writing (Classical bit-operation cost, Shor factoring cost-accounting branches).

Proof

1.1givenA1F1algebra

A block is accepted with probability $p = M / 2^{h}$ . By the definition of $h$ , $M \leq 2^{h}$ , and either $M = 2^{h}$ or $M > 2^{h - 1}$ ; hence $p \geq 1 / 2$ . If $p = 1$ , every block is accepted and each valid $b$ is output with probability $2^{- h} = 1 / M$ . If $p < 1$ , for a fixed valid $b < M$ the probability that the algorithm outputs $b + 1$ on block $t$ is $(1 - p)^{t - 1} 2^{- h}$ by [F1], and summing gives $2^{- h} \sum_{t \geq 0} (1 - p)^{t} = 2^{- h} / p = 1 / M$ .

2.1givenA1step 1.1F1F2algebra

The events that the first $j$ blocks are all rejected decrease with $j$ and have probability $(1 - p)^{j} \leq 2^{- j}$ by [F1]. Their intersection is the event that the algorithm never halts, and [F2] gives that event probability $\lim_{j \to \infty} (1 - p)^{j} = 0$ . Thus the procedure halts almost surely.

3.1givenA1step 1.1F1F3F4algebra∎

Let $K$ be the number of blocks read before the first acceptance. For integer $j \geq 0$ , $P (K > j) = (1 - p)^{j}$ . The tail function is constant on each interval $[j, j + 1)$ , so [F3] gives $E [K] = \sum_{j \geq 0} (1 - p)^{j} = 1 / p \leq 2$ , with the $p = 1$ case interpreted as $K = 1$ . Computing $h$ as the binary length of $M - 1$ takes $O (h)$ transitions. Each block reads and stores $h$ bits in $O (h)$ transitions; comparing that $h$ -bit integer with $M$ takes $O (h)$ transitions, and incrementing an accepted value and writing the output use at most $h + 1$ bits. Since $h \geq 1$ , these operations also take $O (h)$ transitions, so the nonrandom work per block is $O (h)$ . By [F4], these transitions and the $h$ random-bit generations are charged. Thus expected random-bit use is at most $2 h$ and expected total bit transitions are $O (h)$ .

TheoremStatement: AI-adaptedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Order-to-factor output correctness

Statement

For every promised composite $N \geq 4$ , every non-FAIL output of Shor factoring with verified output and bounded outer retries is a proper divisor of $N$ . In its odd-unit branch, any candidate $q$ that passes the algorithm's checks and is even has $a^{q} \equiv 1 (m o d N)$ ; with $z = a^{q / 2} m o d N$ , if $z \equiv̸ \pm 1 (m o d N)$ , both $\gcd (z - 1, N)$ and $\gcd (z + 1, N)$ are proper nontrivial divisors. No minimality of $q$ is needed for this output-correctness claim.

Facts & Assumptions

Given: The input/output instructions in Shor factoring with verified output and bounded outer retries, a promised composite $N \geq 4$ , and an execution that returns rather than FAIL.

[F1]

The even and perfect-power preprocessing return only a divisor $d$ satisfying $1 < d < N$ (Even and perfect-power preprocessing returns a proper factor).

[F2]

For a uniform residue $a \in {1, \dots, N - 1}$ , if $\gcd (a, N) > 1$ it is a proper factor; if the gcd is one then $a$ is a unit (Random residue gcd branch for factoring, For $n \geq 1$ , $[a]_{n}$ is a unit if and only if $\gcd (a, n) = 1$ ).

[F3]

For a unit $a$ and an accepted even exponent $q$ with $a^{q} \equiv 1$ , $z = a^{q / 2}$ satisfies $z^{2} \equiv 1$ (Half an even order gives a square root of one).

[F4]

Every odd composite $N$ has a factorization $N = \prod_{i < k} p_{i}^{e_{i}}$ into distinct odd primes with $k \geq 1$ (The fundamental theorem of arithmetic: every integer $n \geq 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i < r} p_{i} = \prod_{j < s} q_{j}$ with every $p_{i}$ and $q_{j}$ prime, then $r = s$ and $q_{i} = p_{π (i)}$ for some $π \in Sym (r)$ , For $n \geq 1$ and any injective list $p : r \to Z$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i < r} p_{i}^{v_{p_{i}} (n)}$ ; the exponents are determined by $n$ , and $v_{q} (n) = 0$ for every prime $q$ outside the list). For this factorization, a square root $z^{2} \equiv 1$ other than the two global signs gives both gcds as proper nontrivial divisors (Mixed CRT signs yield proper gcd factors).

Proof

1.1givenF1algebra

The even branch returns $2$ only after checking $1 < 2 < N$ and $N m o d 2 = 0$ . The perfect-power branch returns only after the exact checks $1 < b < N$ and $N m o d b = 0$ , and [F1] proves its candidate is proper.

1.2givenF2algebra

In a random-residue branch, a returned gcd candidate is checked to satisfy $1 < d < N$ and $N m o d d = 0$ ; [F2] also shows that a nonunit gcd cannot equal $N$ because the sampled representative satisfies $a < N$ . Thus any returned candidate in this branch is proper.

1.3givenF3F4algebra

The order-finding branch is reached only after the even and perfect-power branches, so $N$ is odd. It first verifies $\gcd (a, N) = 1$ and $a^{q} \equiv 1 (m o d N)$ . If $q$ is even it sets $z = a^{q / 2}$ ; [F3] gives $z^{2} \equiv 1 (m o d N)$ . If $z \equiv̸ \pm 1$ , [F4] gives a prime-power factorization and the CRT sign lemma shows that both computed gcds lie strictly between $1$ and $N$ and divide $N$ , so the explicit verification accepts a proper factor.

2.1step 1.1step 1.2step 1.3∎

Every return branch is one of steps 1.1, 1.2 or 1.3, and each branch verifies the strict divisor conditions before returning. Therefore every non-FAIL output is a proper divisor.

Remarks

This theorem proves output correctness conditional on the outer algorithm's exact period and gcd checks. It does not rely on a candidate being the minimal order, and it makes no probability claim about whether the order-finding branch is reached.

TheoremStatement: AI-adaptedProof: AI-generatedOpen item page →

Separate Shor factoring bit, gate, and query costs

Statement

Let $N \geq 4$ , $n = ⌈ \log_{2} N ⌉$ , and let $δ = u / v \in (0, 1)$ be a reduced rational encoded in binary, with $B$ the bit length of $v$ . Let $T$ be the attempt cap in Shor factoring with verified output and bounded outer retries, and put $Q = 2^{2 n + 3}$ . For the arithmetic, control, sampler and post-processing work after the declared circuits are supplied, under the explicit reversible-arithmetic branch and ideal exact-angle QFT branch of Shor factoring cost-accounting branches, the procedure uses

$O (n^{4} T) = O (n^{4} (1 + \ln (1 / δ)))$ quantum gates;
$O (n^{2} T)$ controlled modular-multiplier calls and zero external black-box queries;
$O (n^{5} + n^{4} T + B^{3})$ expected classical bit operations, including sampler bits and exact computation of $T$ .

For the same order-finding control flow with only bare controlled access to $U_{x}$ , one phase-estimation sample costs $Q - 1$ controlled- $U_{x}$ queries, so the outer algorithm uses $O (n T (Q - 1))$ such queries. No polynomial-in- $n$ query bound, finite-alphabet compilation, uniform-family gate claim, or circuit-description generation-time bound is asserted.

Facts & Assumptions

Given: The algorithm Shor factoring with verified output and bounded outer retries on binary input $N, δ$ , with its declared outer cap $T$ and phase width $m = 2 n + 3$ .

[F1]

For $m = 2 n + 3$ , $Q = 2^{m}$ , and internal failure target $2^{- b}$ , the order finder uses $t = 4 (n + 1) b$ independent samples. Its cost theorem gives $O (n^{2} b)$ controlled modular-multiplier calls, $O (n^{4} b)$ gates and $O (n^{4} b)$ classical bit transitions in the explicit-arithmetic/ideal-QFT model; with bare controlled- $U_{x}$ access, one sample costs $Q - 1$ queries (Modular order finding with rational reconstruction, Separate order-finding query, gate, and bit costs).

[F2]

A known controlled modular multiplication uses $O (n^{2})$ gates, and the repeated-squaring constants and inverses can be computed in $O (n^{3})$ classical bit transitions (Gate and bit cost of modular multiplication and powering).

[F3]

The ideal exact-angle inverse QFT has $O (m^{2})$ gates, while the named cost convention keeps this ideal count separate from the explicit arithmetic circuits, multiplier calls, bare-unitary queries and classical bit operations; it asserts no finite gate alphabet or uniform family (Shor factoring cost-accounting branches).

[F4]

The even/perfect-power preprocessing takes $O (n^{5})$ schoolbook bit operations (Even and perfect-power preprocessing returns a proper factor).

[F5]

For $h = ⌈ \log_{2} (N - 1) ⌉$ , one rejection-sampler call halts almost surely, returns a uniform element of ${1, \dots, N - 1}$ , and uses at most $2 h$ expected random bits and $O (h)$ expected total bit transitions (Rejection sampling is uniform, almost surely terminating, and has expected linear bit cost).

[F6]

Classical bit cost counts machine transitions, including random-bit generation, arithmetic, comparisons, preprocessing and output writing (Classical bit-operation cost).

[F7]

The resource model records gate occurrences, work wires, oracle queries, description length, generator time, and classical bit costs as distinct coordinates; separate theorems must establish each bound (Circuit-family and computation cost model).

Proof

1.1givenF1algebra

The Shor algorithm fixes $b = 2$ , so [F1] gives $O (n^{2})$ multiplier calls, $O (n^{4})$ gates and $O (n^{4})$ classical bit transitions for each order-finding invocation. There are at most $T$ such invocations, so their totals are $O (n^{2} T)$ calls, $O (n^{4} T)$ gates and $O (n^{4} T)$ bit transitions. The definition of $T$ gives $T = O (1 + \ln (1 / δ))$ because $- \ln (5 / 8)$ is a positive constant.

1.2givenF1algebra

In the bare controlled- $U_{x}$ branch, one phase sample applies controlled powers $U_{x}^{2^{j}}$ for $j = 0, \dots, m - 1$ . Repeating the bare call $2^{j}$ times implements the $j$ th power, so one sample uses $\sum_{j = 0}^{m - 1} 2^{j} = 2^{m} - 1 = Q - 1$ queries. For fixed $b = 2$ , [F1] gives $t = 8 (n + 1) = O (n)$ samples per order call. At most $T$ calls therefore use $O (n T (Q - 1))$ queries.

1.3F1F4F5F6algebra

The perfect-power check costs $O (n^{5})$ by [F4]. Each order call costs $O (n^{4})$ classical bit transitions by [F1]. The outer verification adds at most $O (n^{3})$ transitions per attempt: binary modular exponentiation uses $O (n)$ products of $n$ -bit integers. Schoolbook multiplication takes $O (n^{2})$ transitions, and binary long division has at most $n$ quotient positions, each requiring an $O (n)$ -bit comparison/subtraction, so product remainders also take $O (n^{2})$ transitions. The Euclidean gcd algorithm has $O (n)$ remainder steps because in each pair of successive divisions the positive remainder at least halves; each division takes $O (n^{2})$ transitions by the same long-division count. Divisor comparisons and remainder checks fit this bound. By [F5], each sampler call uses $O (n)$ expected total transitions. Thus all these per-attempt work is $O (n^{4} T)$ in total.

1.4givenF6algebra

The exact cap is computed by increasing $t$ until $5^{t} v \leq 8^{t} u$ . Since $v < 2^{B}$ and $u \geq 1$ , $δ > 2^{- B}$ ; also $(5 / 8)^{2 B} = (25 / 64)^{B} < 2^{- B}$ . Hence $T \leq 2 B$ . Throughout this loop, the exact powers have $O (B)$ bits, and each of at most $2 B$ multiply/compare iterations costs $O (B^{2})$ schoolbook bit transitions. Computing $T$ therefore costs $O (B^{3})$ .

2.1F1F2F3F7step 1.1algebra

In the explicit-arithmetic branch, each multiplier call is charged to the supplied reversible circuit; it is not a black-box query. [F2] supplies its $O (n^{2})$ gate count and [F3] supplies the separate ideal QFT count. The resulting gate count is the $O (n^{4} T)$ bound in step 1.1; the distinct coordinates are those of [F7].

3.1step 1.3step 1.4algebra∎

Combining steps 1.3 and 1.4 gives $O (n^{5} + n^{4} T + B^{3})$ expected classical bit operations.

Remarks

The current cost-model definition and the QA08 arithmetic and order-finding cost theorems provide the stated separate resource coordinates. The supplied-circuit and ideal-QFT conventions above determine which bounds are asserted; they provide no circuit-description generation-time bound.

TheoremStatement: AI-adaptedProof: AI-generatedOpen item page →

Bounded-error success of Shor factoring

Statement

For a promised composite $N \geq 4$ and rational $0 < δ < 1$ , the procedure Shor factoring with verified output and bounded outer retries returns a proper divisor with probability at least $1 - δ$ after its declared $T = ⌈ \ln (1 / δ) / (- \ln (5 / 8)) ⌉$ outer attempts. Its exact even and perfect-power preprocessing branches succeed with probability one.

Facts & Assumptions

Given: The algorithm Shor factoring with verified output and bounded outer retries on $N, δ$ , with $T$ the least positive integer satisfying $(5 / 8)^{T} \leq δ$ .

[F1]

The even and perfect-power preprocessing branches return proper factors whenever they apply (Even and perfect-power preprocessing returns a proper factor).

[F2]

A sampled nonunit residue immediately yields a proper gcd factor, and conditional on gcd one the residue is uniform in the unit group (Random residue gcd branch for factoring).

[F3]

For an odd composite that is not a perfect power, the true-order reduction succeeds on a uniform unit with probability at least $1 / 2$ (Classical randomized order-to-factor success bound).

[F4]

The rejection sampler halts almost surely and returns a uniform representative (Rejection sampling is uniform, almost surely terminating, and has expected linear bit cost).

[F5]

Every returned output is a proper divisor (Order-to-factor output correctness).

[F6]

The algorithm uses fresh independent sampler tapes and fresh order-finding randomness across attempts (Shor factoring with verified output and bounded outer retries). For each fixed unit input, order finding uses finitely many measurements of finite registers (Success probability and repetition for modular order finding). Finite terminal outcome laws can therefore be combined by the finite product law, whose coordinate events are independent (The finite product of finite probability spaces, Product weights normalize, and coordinate events are mutually independent).

[F7]

In a finite probability space, conditional probability is $P (A ∣ B) = P (A \cap B) / P (B)$ when $P (B) > 0$ (Conditional probability $P (A ∣ B)$ for $P (B) > 0$ ).

[A1]

Countable choice and dependent choice supply only the countable independent fair-bit tape used by [F4] (The Axiom of Countable Choice ( ${A C}_{ω}$ ), The axiom of dependent choice: a relation in which every element is related to something admits an $N$ -indexed chain, Assuming countable and dependent choice, countable products of arbitrary probability spaces).

[A2]

The current body of Success probability and repetition for modular order finding states that for every fixed unit input and integer parameter $b \geq 1$ , the exact-order output probability is at least $1 - 2^{- b}$ . Setting $b = 2$ gives at least $3 / 4$ for each fixed unit input. The actual algorithm and theorem bodies and the proof route supporting this statement were inspected; this records the current carrier, not independent acceptance.

Proof

1.1givenF1F3algebra

If $N$ is even or a perfect power, preprocessing returns a proper factor by [F1], so the theorem holds with probability one. Otherwise $N$ is odd, composite, and not a perfect power, so [F3] applies.

1.2F2F3F4F6F7A1A2algebra

By [F4], the sampler halts almost surely and has uniform finite output law. For each unit representative $a$ , let $Y_{a}$ be the finite set of order-finding measurement transcripts and $μ_{a}$ its probability mass function; for a nonunit use a singleton $Y_{a}$ of mass one. One attempt has finite terminal outcome space $Ω_{N} = {(a, y) : 1 \leq a < N, y \in Y_{a}}$ with weights $w_{N} (a, y) = μ_{a} (y) / (N - 1)$ : the sampler marginal is [F4], the subsequent fresh measurement law is $μ_{a}$ , and these weights sum to one. All conditioning here is on this finite space as in [F7]. Conditional on the unit event $U$ , [F2] makes $[a]_{N}$ uniform in the unit group. Let $G \subseteq U$ be the representatives whose true-order reduction succeeds, so [F3] gives $P (G ∣ U) \geq 1 / 2$ . For each $a \in G$ , [A2] gives exact-order probability at least $3 / 4$ ; summing its transcript weights gives $P (G and exact order ∣ U) \geq (3 / 4) P (G ∣ U) \geq 3 / 8$ . On that event the algorithm returns a proper factor. This uses a pointwise order-finding bound, without assuming independence between the unit and its measurement outcome.

2.1step 1.2F5algebra

Let $p$ be the probability that a sampled residue is a unit. The attempt succeeds with probability at least $(1 - p) + p (3 / 8) = 1 - 5 p / 8 \geq 3 / 8$ . Any output is correct by [F5]; a nonminimal or otherwise unsuccessful order candidate can only cause this attempt to continue.

3.1givenstep 1.2step 2.1F4F6algebra∎

Preassign $T$ independent terminal records with the finite product law $w_{N}^{\otimes T}$ . By the fresh randomness in [F6], this is the joint terminal law of the actual attempts; stopping at the first success simply leaves subsequent records unused. The event that any of these finitely many samplers does not halt has probability zero by [F4]. Let $B_{i}$ be the coordinate event that attempt $i$ returns no factor. Step 2.1 gives $P (B_{i}) \leq 5 / 8$ , and finite coordinate independence [F6] gives $P (⋂_{i = 1}^{T} B_{i}) = \prod_{i = 1}^{T} P (B_{i}) \leq (5 / 8)^{T} \leq δ$ . Thus the probability of returning a proper factor is at least $1 - δ$ .

Remarks

The exact-order probability premise [A2] is taken from the current batch-32 carrier and checked against its stated fixed-unit hypotheses; the cited carrier remains a draft and this record is not independent acceptance. Countable choice and dependent choice are used only to supply the sampler's independent fair-bit tapes [A1].

5 · Examples, counterexamples and false statements

None yet.

Shor’s Factoring Algorithm

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Exact uniform sampling from the nonzero residue representatives

Definition

Mixed CRT signs yield proper gcd factors

Statement

Facts & Assumptions

Proof

Half an even order gives a square root of one

Statement

Facts & Assumptions

Proof

Two-adic order distribution in odd prime-power unit groups

Statement

Facts & Assumptions

Proof

Random residue gcd branch for factoring

Statement

Facts & Assumptions

Proof

Classical randomized order-to-factor success bound

Statement

Facts & Assumptions

Proof

Shor factoring with verified output and bounded outer retries

Definition

Remarks

Shor factoring cost-accounting branches

Definition

Remarks

Even and perfect-power preprocessing returns a proper factor

Statement

Facts & Assumptions

Proof

Rejection sampling is uniform, almost surely terminating, and has expected linear bit cost

Statement

Facts & Assumptions

Proof

Order-to-factor output correctness

Statement

Facts & Assumptions

Proof

Remarks

Separate Shor factoring bit, gate, and query costs

Statement

Facts & Assumptions

Proof

Remarks

Bounded-error success of Shor factoring

Statement

Facts & Assumptions

Proof

Remarks

5 · Examples, counterexamples and false statements

Sources