-
Notifications
You must be signed in to change notification settings - Fork 0
/
miller_rabin_primality_test.rs
52 lines (47 loc) · 1.38 KB
/
miller_rabin_primality_test.rs
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
use super::modpow::*;
use rand::Rng;
type U = u128;
/// Miller-Rabin primality test.
/// modmul is late, so it should not be used in this function.
pub fn miller_rabin_primality_test(n: U, iteration: Option<usize>) -> bool {
let iteration = iteration.unwrap_or(5);
if n < 2 {
return false;
}
if n == 2 {
return true;
}
if n % 2 == 0 {
return false;
}
let mut rng = rand::thread_rng();
let mut d = n - 1;
while d % 2 == 0 {
d /= 2;
}
for _ in 0..iteration {
let a = rng.gen::<U>() % (n - 1) + 1;
let mut t = d;
let mut m = modpow(a, t, n);
while t != n - 1 && m != 1 && m != n - 1 {
m = m * m % n;
t *= 2;
}
if m != n - 1 && t % 2 == 0 {
return false;
}
}
true
}
#[test]
fn test() {
assert_eq!(miller_rabin_primality_test(1, None), false);
assert_eq!(miller_rabin_primality_test(2, None), true);
assert_eq!(miller_rabin_primality_test(3, None), true);
assert_eq!(miller_rabin_primality_test(4, None), false);
assert_eq!(miller_rabin_primality_test(5, None), true);
assert_eq!(miller_rabin_primality_test(6, None), false);
assert_eq!(miller_rabin_primality_test(7, None), true);
assert_eq!(miller_rabin_primality_test(8, None), false);
assert_eq!(miller_rabin_primality_test(9, None), false);
}