layer_crypto/
factorize.rs

1// Copyright (c) Ankit Chaubey <ankitchaubey.dev@gmail.com>
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4// NOTE:
5// The "Layer" project is no longer maintained or supported.
6// Its original purpose for personal SDK/APK experimentation and learning
7// has been fulfilled.
8//
9// Please use Ferogram instead:
10// https://github.com/ankit-chaubey/ferogram
11// Ferogram will receive future updates and development, although progress
12// may be slower.
13//
14// Ferogram is an async Telegram MTProto client library written in Rust.
15// Its implementation follows the behaviour of the official Telegram clients,
16// particularly Telegram Desktop and TDLib, and aims to provide a clean and
17// modern async interface for building Telegram clients and tools.
18
19//! Pollard-rho (Brent variant) integer factorization: used for PQ step.
20
21fn gcd(mut a: u128, mut b: u128) -> u128 {
22    while b != 0 {
23        let t = b;
24        b = a % b;
25        a = t;
26    }
27    a
28}
29
30fn modpow(mut n: u128, mut e: u128, m: u128) -> u128 {
31    if m == 1 {
32        return 0;
33    }
34    let mut result = 1;
35    n %= m;
36    while e > 0 {
37        if e & 1 == 1 {
38            result = result * n % m;
39        }
40        e >>= 1;
41        n = n * n % m;
42    }
43    result
44}
45
46fn abs_sub(a: u128, b: u128) -> u128 {
47    a.max(b) - a.min(b)
48}
49
50fn factorize_with(pq: u128, c: u128) -> (u64, u64) {
51    if pq.is_multiple_of(2) {
52        return (2, (pq / 2) as u64);
53    }
54
55    let mut y = 3 * (pq / 7);
56    let m = 7 * (pq / 13);
57    let mut g = 1u128;
58    let mut r = 1u128;
59    let mut q = 1u128;
60    let mut x = 0u128;
61    let mut ys = 0u128;
62
63    while g == 1 {
64        x = y;
65        for _ in 0..r {
66            y = (modpow(y, 2, pq) + c) % pq;
67        }
68        let mut k = 0;
69        while k < r && g == 1 {
70            ys = y;
71            for _ in 0..m.min(r - k) {
72                y = (modpow(y, 2, pq) + c) % pq;
73                q = q * abs_sub(x, y) % pq;
74            }
75            g = gcd(q, pq);
76            k += m;
77        }
78        r *= 2;
79    }
80
81    if g == pq {
82        loop {
83            ys = (modpow(ys, 2, pq) + c) % pq;
84            g = gcd(abs_sub(x, ys), pq);
85            if g > 1 {
86                break;
87            }
88        }
89    }
90
91    let p = g as u64;
92    let q = (pq / g) as u64;
93    (p.min(q), p.max(q))
94}
95
96/// Factorize `pq` into two prime factors `(p, q)` where `p ≤ q`.
97pub fn factorize(pq: u64) -> (u64, u64) {
98    let n = pq as u128;
99    for attempt in [43u128, 47, 53, 59, 61] {
100        let c = attempt * (n / 103);
101        let (p, q) = factorize_with(n, c);
102        if p != 1 {
103            return (p, q);
104        }
105    }
106    panic!("factorize failed after fixed attempts");
107}
108
109#[cfg(test)]
110mod tests {
111    use super::*;
112    #[test]
113    fn t1() {
114        assert_eq!(factorize(1470626929934143021), (1206429347, 1218991343));
115    }
116    #[test]
117    fn t2() {
118        assert_eq!(factorize(2363612107535801713), (1518968219, 1556064227));
119    }
120}
layer_crypto/factorize.rs

layer_crypto/
factorize.rs
