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

layer_crypto/
factorize.rs
