nums/
pollard_rho.rs

1use crate::CompositeSplitter;
2use num_bigint::BigUint;
3use num_integer::{gcd, Integer};
4use num_traits::{CheckedSub, One};
5
6pub struct PollardRho;
7
8impl CompositeSplitter for PollardRho {
9    fn divisor(&self, n: &BigUint) -> BigUint {
10        if n.is_even() {
11            return BigUint::from(2u8);
12        }
13
14        let mut addend = BigUint::from(1u8);
15        loop {
16            if let Some(d) = pollard_rho_attempt(n, &addend) {
17                return d;
18            }
19            addend.inc();
20            if &addend == n {
21                panic!("oop");
22            }
23        }
24    }
25}
26
27fn pollard_rho_attempt(n: &BigUint, addend: &BigUint) -> Option<BigUint> {
28    let start = BigUint::from(2u8);
29    let mut x = start.clone();
30    let mut y = start.clone();
31
32    let g = |x: &BigUint| (x * x + addend) % n;
33
34    loop {
35        x = g(&x);
36        y = g(&g(&y));
37        let d = gcd(distance(&x, &y), n.clone());
38
39        if &d == n {
40            return None; // failure
41        }
42        if !d.is_one() {
43            return Some(d);
44        }
45    }
46}
47
48fn distance(x: &BigUint, y: &BigUint) -> BigUint {
49    x.checked_sub(y).unwrap_or_else(|| y - x)
50}
51
52#[cfg(test)]
53mod tests {
54    use crate::{Factorizer, FactorizerFromSplitter, MillerRabin, PollardRho};
55    use alloc::vec;
56    use core::str::FromStr;
57    use num_bigint::BigUint;
58
59    #[test]
60    fn baby_bear_ext5() {
61        // This n is the order of the multiplicative group of BabyBear^5.
62        let n = BigUint::from_str("33075446146858977625031769923874103810955673600").unwrap();
63        let primality_test = MillerRabin { error_bits: 128 };
64        let res_pollard_rho = FactorizerFromSplitter {
65            primality_test,
66            composite_splitter: PollardRho,
67        }
68        .factor_counts(&n);
69        assert_eq!(
70            res_pollard_rho,
71            vec![
72                (BigUint::from(2u8), 27),
73                (BigUint::from(3u8), 1),
74                (BigUint::from(5u8), 2),
75                (BigUint::from(26321u16), 1),
76                (BigUint::from(1081891u32), 1),
77                (BigUint::from(115384818561587951104978331u128), 1),
78            ]
79        );
80    }
81}