logicaffeine_proof/period.rs
1//! # The period / order seam — the classical shell of Shor's algorithm
2//!
3//! The multiplicative structure of `ℤ/N` hides a Fourier object: the map `x ↦ aˣ mod N` is **periodic**,
4//! with period `r = ord_N(a)` (the multiplicative order). That period is the additive shadow of the
5//! multiplicative group, and it *reveals the factorization*: if `r` is even and `a^{r/2} ≢ ±1 (mod N)`,
6//! then `a^{r/2}` is a nontrivial square root of `1`, so `gcd(a^{r/2} − 1, N)` and `gcd(a^{r/2} + 1, N)`
7//! split `N`. Factoring reduces to order-finding.
8//!
9//! The catch — and the whole point — is that **classically, finding the order is not easier than
10//! factoring.** Baby-step-giant-step does it in `O(√r)`, exponential in the bit length. Shor's quantum
11//! algorithm replaces this scan with a *quantum Fourier transform* that reads the period off in polynomial
12//! time. So this module is the honest classical primitive: the reduction is exact and the order-finder is
13//! correct, but the speed lives on the quantum side of the seam. It is also a first-class number-theory
14//! primitive in its own right (order-finding underlies discrete-log and group-structure computations).
15
16use crate::factor::{gcd, modpow};
17use logicaffeine_base::BigInt;
18use std::collections::HashMap;
19
20#[inline]
21fn i(x: i64) -> BigInt {
22 BigInt::from_i64(x)
23}
24
25#[inline]
26fn rem_pos(a: &BigInt, n: &BigInt) -> BigInt {
27 let r = a.div_rem(n).map(|(_, r)| r).unwrap_or_else(|| a.clone());
28 if r.is_negative() {
29 r.add(n)
30 } else {
31 r
32 }
33}
34
35#[inline]
36fn mulmod(a: &BigInt, b: &BigInt, n: &BigInt) -> BigInt {
37 rem_pos(&a.mul(b), n)
38}
39
40/// A stable map key for a residue in `[0, n)`.
41#[inline]
42fn key(x: &BigInt) -> Vec<u8> {
43 x.to_le_bytes().1
44}
45
46/// The distinct prime factors of a `u64` (trial division — used only on small orders).
47fn distinct_primes(mut r: u64) -> Vec<u64> {
48 let mut ps = Vec::new();
49 let mut d = 2u64;
50 while d * d <= r {
51 if r % d == 0 {
52 ps.push(d);
53 while r % d == 0 {
54 r /= d;
55 }
56 }
57 d += 1;
58 }
59 if r > 1 {
60 ps.push(r);
61 }
62 ps
63}
64
65/// Given a multiple `r` of `ord_N(a)`, reduce it to the exact order by stripping prime factors while the
66/// smaller exponent still annihilates `a`.
67fn reduce_to_order(a: &BigInt, mut r: u64, n: &BigInt) -> u64 {
68 let one = i(1);
69 for p in distinct_primes(r) {
70 while r % p == 0 && modpow(a, &i((r / p) as i64), n) == one {
71 r /= p;
72 }
73 }
74 r
75}
76
77/// The **multiplicative order** of `a` modulo `n` — the least `r > 0` with `aʳ ≡ 1 (mod n)` — by
78/// baby-step-giant-step, searching orders up to `bound`. `None` if `gcd(a, n) ≠ 1` (no order) or the order
79/// exceeds `bound`. Runs in `O(√bound)` field multiplications.
80pub fn multiplicative_order(a: &BigInt, n: &BigInt, bound: u64) -> Option<u64> {
81 let one = i(1);
82 if gcd(a, n) != one {
83 return None;
84 }
85 let a = rem_pos(a, n);
86 if a == one {
87 return Some(1);
88 }
89 // m = ⌈√bound⌉.
90 let m = (bound as f64).sqrt() as u64 + 1;
91
92 // Baby steps a⁰, a¹, …, a^{m−1}. A hit at aʲ = 1 (j > 0) IS the order (a small one).
93 let mut baby: HashMap<Vec<u8>, u64> = HashMap::new();
94 let mut cur = one.clone();
95 for j in 0..m {
96 if j > 0 && cur == one {
97 return Some(j);
98 }
99 baby.entry(key(&cur)).or_insert(j);
100 cur = mulmod(&cur, &a, n);
101 }
102 let giant = cur; // a^m
103 // Giant steps: find k with a^{km} = aⁱ (i < m), so a^{km − i} = 1 is a multiple of the order.
104 let mut gk = giant.clone();
105 for k in 1..=m {
106 if let Some(&idx) = baby.get(&key(&gk)) {
107 let cand = k * m - idx;
108 if cand > 0 {
109 return Some(reduce_to_order(&a, cand, n));
110 }
111 }
112 gk = mulmod(&gk, &giant, n);
113 }
114 None
115}
116
117/// Split `n` from a known order `r` of `a`: if `r` is even and `a^{r/2}` is a nontrivial square root of `1`
118/// (`≢ ±1`), then `gcd(a^{r/2} ± 1, n)` is a proper factor. `None` when the order is odd or the root is
119/// trivial (`±1`) — the ~50% of the time a fresh `a` is needed.
120pub fn factor_from_order(a: &BigInt, r: u64, n: &BigInt) -> Option<BigInt> {
121 if r % 2 != 0 {
122 return None;
123 }
124 let one = i(1);
125 let root = modpow(a, &i((r / 2) as i64), n); // a^{r/2} mod n
126 if root == one || root == n.sub(&one) {
127 return None; // a^{r/2} ≡ ±1 — no information
128 }
129 for cand in [root.sub(&one), root.add(&one)] {
130 let g = gcd(&cand, n);
131 if g != one && g != *n {
132 return Some(g);
133 }
134 }
135 None
136}
137
138/// **Factoring via order-finding** — the classical shell of Shor's algorithm. Draw bases `a`, find each
139/// order (bounded by `bound`), and split `n` when the order is even with a nontrivial root. `None` if no
140/// trial succeeded within `tries`/`bound`. Classically `O(√order)` per base (exponential in bit length);
141/// this is exactly the step Shor's quantum Fourier transform makes polynomial.
142pub fn factor_via_order(n: &BigInt, tries: usize, bound: u64, seed: u64) -> Option<BigInt> {
143 let one = i(1);
144 if !n.is_odd() {
145 return Some(i(2));
146 }
147 for t in 0..tries {
148 let a_u = 2 + seed.wrapping_add(t as u64).wrapping_mul(2_654_435_761) % 1_000_000;
149 let a = rem_pos(&i(a_u as i64), n);
150 if a == one || a.is_zero() {
151 continue;
152 }
153 // A base sharing a factor with n hands it over directly (the lucky case).
154 let g = gcd(&a, n);
155 if g != one && g != *n {
156 return Some(g);
157 }
158 if let Some(r) = multiplicative_order(&a, n, bound) {
159 if let Some(f) = factor_from_order(&a, r, n) {
160 return Some(f);
161 }
162 }
163 }
164 None
165}
166
167#[cfg(test)]
168#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/period/tests.rs"]
169mod tests;