haar_lib/math/prime_test/
miller_rabin.rs

1//! Miller-Rabin素数判定法
2pub use crate::math::prime_test::CheckPrime;
3
4fn pow(mut a: u128, mut b: u128, p: u128) -> u128 {
5    let mut ret = 1;
6
7    while b > 0 {
8        if b & 1 == 1 {
9            ret = ret * a % p;
10        }
11        a = a * a % p;
12        b >>= 1;
13    }
14
15    ret
16}
17
18fn is_composite(a: u64, p: u64, s: u64, d: u64) -> bool {
19    let p = p as u128;
20    let mut x = pow(a as u128, d as u128, p);
21
22    if x == 1 {
23        false
24    } else {
25        for _ in 0..s {
26            if x == p - 1 {
27                return false;
28            }
29            x = x * x % p;
30        }
31
32        true
33    }
34}
35
36/// Miller-Rabin素数判定法
37pub struct MillerRabin;
38
39impl CheckPrime<u64> for MillerRabin {
40    fn is_prime(&self, n: u64) -> bool {
41        if n <= 1 {
42            false
43        } else if n == 2 {
44            true
45        } else if n % 2 == 0 {
46            false
47        } else {
48            let mut s = 0;
49            let mut d = n - 1;
50            while d & 1 == 0 {
51                s += 1;
52                d >>= 1;
53            }
54
55            if n < 4_759_123_141 {
56                for &x in &[2, 7, 61] {
57                    if x < n && is_composite(x, n, s, d) {
58                        return false;
59                    }
60                }
61
62                true
63            } else {
64                for &x in &[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] {
65                    if x < n && is_composite(x, n, s, d) {
66                        return false;
67                    }
68                }
69
70                true
71            }
72        }
73    }
74}
haar_lib/math/prime_test/miller_rabin.rs

haar_lib/math/prime_test/
miller_rabin.rs
