ExampleConstruction: AI-adaptedVerification: 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.

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].

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

46 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)