algebraeon_rings/natural/factorization/
structure.rs

1use crate::natural::factorization::factor_nat;
2use crate::natural::factorization::primes::is_prime_nat;
3use crate::structure::{
4    Factored, FactoringMonoidSignature, FactoringStructure, MetaFactoringMonoid,
5    MultiplicationSignature, MultiplicativeMonoidSignature, SemiRingSignature,
6    UniqueFactorizationMonoidSignature,
7};
8use algebraeon_nzq::traits::ModPow;
9use algebraeon_nzq::{Natural, NaturalCanonicalStructure, gcd};
10use algebraeon_sets::structure::{BorrowedStructure, MetaType, SetSignature, ToStringSignature};
11use itertools::Itertools;
12
13impl UniqueFactorizationMonoidSignature for NaturalCanonicalStructure {
14    type FactoredExponent = NaturalCanonicalStructure;
15
16    fn factorization_exponents(&self) -> &Self::FactoredExponent {
17        Natural::structure_ref()
18    }
19
20    fn into_factorization_exponents(self) -> Self::FactoredExponent {
21        Natural::structure()
22    }
23
24    fn try_is_irreducible(&self, a: &Self::Set) -> Option<bool> {
25        Some(is_prime_nat(a))
26    }
27
28    fn factorization_pow(&self, a: &Self::Set, k: &Natural) -> Self::Set {
29        self.nat_pow(a, k)
30    }
31}
32
33impl FactoringMonoidSignature for NaturalCanonicalStructure {
34    fn is_irreducible(&self, a: &Self::Set) -> bool {
35        is_prime_nat(a)
36    }
37
38    fn factor_unchecked(
39        &self,
40        a: &Self::Set,
41    ) -> Factored<Self::Set, <Self::FactoredExponent as SetSignature>::Set> {
42        factor_nat(a.clone())
43    }
44}
45
46impl<
47    ObjectB: BorrowedStructure<NaturalCanonicalStructure>,
48    ExponentB: BorrowedStructure<NaturalCanonicalStructure>,
49> FactoringStructure<NaturalCanonicalStructure, ObjectB, NaturalCanonicalStructure, ExponentB>
50{
51    pub fn euler_totient(&self, a: &Factored<Natural, Natural>) -> Natural {
52        #[cfg(debug_assertions)]
53        self.is_element(a).unwrap();
54        match a {
55            Factored::Zero => {
56                // The number of units in the quotient ring Z/0Z = Z is 2 i.e. +1 and -1
57                self.objects().from_nat(&Natural::TWO)
58            }
59            Factored::NonZero(a) => {
60                let mut prod = a.unit().clone();
61                for (p, k) in a.powers() {
62                    debug_assert!(p != &Natural::ZERO);
63                    debug_assert!(k != &Natural::ZERO);
64                    self.objects().mul_mut(
65                        &mut prod,
66                        &((p - &Natural::ONE) * p.pow(&(k - &Natural::ONE))),
67                    );
68                }
69                prod
70            }
71        }
72    }
73}
74
75#[derive(Debug, Clone, Copy, PartialEq, Eq)]
76pub enum IsPrimitiveRootResult {
77    NonUnit,
78    No,
79    Yes,
80}
81
82impl<
83    PowersB: BorrowedStructure<NaturalCanonicalStructure>,
84    ExponentB: BorrowedStructure<NaturalCanonicalStructure>,
85> FactoringStructure<NaturalCanonicalStructure, PowersB, NaturalCanonicalStructure, ExponentB>
86{
87    /// Return whether x is a primitive root modulo the factorized value
88    pub fn is_primitive_root(
89        &self,
90        x: &Natural,
91        n_factored: &Factored<Natural, Natural>,
92    ) -> IsPrimitiveRootResult {
93        #[cfg(debug_assertions)]
94        self.is_element(n_factored).unwrap();
95
96        let factorizations = Natural::structure_ref().factorizations();
97        let n = factorizations.expand(n_factored);
98        if gcd(x.clone(), n.clone()) != Natural::ONE {
99            IsPrimitiveRootResult::NonUnit
100        } else {
101            let phi_n = factorizations.euler_totient(n_factored);
102            let x_mod_n = x % &n;
103            for p in phi_n.clone().factor().distinct_irreducibles().unwrap() {
104                if (&x_mod_n).mod_pow(&phi_n / p, &n) == Natural::ONE {
105                    return IsPrimitiveRootResult::No;
106                }
107            }
108            IsPrimitiveRootResult::Yes
109        }
110    }
111}
112
113impl<
114    PowersB: BorrowedStructure<NaturalCanonicalStructure>,
115    ExponentB: BorrowedStructure<NaturalCanonicalStructure>,
116> ToStringSignature
117    for FactoringStructure<NaturalCanonicalStructure, PowersB, NaturalCanonicalStructure, ExponentB>
118{
119    fn to_string(&self, elem: &Self::Set) -> String {
120        use std::fmt::Write;
121        let mut f = String::new();
122        if let Some(powers) = elem.powers() {
123            if powers.is_empty() {
124                write!(f, "1").unwrap();
125            } else {
126                for (i, (p, k)) in powers
127                    .iter()
128                    .sorted_by_cached_key(|(p, _k)| (*p).clone())
129                    .enumerate()
130                {
131                    if i != 0 {
132                        write!(f, " × ").unwrap();
133                    }
134                    write!(f, "{}", p).unwrap();
135                    if k != &Natural::ONE {
136                        write!(f, "^").unwrap();
137                        write!(f, "{}", k).unwrap();
138                    }
139                }
140            }
141        } else {
142            write!(f, "0").unwrap();
143        }
144        f
145    }
146}
algebraeon_rings/natural/factorization/structure.rs

algebraeon_rings/natural/factorization/
structure.rs
