large_primes/primality/
fermat.rs

1use num_bigint::BigUint;
2use num_traits::One;
3use crate::operations::pow_mod;
4use crate::operations::gcd;
5
6/// Performs a probabilistic primality test using Fermat's little theorem.
7///
8/// Fermat's little theorem states that if `p` is a prime number, then for any
9/// integer `a` such that `1 < a < p - 1`, the number `a^(p-1)` is congruent to 1 modulo `p`.
10/// This function tests the primality of `num` using a set of base witnesses (2, 3, 5, 7, 11, 13, 17, 19, 23, 29).
11///
12/// Note that passing this test does not guarantee that `num` is prime, but failing it
13/// guarantees that `num` is composite. Thus, this function can produce false positives,
14/// but not false negatives.
15///
16/// # Arguments
17///
18/// * `num` - A reference to a `BigUint` representing the number to test for primality.
19///
20/// # Returns
21///
22/// * `true` if `num` passes the Fermat primality test for all witnesses.
23/// * `false` if `num` fails the test for any witness, or if `num` is less than or equal to 1.
24///
25/// # Examples
26///
27/// ```
28/// use num_bigint::BigUint;
29/// use large_primes::fermat;
30/// 
31/// let number = BigUint::parse_bytes(b"97", 10).unwrap();
32/// assert!(fermat(&number));
33///
34/// let non_prime = BigUint::parse_bytes(b"100", 10).unwrap();
35/// assert!(!fermat(&non_prime));
36/// ```
37
38pub fn fermat(num: &BigUint) -> bool {
39    // Fermat's little theorem test for witnesses 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
40
41    if *num <= BigUint::one() {
42        return false;
43    }
44
45    let switnesses = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
46    let witnesses: Vec<BigUint> = switnesses
47        .iter()
48        .map(|x| BigUint::from(*x as u32))
49        .collect();
50    for witness in witnesses {
51        if gcd(&witness, num) != BigUint::one() {
52            continue;
53        }
54        let mod_value = pow_mod(&witness, &num, num);
55        let rhs = pow_mod(&witness, &BigUint::one(), &num);
56        if mod_value != rhs {
57            return false;
58        }
59    }
60    return true;
61}
62
63#[cfg(test)]
64mod tests {
65    use num_traits::Zero;
66
67    use super::*;
68
69    #[test]
70    fn edge_cases() {
71        // Test case 0: False
72        assert_eq!(fermat(&BigUint::zero()), false);
73
74        // Test case 1: False
75        assert_eq!(fermat(&BigUint::one()), false);
76
77        // Test case 2: True
78        assert_eq!(fermat(&BigUint::from(2u32)), true);
79
80        // Test case 3: True
81        assert_eq!(fermat(&BigUint::from(3u32)), true);
82
83        // Test case 4: False
84        assert_eq!(fermat(&BigUint::from(4u32)), false);
85    }
86
87    #[test]
88    fn large_primes() {
89        let primes = [
90            // 10-12 digit primes
91            "871603259",
92            "98762051",
93            "1000000007",
94            "123575321",
95            "193818613",
96            "444444443",
97            "999999937",
98            "1000000000039",
99            "9999999929",
100        ];
101
102        for prime in primes {
103            let prime = BigUint::parse_bytes(prime.as_bytes(), 10).unwrap();
104            assert_eq!(fermat(&prime), true);
105        }
106    }
107
108    #[test]
109    fn large_composites() {
110        let primes = [
111            // 10-12 digit primes
112            "871603259",
113            "98762051",
114            "1000000007",
115            "123575321",
116            "193818613",
117            "444444443",
118            "999999937",
119            "1000000000039",
120            "9999999929",
121        ];
122
123        for i in 0..primes.len() {
124            for j in 0..primes.len() {
125                if i == j {
126                    continue;
127                }
128                let composite =
129                    BigUint::parse_bytes(primes[i].as_bytes(), 10).unwrap() *
130                    BigUint::parse_bytes(primes[j].as_bytes(), 10).unwrap();
131                assert_eq!(fermat(&composite), false);
132            }
133        }
134    }
135
136    #[test]
137    fn carmichael_number() {
138        let carmichaels: Vec<BigUint> = vec![
139            BigUint::parse_bytes(b"561", 10).unwrap(),
140            BigUint::parse_bytes(b"41041", 10).unwrap(),
141            BigUint::parse_bytes(b"825265", 10).unwrap(),
142            BigUint::parse_bytes(b"321197185", 10).unwrap(),
143            BigUint::parse_bytes(b"5394826801", 10).unwrap(),
144            BigUint::parse_bytes(b"232250619601", 10).unwrap(),
145            BigUint::parse_bytes(b"9746347772161", 10).unwrap(),
146            BigUint::parse_bytes(b"1436697831295441", 10).unwrap(),
147            BigUint::parse_bytes(b"60977817398996785", 10).unwrap(),
148            BigUint::parse_bytes(b"7156857700403137441", 10).unwrap()
149        ];
150
151        for carmichael in carmichaels {
152            assert_eq!(fermat(&carmichael), true);
153        }
154    }
155}
large_primes/primality/fermat.rs

large_primes/primality/
fermat.rs
