const_primes/
check.rs

1//! This module contains an implementation of a deterministic Miller-Rabin primality test
2
3#[cfg(not(feature = "fast_test"))]
4use crate::integer_math::{mod_mul, mod_pow};
5
6/// Returns whether `n` is prime.
7///
8/// Does trial division with a small wheel up to `log2(n)` and then uses a
9/// deterministic Miller-Rabin primality test.
10///
11/// If the `fast_test` feature is enabled this function calls the [`machine_prime::is_prime`] function with the `lucas` feature instead.
12///
13/// # Example
14///
15/// Basic usage:
16///
17/// ```
18/// # use const_primes::is_prime;
19/// const CHECK: bool = is_prime(18_446_744_073_709_551_557);
20/// assert!(CHECK);
21/// ```
22#[must_use]
23pub const fn is_prime(n: u64) -> bool {
24    #[cfg(feature = "fast_test")]
25    {
26        machine_prime::is_prime(n)
27    }
28
29    #[cfg(not(feature = "fast_test"))]
30    {
31        // Since we know the maximum size of the numbers we test against
32        // we can use the fact that there are known perfect bases
33        // in order to make the test both fast and deterministic.
34        // This list of witnesses was taken from
35        // <https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases>.
36        const NUM_BASES: usize = 11;
37        const WITNESSES: [(u64, &[u64]); NUM_BASES] = [
38            (2_046, &[2]),
39            (1_373_652, &[2, 3]),
40            (9_080_190, &[31, 73]),
41            (25_326_000, &[2, 3, 5]),
42            (4_759_123_140, &[2, 7, 61]),
43            (1_112_004_669_632, &[2, 13, 23, 1_662_803]),
44            (2_152_302_898_746, &[2, 3, 5, 7, 11]),
45            (3_474_749_660_382, &[2, 3, 5, 7, 11, 13]),
46            (341_550_071_728_320, &[2, 3, 5, 7, 11, 13, 17]),
47            (3_825_123_056_546_413_050, &[2, 3, 5, 7, 11, 13, 17, 19, 23]),
48            (u64::MAX, &[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]),
49        ];
50
51        if n == 2 || n == 3 {
52            return true;
53        } else if n <= 1 || n % 2 == 0 || n % 3 == 0 {
54            return false;
55        }
56
57        // Use a small wheel to check up to log2(n).
58        // This keeps the complexity at O(log(n)).
59        let mut candidate_factor = 5;
60        let trial_limit = n.ilog2() as u64;
61        while candidate_factor <= trial_limit {
62            if n % candidate_factor == 0 || n % (candidate_factor + 2) == 0 {
63                return false;
64            }
65            candidate_factor += 6;
66        }
67
68        // Find r such that n = 2^d * r + 1 for some r >= 1
69        let mut d = n - 1;
70        while d % 2 == 0 {
71            d >>= 1;
72        }
73
74        let mut i = 0;
75        while i < NUM_BASES && WITNESSES[i].0 < n {
76            i += 1;
77        }
78        let witnesses = WITNESSES[i].1;
79
80        let mut i = 0;
81        while i < witnesses.len() && witnesses[i] < n {
82            if !miller_test(d, n, witnesses[i]) {
83                return false;
84            }
85            i += 1;
86        }
87
88        true
89    }
90}
91
92#[cfg(not(feature = "fast_test"))]
93/// Performs a Miller-Rabin test with the witness k.
94const fn miller_test(mut d: u64, n: u64, k: u64) -> bool {
95    let mut x = mod_pow(k, d, n);
96    if x == 1 || x == n - 1 {
97        return true;
98    }
99
100    while d != n - 1 {
101        x = mod_mul(x, x, n);
102        d *= 2;
103
104        if x == 1 {
105            return false;
106        } else if x == n - 1 {
107            return true;
108        }
109    }
110
111    false
112}
113
114#[cfg(test)]
115mod test {
116    use super::is_prime;
117
118    #[test]
119    fn check_is_prime() {
120        // region: test data
121        #[rustfmt::skip]
122        const TEST_CASES: [bool; 100] = [false, false, true, true, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false];
123        // endregion: test data
124        for (x, ans) in TEST_CASES.into_iter().enumerate() {
125            assert_eq!(is_prime(x as u64), ans);
126        }
127        assert!(is_prime(65_521));
128        assert!(is_prime(4_294_967_291));
129        assert!(is_prime(18_446_744_073_709_551_557));
130        assert!(is_prime(3_474_749_660_401));
131        assert!(is_prime(2_039));
132        assert!(is_prime(1_373_639));
133        assert!(is_prime(9_080_189));
134        assert!(is_prime(25_325_981));
135        assert!(is_prime(4_759_123_129));
136        assert!(is_prime(1_112_004_669_631));
137        assert!(is_prime(2_152_302_898_729));
138        assert!(is_prime(3_474_749_660_329));
139        assert!(is_prime(341_550_071_728_289));
140        assert!(is_prime(3_825_123_056_546_412_979));
141    }
142}
const_primes/check.rs

const_primes/
check.rs
