layer_crypto/
factorize.rs

1//! Pollard-rho (Brent variant) integer factorization — used for PQ step.
2
3fn gcd(mut a: u128, mut b: u128) -> u128 {
4    while b != 0 {
5        let t = b;
6        b = a % b;
7        a = t;
8    }
9    a
10}
11
12fn modpow(mut n: u128, mut e: u128, m: u128) -> u128 {
13    if m == 1 {
14        return 0;
15    }
16    let mut result = 1;
17    n %= m;
18    while e > 0 {
19        if e & 1 == 1 {
20            result = result * n % m;
21        }
22        e >>= 1;
23        n = n * n % m;
24    }
25    result
26}
27
28fn abs_sub(a: u128, b: u128) -> u128 {
29    a.max(b) - a.min(b)
30}
31
32fn factorize_with(pq: u128, c: u128) -> (u64, u64) {
33    if pq.is_multiple_of(2) {
34        return (2, (pq / 2) as u64);
35    }
36
37    let mut y = 3 * (pq / 7);
38    let m = 7 * (pq / 13);
39    let mut g = 1u128;
40    let mut r = 1u128;
41    let mut q = 1u128;
42    let mut x = 0u128;
43    let mut ys = 0u128;
44
45    while g == 1 {
46        x = y;
47        for _ in 0..r {
48            y = (modpow(y, 2, pq) + c) % pq;
49        }
50        let mut k = 0;
51        while k < r && g == 1 {
52            ys = y;
53            for _ in 0..m.min(r - k) {
54                y = (modpow(y, 2, pq) + c) % pq;
55                q = q * abs_sub(x, y) % pq;
56            }
57            g = gcd(q, pq);
58            k += m;
59        }
60        r *= 2;
61    }
62
63    if g == pq {
64        loop {
65            ys = (modpow(ys, 2, pq) + c) % pq;
66            g = gcd(abs_sub(x, ys), pq);
67            if g > 1 {
68                break;
69            }
70        }
71    }
72
73    let p = g as u64;
74    let q = (pq / g) as u64;
75    (p.min(q), p.max(q))
76}
77
78/// Factorize `pq` into two prime factors `(p, q)` where `p ≤ q`.
79pub fn factorize(pq: u64) -> (u64, u64) {
80    let n = pq as u128;
81    for attempt in [43u128, 47, 53, 59, 61] {
82        let c = attempt * (n / 103);
83        let (p, q) = factorize_with(n, c);
84        if p != 1 {
85            return (p, q);
86        }
87    }
88    panic!("factorize failed after fixed attempts");
89}
90
91#[cfg(test)]
92mod tests {
93    use super::*;
94    #[test]
95    fn t1() {
96        assert_eq!(factorize(1470626929934143021), (1206429347, 1218991343));
97    }
98    #[test]
99    fn t2() {
100        assert_eq!(factorize(2363612107535801713), (1518968219, 1556064227));
101    }
102}
layer_crypto/factorize.rs

layer_crypto/
factorize.rs
