nums/
trial_division.rs

Help
1use alloc::vec;
2use alloc::vec::Vec;
3use num_bigint::BigUint;
4use num_integer::Integer;
5use num_traits::{One, Zero};
6
7use crate::traits::PrimalityTest;
8use crate::Factorizer;
9
10/// The trial division method for primality testing or factorization.
11pub struct TrialDivision;
12
13impl PrimalityTest for TrialDivision {
14    fn is_prime(&self, n: &BigUint) -> bool {
15        if n.is_zero() || n.is_one() {
16            return false;
17        }
18
19        let mut divisor = BigUint::from(2u8);
20        while &divisor * &divisor <= *n {
21            if n.is_multiple_of(&divisor) {
22                return false;
23            }
24            divisor.inc();
25        }
26        true
27    }
28}
29
30impl Factorizer for TrialDivision {
31    fn factors(&self, n: &BigUint) -> Vec<BigUint> {
32        assert!(!n.is_zero());
33
34        let mut n = n.clone();
35        let mut factors = vec![];
36        let mut divisor = BigUint::from(2u8);
37
38        while &divisor * &divisor <= n {
39            let (quotient, remainder) = n.div_rem(&divisor);
40            if remainder.is_zero() {
41                factors.push(divisor.clone());
42                n = quotient;
43            } else {
44                divisor.inc();
45            }
46        }
47
48        if !n.is_one() {
49            factors.push(n);
50        }
51        factors
52    }
53}
54
55#[cfg(test)]
56mod tests {
57    use alloc::vec;
58    use num_bigint::BigUint;
59    use num_traits::{One, Zero};
60
61    use crate::{Factorizer, PrimalityTest, TrialDivision};
62
63    #[test]
64    fn is_prime() {
65        assert_eq!(TrialDivision.is_prime(&BigUint::zero()), false);
66        assert_eq!(TrialDivision.is_prime(&BigUint::one()), false);
67        assert_eq!(TrialDivision.is_prime(&BigUint::from(2u8)), true);
68        assert_eq!(TrialDivision.is_prime(&BigUint::from(3u8)), true);
69        assert_eq!(TrialDivision.is_prime(&BigUint::from(4u8)), false);
70        assert_eq!(TrialDivision.is_prime(&BigUint::from(5u8)), true);
71        assert_eq!(TrialDivision.is_prime(&BigUint::from(6u8)), false);
72        assert_eq!(TrialDivision.is_prime(&BigUint::from(7u8)), true);
73        assert_eq!(TrialDivision.is_prime(&BigUint::from(8u8)), false);
74    }
75
76    #[test]
77    fn factor() {
78        assert_eq!(TrialDivision.factors(&BigUint::one()), vec![]);
79        assert_eq!(
80            TrialDivision.factors(&BigUint::from(2u8)),
81            vec![BigUint::from(2u8)]
82        );
83        assert_eq!(
84            TrialDivision.factors(&BigUint::from(3u8)),
85            vec![BigUint::from(3u8)]
86        );
87        assert_eq!(
88            TrialDivision.factors(&BigUint::from(4u8)),
89            vec![BigUint::from(2u8), BigUint::from(2u8)]
90        );
91        assert_eq!(
92            TrialDivision.factors(&BigUint::from(5u8)),
93            vec![BigUint::from(5u8)]
94        );
95        assert_eq!(
96            TrialDivision.factors(&BigUint::from(6u8)),
97            vec![BigUint::from(2u8), BigUint::from(3u8)]
98        );
99    }
100}
nums/trial_division.rs

nums/
trial_division.rs
