Function num_prime::factor::one_line

source · 
pub fn one_line<T: Integer + NumRef + FromPrimitive + ExactRoots + CheckedAdd>(
    target: &T,
    mul_target: T,
    max_iter: usize
) -> (Option<T>, usize)
where
    for<'r> &'r T: RefNum<T>,
Expand description

William Hart’s one line factorization algorithm for 64 bit integers.

The number to be factored could be multiplied by a smooth number (coprime to the target) to speed up, put the multiplied number in the mul_target argument. A good multiplier given by Hart is 480. iters determine the range for iterating the inner multiplier itself. The returned values are the factor and the count of passed iterations.

The one line factorization algorithm is especially good at factoring semiprimes with form pq, where p = next_prime(c^a+d1), p = next_prime(c^b+d2), a and b are close, and c, d1, d2 are small integers.

Reference: Hart, W. B. (2012). A one line factoring algorithm. Journal of the Australian Mathematical Society, 92(1), 61-69. doi:10.1017/S1446788712000146

Examples found in repository?
examples/profile_factorization.rs (line 41)
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
}