ferogram_crypto/
factorize.rs

1// Copyright (c) Ankit Chaubey <ankitchaubey.dev@gmail.com>
2//
3// ferogram: async Telegram MTProto client in Rust
4// https://github.com/ankit-chaubey/ferogram
5//
6// Licensed under either the MIT License or the Apache License 2.0.
7// See the LICENSE-MIT or LICENSE-APACHE file in this repository:
8// https://github.com/ankit-chaubey/ferogram
9//
10// Feel free to use, modify, and share this code.
11// Please keep this notice when redistributing.
12
13fn gcd(mut a: u128, mut b: u128) -> u128 {
14    while b != 0 {
15        let t = b;
16        b = a % b;
17        a = t;
18    }
19    a
20}
21
22fn modpow(mut n: u128, mut e: u128, m: u128) -> u128 {
23    if m == 1 {
24        return 0;
25    }
26    let mut result = 1;
27    n %= m;
28    while e > 0 {
29        if e & 1 == 1 {
30            result = result * n % m;
31        }
32        e >>= 1;
33        n = n * n % m;
34    }
35    result
36}
37
38fn abs_sub(a: u128, b: u128) -> u128 {
39    a.max(b) - a.min(b)
40}
41
42fn factorize_with(pq: u128, c: u128) -> (u64, u64) {
43    if pq.is_multiple_of(2) {
44        return (2, (pq / 2) as u64);
45    }
46
47    let mut y = 3 * (pq / 7);
48    let m = 7 * (pq / 13);
49    let mut g = 1u128;
50    let mut r = 1u128;
51    let mut q = 1u128;
52    let mut x = 0u128;
53    let mut ys = 0u128;
54
55    while g == 1 {
56        x = y;
57        for _ in 0..r {
58            y = (modpow(y, 2, pq) + c) % pq;
59        }
60        let mut k = 0;
61        while k < r && g == 1 {
62            ys = y;
63            for _ in 0..m.min(r - k) {
64                y = (modpow(y, 2, pq) + c) % pq;
65                q = q * abs_sub(x, y) % pq;
66            }
67            g = gcd(q, pq);
68            k += m;
69        }
70        r *= 2;
71    }
72
73    if g == pq {
74        loop {
75            ys = (modpow(ys, 2, pq) + c) % pq;
76            g = gcd(abs_sub(x, ys), pq);
77            if g > 1 {
78                break;
79            }
80        }
81    }
82
83    let p = g as u64;
84    let q = (pq / g) as u64;
85    (p.min(q), p.max(q))
86}
87
88/// Factorize `pq` into two prime factors `(p, q)` where `p ≤ q`.
89pub fn factorize(pq: u64) -> (u64, u64) {
90    let n = pq as u128;
91    for attempt in [43u128, 47, 53, 59, 61] {
92        let c = attempt * (n / 103);
93        let (p, q) = factorize_with(n, c);
94        if p != 1 {
95            return (p, q);
96        }
97    }
98    panic!("factorize failed after fixed attempts");
99}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104    #[test]
105    fn t1() {
106        assert_eq!(factorize(1470626929934143021), (1206429347, 1218991343));
107    }
108    #[test]
109    fn t2() {
110        assert_eq!(factorize(2363612107535801713), (1518968219, 1556064227));
111    }
112}
ferogram_crypto/factorize.rs

ferogram_crypto/
factorize.rs
