Function num_prime::factor::pollard_rho

source · 
pub fn pollard_rho<T: Integer + FromPrimitive + NumRef + Clone + for<'r> ModularCoreOps<&'r T, &'r T, Output = T> + for<'r> ModularUnaryOps<&'r T, Output = T>>(
    target: &T,
    start: T,
    offset: T,
    max_iter: usize
) -> (Option<T>, usize)
where
    for<'r> &'r T: RefNum<T>,
Expand description

Find factors using Pollard’s rho algorithm with Brent’s loop detection algorithm

The returned values are the factor and the count of passed iterations.

Examples found in repository?
examples/profile_factorization.rs (line 22)
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

fn profile_n(n: u128) -> Vec<(String, usize)> {
    let k_squfof: Vec<u16> = SQUFOF_MULTIPLIERS.iter().take(10).cloned().collect();
    let k_oneline: Vec<u16> = vec![1, 360, 480];
    const MAXITER: usize = 1 << 20;
    const POLLARD_REPEATS: usize = 2;

    let mut n_stats = Vec::new();

    // pollard rho
    for i in 0..POLLARD_REPEATS {
        n_stats.push((
            format!("pollard_rho{}", i + 1),
            pollard_rho(&n, random(), random(), MAXITER).1,
        ));
    }

    // squfof
    for &k in &k_squfof {
        let key = format!("squfof_k{}", k);
        if let Some(kn) = n.checked_mul(k as u128) {
            let n = squfof(&n, kn, MAXITER).1;
            n_stats.push((key, n));
        } else {
            n_stats.push((key, MAXITER));
        };
    }

    // one line
    for &k in &k_oneline {
        let key = format!("one_line_k{}", k);
        if let Some(kn) = n.checked_mul(k as u128) {
            let n = one_line(&n, kn, MAXITER).1;
            n_stats.push((key, n));
        } else {
            n_stats.push((key, MAXITER));
        };
    }

    n_stats
}

/// Collect the best case of each factorization algorithm
fn profile_n_min(n: u128) -> Vec<(String, usize)> {
    let k_squfof: Vec<u16> = SQUFOF_MULTIPLIERS.iter().cloned().collect();
    let k_oneline: Vec<u16> = vec![1, 360, 480];
    const MAXITER: usize = 1 << 24;
    const POLLARD_REPEATS: usize = 4;

    let mut n_stats = Vec::new();

    // pollard rho
    let mut pollard_best = (MAXITER, u128::MAX);
    for _ in 0..POLLARD_REPEATS {
        let tstart = Instant::now();
        let (result, iters) = pollard_rho(&n, random(), random(), pollard_best.0);
        if result.is_some() {
            pollard_best = pollard_best.min((iters, tstart.elapsed().as_micros()));
        }
    }
    n_stats.push(("pollard_rho".to_string(), pollard_best.0));
    n_stats.push(("time_pollard_rho".to_string(), pollard_best.1 as usize));

    // squfof
    let mut squfof_best = (MAXITER, u128::MAX);
    for &k in &k_squfof {
        if let Some(kn) = n.checked_mul(k as u128) {
            let tstart = Instant::now();
            let (result, iters) = squfof(&n, kn, squfof_best.0);
            if result.is_some() {
                squfof_best = squfof_best.min((iters, tstart.elapsed().as_micros()));
            }
        }
    }
    n_stats.push(("squfof".to_string(), squfof_best.0));
    n_stats.push(("time_squfof".to_string(), squfof_best.1 as usize));

    // one line
    let mut oneline_best = (MAXITER, u128::MAX);
    for &k in &k_oneline {
        if let Some(kn) = n.checked_mul(k as u128) {
            let tstart = Instant::now();
            let (result, iters) = one_line(&n, kn, oneline_best.0);
            if result.is_some() {
                oneline_best = oneline_best.min((iters, tstart.elapsed().as_micros()));
            }
        }
    }
    n_stats.push(("one_line".to_string(), oneline_best.0));
    n_stats.push(("time_one_line".to_string(), squfof_best.1 as usize));

    n_stats
}