TheoremStatement: AI-adaptedProof: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

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.

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.

Depends on

Used by

A Shor order sample for factoring fifteen Example
Shor factoring preprocessing and retry branches Example
Bounded-error success of Shor factoring Theorem

Dependency tree · two levels

80 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (standard reference, not scraped)
Ronald de Wolf, Quantum Computing: Lecture Notes (standard reference, not scraped)