pub fn one_line<T: Integer + NumRef + FromPrimitive + ExactRoots + CheckedAdd>(
target: &T,
mul_target: T,
max_iter: usize,
) -> (Option<T>, usize)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?
10fn profile_n(n: u128) -> Vec<(String, usize)> {
11 let k_squfof: Vec<u16> = SQUFOF_MULTIPLIERS.iter().take(10).cloned().collect();
12 let k_oneline: Vec<u16> = vec![1, 360, 480];
13 const MAXITER: usize = 1 << 20;
14 const POLLARD_REPEATS: usize = 2;
15
16 let mut n_stats = Vec::new();
17
18 // pollard rho
19 for i in 0..POLLARD_REPEATS {
20 n_stats.push((
21 format!("pollard_rho{}", i + 1),
22 pollard_rho(&n, random(), random(), MAXITER).1,
23 ));
24 }
25
26 // squfof
27 for &k in &k_squfof {
28 let key = format!("squfof_k{}", k);
29 if let Some(kn) = n.checked_mul(k as u128) {
30 let n = squfof(&n, kn, MAXITER).1;
31 n_stats.push((key, n));
32 } else {
33 n_stats.push((key, MAXITER));
34 };
35 }
36
37 // one line
38 for &k in &k_oneline {
39 let key = format!("one_line_k{}", k);
40 if let Some(kn) = n.checked_mul(k as u128) {
41 let n = one_line(&n, kn, MAXITER).1;
42 n_stats.push((key, n));
43 } else {
44 n_stats.push((key, MAXITER));
45 };
46 }
47
48 n_stats
49}
50
51/// Collect the best case of each factorization algorithm
52fn profile_n_min(n: u128) -> Vec<(String, usize)> {
53 let k_squfof: Vec<u16> = SQUFOF_MULTIPLIERS.iter().cloned().collect();
54 let k_oneline: Vec<u16> = vec![1, 360, 480];
55 const MAXITER: usize = 1 << 24;
56 const POLLARD_REPEATS: usize = 4;
57
58 let mut n_stats = Vec::new();
59
60 // pollard rho
61 let mut pollard_best = (MAXITER, u128::MAX);
62 for _ in 0..POLLARD_REPEATS {
63 let tstart = Instant::now();
64 let (result, iters) = pollard_rho(&n, random(), random(), pollard_best.0);
65 if result.is_some() {
66 pollard_best = pollard_best.min((iters, tstart.elapsed().as_micros()));
67 }
68 }
69 n_stats.push(("pollard_rho".to_string(), pollard_best.0));
70 n_stats.push(("time_pollard_rho".to_string(), pollard_best.1 as usize));
71
72 // squfof
73 let mut squfof_best = (MAXITER, u128::MAX);
74 for &k in &k_squfof {
75 if let Some(kn) = n.checked_mul(k as u128) {
76 let tstart = Instant::now();
77 let (result, iters) = squfof(&n, kn, squfof_best.0);
78 if result.is_some() {
79 squfof_best = squfof_best.min((iters, tstart.elapsed().as_micros()));
80 }
81 }
82 }
83 n_stats.push(("squfof".to_string(), squfof_best.0));
84 n_stats.push(("time_squfof".to_string(), squfof_best.1 as usize));
85
86 // one line
87 let mut oneline_best = (MAXITER, u128::MAX);
88 for &k in &k_oneline {
89 if let Some(kn) = n.checked_mul(k as u128) {
90 let tstart = Instant::now();
91 let (result, iters) = one_line(&n, kn, oneline_best.0);
92 if result.is_some() {
93 oneline_best = oneline_best.min((iters, tstart.elapsed().as_micros()));
94 }
95 }
96 }
97 n_stats.push(("one_line".to_string(), oneline_best.0));
98 n_stats.push(("time_one_line".to_string(), squfof_best.1 as usize));
99
100 n_stats
101}