const_primes/
check.rs

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

const_primes/
check.rs
