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 — Examples

1 · Prerequisites

2 · Summary

The first example follows an accepted order sample for $N = 15$ and computes both proper factors. The second checks the even and perfect-power prechecks, a nonunit gcd, an odd-order retry, and a half-power equal to the global sign $- 1$ that produces no proper gcd. Every arithmetic claim is verified directly.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-adaptedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

A Shor order sample for factoring fifteen

Example

Take $N = 15$ and suppose the sampler returns the unit $a = 2$ . A valid order-finding result is $q = 4$ . Then $z = 2^{q / 2} = 4 (m o d 15)$ , and the two gcds are $\gcd (3, 15) = 3$ and $\gcd (5, 15) = 5$ .

Facts & Assumptions

Given: The Shor factoring instructions on $N = 15$ , a sample $a = 2$ , and the candidate $q = 4$ .

[F1]

A candidate is accepted for the reduction only when $2 \leq q \leq N$ , $q$ is even, and $a^{q} \equiv 1 (m o d N)$ ; the algorithm then computes the two gcds and returns only a verified proper divisor (Shor factoring with verified output and bounded outer retries).

[F2]

Residue powers are computed by multiplication of congruence classes (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, Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ ).

[F3]

A gcd is a common divisor, so a gcd strictly between $1$ and $N$ is a proper nontrivial divisor when it divides $N$ (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$ ).

[F4]

In an odd modulus, an accepted even exponent gives a square root of one; a non-global sign gives both gcds as proper factors (Order-to-factor output correctness).

Verification

1.1givenF1F2algebra

Direct multiplication gives $2^{1} \equiv 2$ , $2^{2} \equiv 4$ , $2^{3} \equiv 8$ , and $2^{4} \equiv 1 (m o d 15)$ . Since none of the first three powers is $1$ , the true order is $4$ . Thus $q = 4$ satisfies $2 \leq q \leq 15$ , is even, and passes the power check in [F1].

2.1givenstep 1.1F2F3F4algebra

The half-power is $z = 2^{2} \equiv 4 (m o d 15)$ , which is neither $1$ nor $- 1 \equiv 14$ . The computed values are $\gcd (z - 1, 15) = \gcd (3, 15) = 3$ and $\gcd (z + 1, 15) = \gcd (5, 15) = 5$ .

3.1givenstep 2.1F1F3F4∎

Both candidates divide $15$ and satisfy $1 < 3, 5 < 15$ . Since the algorithm checks $d_{-}$ first, it returns $3$ on this execution; both factors are certified by [F3] and [F4].

ExampleConstruction: AI-adaptedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

Shor factoring preprocessing and retry branches

Example

The following exact inputs exercise the early return and retry branches of Shor factoring with verified output and bounded outer retries: the even input $14$ , the perfect power $81 = 3^{4}$ , the nonunit choice $a = 5$ for $N = 15$ , and the unit samples $(N, a) = (35, 11)$ and $(15, 14)$ . For these two retry executions, take the order-finding subroutine to return candidate $q = 3$ for $(35, 11)$ and candidate $q = 2$ for $(15, 14)$ .

Facts & Assumptions

Given: The stated Shor algorithm, the displayed residue samples, and the chosen order-finding candidate outputs $q = 3$ for $(N, a) = (35, 11)$ and $q = 2$ for $(N, a) = (15, 14)$ .

[F1]

The even precheck returns $2$ for even composite $N \geq 4$ . When the root-search branch is reached on a perfect-power input, it detects an exact representation $N = c^{e}$ with $c \geq 2$ and $e \geq 2$ , and returns that representation's base $c$ as a proper factor (Shor factoring with verified output and bounded outer retries, Even and perfect-power preprocessing returns a proper factor).

[F2]

A nonunit sample in ${1, \dots, N - 1}$ gives a proper gcd factor; conditional on gcd one, it 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]

A period candidate is continued only when it is even, between $2$ and $N$ , and passes $a^{q} \equiv 1 (m o d N)$ ; the half-power gcds are returned only after the strict divisor checks (Shor factoring with verified output and bounded outer retries, Order-to-factor output correctness).

[F4]

Modular powers and gcds here are computed by integer multiplication, congruence and common-divisor calculations (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, Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ , 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$ ).

Verification

1.1givenF1algebra

For $N = 14$ , the even branch checks $1 < 2 < 14$ and $14 m o d 2 = 0$ , so it returns the proper factor $2$ before sampling. For $N = 81$ , the root search starts at $e = 2$ and finds $9^{2} = 81$ ; since $1 < 9 < 81$ , that branch returns $9$ . The alternative representation $81 = 3^{4}$ is not reached after this earlier return.

1.2givenF2F4algebra

For $N = 15$ and sample $a = 5$ , $\gcd (5, 15) = 5$ , which is strictly between $1$ and $15$ and divides $15$ ; the nonunit branch returns $5$ without order finding.

1.3givenF3F4algebra

For $N = 35$ and $a = 11$ , $\gcd (11, 35) = 1$ . The powers satisfy $11^{1} \equiv 11$ , $11^{2} \equiv 16$ , and $11^{3} \equiv 1 (m o d 35)$ , so the true order is $3$ , agreeing with the chosen candidate $q = 3$ . This candidate is odd and therefore fails the algorithm's even-period check; this attempt continues.

2.1givenF3F4algebra∎

For $N = 15$ and $a = 14$ , $\gcd (14, 15) = 1$ and $14^{2} \equiv 1 (m o d 15)$ while $14 \equiv̸ 1$ , so the true order is $2$ , agreeing with the chosen candidate $q = 2$ . The half-power is $z = 14 \equiv - 1 (m o d 15)$ , giving $\gcd (z - 1, 15) = \gcd (13, 15) = 1$ and $\gcd (z + 1, 15) = \gcd (15, 15) = 15$ . Neither passes the strict check, so the algorithm continues.

Shor’s Factoring Algorithm — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

A Shor order sample for factoring fifteen

Example

Facts & Assumptions

Verification

Shor factoring preprocessing and retry branches

Example

Facts & Assumptions

Verification

Sources