1
2
3
4
5
6
7
8
9
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
use std::fs::File;
use std::io::{Error, Write};
use std::time::Instant;
use num_prime::factor::{one_line, pollard_rho, squfof, SQUFOF_MULTIPLIERS};
use num_prime::RandPrime;
use rand::random;
/// Collect the the iteration number of each factorization algorithm with different settings
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
}
/// This program try various factorization methods, and log down their iterations number into a csv file
fn main() -> Result<(), Error> {
let mut rng = rand::thread_rng();
const REPEATS: u32 = 4;
let mut n_list = Vec::<(u128, f32)>::new(); // n and bits of n
let mut stats: Vec<Vec<(String, usize)>> = Vec::new();
for total_bits in 20..120 {
for _ in 0..REPEATS {
let p1: u128 = rng.gen_prime(total_bits / 2, None);
let p2: u128 =
rng.gen_prime_exact(total_bits - (128 - p1.leading_zeros()) as usize, None);
if p1 == p2 {
continue;
}
let n = p1 * p2;
n_list.push((n, (n as f64).log2() as f32));
println!("Semiprime ({}bits): {} = {} * {}", total_bits, n, p1, p2);
// stats.push(profile_n(n));
stats.push(profile_n_min(n));
}
}
// Log into the CSV file
let mut fout = File::create("profile_stats.csv")?;
fout.write(b"n,n_bits")?;
for k in stats[0].iter().map(|(k, _)| k) {
fout.write(b",")?;
fout.write(k.as_bytes())?;
}
for ((n, bits), n_stats) in n_list.iter().zip(stats) {
fout.write(b"\n")?;
fout.write(n.to_string().as_bytes())?;
fout.write(b",")?;
fout.write(bits.to_string().as_bytes())?;
for (_, v) in n_stats {
fout.write(b",")?;
fout.write(v.to_string().as_bytes())?;
}
}
Ok(())
}
|
