nums/
miller_rabin.rs

1use crate::traits::PrimalityTest;
2use num_bigint::{BigUint, RandBigInt};
3use num_traits::{One, Zero};
4
5/// The Miller-Rabin primality test.
6///
7/// This is a probabilistic test, but can be configured to have a cryptographically small error
8/// margin.
9pub struct MillerRabin {
10    pub error_bits: usize,
11}
12
13impl PrimalityTest for MillerRabin {
14    fn is_prime(&self, n: &BigUint) -> bool {
15        if n.is_zero() || n.is_one() {
16            return false;
17        }
18
19        let one = BigUint::one();
20        let two = BigUint::from(2u8);
21        let mut rng = rand::thread_rng();
22
23        // Decompose n - 1 into 2^s d by splitting off factors of two.
24        let n_minus_1 = n - &one;
25        let s = n_minus_1.trailing_zeros().unwrap();
26        let d = &n_minus_1 >> s;
27
28        let num_bases = (self.error_bits + 1) / 2;
29        'base_search: for _ in 0..num_bases {
30            let base = rng.gen_biguint_range(&one, &n);
31
32            // Let x = 2^d mod n.
33            let x = base.modpow(&d, &n);
34            if x.is_one() {
35                continue; // pass
36            }
37
38            // Use iterative squaring to check if x^(2^r) == n - 1 for some r < s.
39            let mut square = x;
40            if square == n_minus_1 {
41                continue; // pass with r = 0
42            }
43            for _r in 1..s {
44                square = square.modpow(&two, &n);
45                if square == n_minus_1 {
46                    continue 'base_search; // pass
47                }
48            }
49            return false; // failed; composite detected
50        }
51        true
52    }
53}