competitive_library/math/
miller_rabin.rs

1use crate::math::mod_pow::modpow;
2use crate::other::xorshift::XorShift;
3
4pub fn is_prime(n: i64) -> bool {
5    if n == 2 || n == 3 {
6        return true;
7    } else if n == 1 || (n > 2 && n & 1 == 0) {
8        return false;
9    }
10
11    let (mut s, mut t) = (0, n - 1);
12
13    while t & 1 == 0 {
14        s += 1;
15        t >>= 1;
16    }
17
18    let r = {
19        let mut r = XorShift::<u64>::new().next().unwrap() as i64 % (n - 3);
20        r += 2;
21        r
22    };
23
24    if modpow(r, t, n) == 1 {
25        return true;
26    }
27
28    for i in 0..s {
29        if modpow(r, 2_i64.pow(i) * t, n) == n - 1 {
30            return true;
31        }
32    }
33
34    false
35}
36
37#[cfg(test)]
38mod tests {
39
40    use super::*;
41    #[test]
42    fn test_miller_rabin() {
43        let v = vec![
44            (1, false),
45            (2, true),
46            (3, true),
47            (4, false),
48            (5, true),
49            (6, false),
50            (7, true),
51            (8, false),
52            (9, false),
53            (10, false),
54            (11, true),
55            (1_000_000_007, true),
56            (8191, true),
57            (131_071, true),
58            (524_287, true),
59            (6_700_417, true),
60            (2_147_483_647, true),
61            (67_280_421_310_721, true),
62            (67_280_421_310_722, false),
63            (100_000_000_000_000, false),
64            (68_718_297_093, false), // 131071 * 524287
65        ];
66        for (i, ans) in v {
67            assert_eq!(is_prime(i), ans, "testing {}", i);
68        }
69    }
70    #[test]
71    fn test_miller_rabin_loop() {
72        for _ in 0..100 {
73            test_miller_rabin();
74        }
75    }
76}
competitive_library/math/miller_rabin.rs

competitive_library/math/
miller_rabin.rs
