Skip to main content

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;