ferogram_crypto/
factorize.rs

1/*
2 * Copyright (c) 2026 Ankit Chaubey <ankitchaubey.dev@gmail.com>
3 * https://github.com/ankit-chaubey
4 *
5 * Project: ferogram
6 * Website: https://ferogram.dev
7 *
8 * Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
9 * https://www.apache.org/licenses/LICENSE-2.0> or the MIT license
10 * <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your option.
11 * This file may not be copied, modified, or distributed except according
12 * to those terms.
13 */
14
15fn gcd(mut a: u128, mut b: u128) -> u128 {
16    while b != 0 {
17        let t = b;
18        b = a % b;
19        a = t;
20    }
21    a
22}
23
24fn modpow(mut n: u128, mut e: u128, m: u128) -> u128 {
25    if m == 1 {
26        return 0;
27    }
28    let mut result = 1;
29    n %= m;
30    while e > 0 {
31        if e & 1 == 1 {
32            result = result * n % m;
33        }
34        e >>= 1;
35        n = n * n % m;
36    }
37    result
38}
39
40fn abs_sub(a: u128, b: u128) -> u128 {
41    a.max(b) - a.min(b)
42}
43
44fn factorize_with(pq: u128, c: u128) -> (u64, u64) {
45    if pq.is_multiple_of(2) {
46        return (2, (pq / 2) as u64);
47    }
48
49    let mut y = 3 * (pq / 7);
50    let m = 7 * (pq / 13);
51    let mut g = 1u128;
52    let mut r = 1u128;
53    let mut q = 1u128;
54    let mut x = 0u128;
55    let mut ys = 0u128;
56
57    while g == 1 {
58        x = y;
59        for _ in 0..r {
60            y = (modpow(y, 2, pq) + c) % pq;
61        }
62        let mut k = 0;
63        while k < r && g == 1 {
64            ys = y;
65            for _ in 0..m.min(r - k) {
66                y = (modpow(y, 2, pq) + c) % pq;
67                q = q * abs_sub(x, y) % pq;
68            }
69            g = gcd(q, pq);
70            k += m;
71        }
72        r *= 2;
73    }
74
75    if g == pq {
76        loop {
77            ys = (modpow(ys, 2, pq) + c) % pq;
78            g = gcd(abs_sub(x, ys), pq);
79            if g > 1 {
80                break;
81            }
82        }
83    }
84
85    let p = g as u64;
86    let q = (pq / g) as u64;
87    (p.min(q), p.max(q))
88}
89
90/// Factorize `pq` into two prime factors `(p, q)` where `p ≤ q`.
91///
92/// Returns `None` if `pq` isn't a semiprime this routine can factor within
93/// the fixed attempt budget (e.g. a malformed or adversarial value from a
94/// server). Callers on a security-sensitive path (auth key exchange) must
95/// treat that as a protocol error, not panic.
96pub fn factorize(pq: u64) -> Option<(u64, u64)> {
97    let n = pq as u128;
98    for attempt in [43u128, 47, 53, 59, 61] {
99        let c = attempt * (n / 103);
100        let (p, q) = factorize_with(n, c);
101        if p != 1 {
102            return Some((p, q));
103        }
104    }
105    None
106}
107
108#[cfg(test)]
109mod tests {
110    use super::*;
111    #[test]
112    fn t1() {
113        assert_eq!(
114            factorize(1470626929934143021),
115            Some((1206429347, 1218991343))
116        );
117    }
118    #[test]
119    fn t2() {
120        assert_eq!(
121            factorize(2363612107535801713),
122            Some((1518968219, 1556064227))
123        );
124    }
125}
ferogram_crypto/factorize.rs

ferogram_crypto/
factorize.rs
