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

ferogram_crypto/
factorize.rs
