nums/
traits.rs

1use alloc::vec;
2use alloc::vec::Vec;
3use core::fmt::{Debug, Display, Formatter};
4use core::iter;
5use core::ops::Mul;
6use num_bigint::BigUint;
7use num_traits::One;
8
9pub trait PrimalityTest {
10    fn is_prime(&self, n: &BigUint) -> bool;
11}
12
13pub trait CompositeSplitter {
14    /// Undefined behavior if `n` is prime.
15    fn divisor(&self, n: &BigUint) -> BigUint;
16
17    fn split(&self, n: &BigUint) -> (BigUint, BigUint) {
18        let d1 = self.divisor(n);
19        let d2 = n / &d1;
20        if d1 < d2 {
21            (d1, d2)
22        } else {
23            (d2, d1)
24        }
25    }
26}
27
28/// Factors numbers.
29pub trait Factorizer {
30    /// Returns the prime factorization of the given number `n`.
31    fn prime_factors(&self, n: &BigUint) -> FactoredInteger;
32}
33
34#[derive(Eq, PartialEq, Hash)]
35pub struct FactoredInteger {
36    /// A list of `(prime, count)` pairs, ordered starting with the smallest prime.
37    /// There should be no zero counts.
38    factor_counts: Vec<(BigUint, usize)>,
39}
40
41impl FactoredInteger {
42    /// The value 1, which has no prime factors.
43    pub fn one() -> Self {
44        Self {
45            factor_counts: vec![],
46        }
47    }
48
49    /// A number with a single factor, which is assumed to be prime.
50    pub fn single(factor: BigUint) -> Self {
51        Self {
52            factor_counts: vec![(factor, 1)],
53        }
54    }
55
56    pub fn from_factors(mut factors: Vec<BigUint>) -> Self {
57        factors.sort();
58        Self::from_ordered_factors(factors)
59    }
60
61    pub fn from_ordered_factors(factors: Vec<BigUint>) -> Self {
62        let mut factors_iter = factors.into_iter().peekable();
63        let mut factor_counts = vec![];
64        while let Some(f) = factors_iter.next() {
65            let mut count = 1;
66            while factors_iter.peek() == Some(&f) {
67                count += 1;
68                factors_iter.next();
69            }
70            factor_counts.push((f, count));
71        }
72        Self { factor_counts }
73    }
74
75    pub fn from_ordered_factor_counts(factor_counts: Vec<(BigUint, usize)>) -> Self {
76        Self { factor_counts }
77    }
78
79    pub fn to_biguint(&self) -> BigUint {
80        self.to_vec()
81            .into_iter()
82            .fold(BigUint::one(), |acc, x| acc * x)
83    }
84
85    pub fn to_vec(&self) -> Vec<BigUint> {
86        self.factor_counts
87            .iter()
88            .flat_map(|(factor, count)| iter::repeat(factor.clone()).take(*count))
89            .collect()
90    }
91
92    pub fn num_distinct_prime_factors(&self) -> usize {
93        self.factor_counts.len()
94    }
95
96    pub fn is_one(&self) -> bool {
97        self.factor_counts.is_empty()
98    }
99}
100
101impl Mul for FactoredInteger {
102    type Output = Self;
103
104    fn mul(self, rhs: Self) -> Self {
105        let mut combined_vec = self.to_vec();
106        combined_vec.extend(rhs.to_vec());
107        Self::from_factors(combined_vec)
108    }
109}
110
111impl Display for FactoredInteger {
112    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
113        if self.is_one() {
114            return write!(f, "1");
115        }
116
117        let mut first = true;
118        for (factor, count) in &self.factor_counts {
119            if first {
120                first = false;
121            } else {
122                write!(f, " * ")?;
123            }
124
125            if *count == 1 {
126                write!(f, "{}", factor)?;
127            } else {
128                write!(f, "{}^{}", factor, count)?;
129            }
130        }
131
132        Ok(())
133    }
134}
135
136impl Debug for FactoredInteger {
137    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
138        write!(f, "{}", self)
139    }
140}
nums/traits.rs

nums/
traits.rs
