1use crate::traits::{CompositeSplitter, Factorizer, PrimalityTest};
2use alloc::vec;
3use alloc::vec::Vec;
4use num_bigint::BigUint;
5use num_traits::{One, Zero};
6
7pub struct PrimalityTestFromFactorizer<F: Factorizer> {
8 pub factorizer: F,
9}
10
11impl<F: Factorizer> PrimalityTest for PrimalityTestFromFactorizer<F> {
12 fn is_prime(&self, n: &BigUint) -> bool {
13 let factors = self.factorizer.factors(n);
14 match factors.len() {
15 0 => {
16 assert!(n.is_one());
17 false
18 }
19 1 => {
20 assert_eq!(&factors[0], n);
21 true
22 }
23 _ => false,
24 }
25 }
26}
27
28pub struct FactorizerFromSplitter<PT, CS>
29where
30 PT: PrimalityTest,
31 CS: CompositeSplitter,
32{
33 pub primality_test: PT,
34 pub composite_splitter: CS,
35}
36
37impl<PT, CS> Factorizer for FactorizerFromSplitter<PT, CS>
38where
39 PT: PrimalityTest,
40 CS: CompositeSplitter,
41{
42 fn factors(&self, n: &BigUint) -> Vec<BigUint> {
43 assert!(!n.is_zero());
44
45 if n.is_one() {
46 return vec![];
47 }
48
49 if self.primality_test.is_prime(n) {
50 return vec![n.clone()];
51 }
52
53 let (a, b) = self.composite_splitter.split(n);
54 assert!(!a.is_one());
55 assert!(!b.is_one());
56 assert_ne!(&a, n);
57 assert_ne!(&b, n);
58 let mut factors = self.factors(&a);
59 factors.extend(self.factors(&b));
60 factors
61 }
62}