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.

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

Depends on

Used by

Bounded-error success of Shor factoring Theorem

Dependency tree · two levels

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