nums/
adapters.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
use crate::traits::{CompositeSplitter, Factorizer, PrimalityTest};
use alloc::vec;
use alloc::vec::Vec;
use num_bigint::BigUint;
use num_traits::{One, Zero};

pub struct PrimalityTestFromFactorizer<F: Factorizer> {
    pub factorizer: F,
}

impl<F: Factorizer> PrimalityTest for PrimalityTestFromFactorizer<F> {
    fn is_prime(&self, n: &BigUint) -> bool {
        let factors = self.factorizer.factors(n);
        match factors.len() {
            0 => {
                assert!(n.is_one());
                false
            }
            1 => {
                assert_eq!(&factors[0], n);
                true
            }
            _ => false,
        }
    }
}

pub struct FactorizerFromSplitter<PT, CS>
where
    PT: PrimalityTest,
    CS: CompositeSplitter,
{
    pub primality_test: PT,
    pub composite_splitter: CS,
}

impl<PT, CS> Factorizer for FactorizerFromSplitter<PT, CS>
where
    PT: PrimalityTest,
    CS: CompositeSplitter,
{
    fn factors(&self, n: &BigUint) -> Vec<BigUint> {
        assert!(!n.is_zero());

        if n.is_one() {
            return vec![];
        }

        if self.primality_test.is_prime(n) {
            return vec![n.clone()];
        }

        let (a, b) = self.composite_splitter.split(n);
        assert!(!a.is_one());
        assert!(!b.is_one());
        assert_ne!(&a, n);
        assert_ne!(&b, n);
        let mut factors = self.factors(&a);
        factors.extend(self.factors(&b));
        factors
    }
}