ferogram_crypto/
factorize.rs

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

ferogram_crypto/
factorize.rs
