cp_library_rs/number_theory/
pollard_rho_algorithm.rs

1//! ポラード・ロー法による素因数分解
2
3use crate::number_theory::miller_rabin_test::is_prime_MR;
4
5fn gcd(a: usize, b: usize) -> usize {
6    if b == 0 {
7        a
8    } else {
9        gcd(b, a % b)
10    }
11}
12
13/// ポラード・ロー法を適用し、約数を見つける
14pub fn pollard_rho(N: usize) -> usize {
15    if N % 2 == 0 {
16        return 2;
17    }
18    if is_prime_MR(N) {
19        return N;
20    }
21    let tmp = &mut 0;
22    let f =
23        |x: usize, tmp: &mut u128| -> usize { (((x as u128).pow(2) + *tmp) % N as u128) as usize };
24    let mut step = 0;
25    loop {
26        *tmp += 1;
27        step += 1;
28        let mut x = step;
29        let mut y = f(x, tmp);
30        loop {
31            let p = gcd(N + y - x, N);
32            if p == 0 || p == N {
33                break;
34            }
35            if p != 1 {
36                return p;
37            }
38            x = f(x, tmp);
39            y = f(f(y, tmp), tmp);
40        }
41    }
42}
43
44/// ポラード・ロー法により素因数分解を行う
45///
46/// - 時間計算量: $`O(n^{1/4})`$
47pub fn factorize_pollard_rho(N: usize) -> Vec<usize> {
48    if N == 1 {
49        return vec![];
50    }
51    let p = pollard_rho(N);
52    if p == N {
53        return vec![N];
54    }
55    let mut left = factorize_pollard_rho(p);
56    let mut right = factorize_pollard_rho(N / p);
57    left.append(&mut right);
58    left.sort();
59    left
60}
cp_library_rs/number_theory/pollard_rho_algorithm.rs

cp_library_rs/number_theory/
pollard_rho_algorithm.rs
