algebraeon_rings/structure/
factorization.rs

1use crate::structure::{
2    CancellativeAdditionSignature, CancellativeMultiplicationSignature,
3    CommutativeMultiplicationSignature, FavoriteAssociateSignature, FieldSignature,
4    MetaMultiplicativeMonoidSignature, MetaOneSignature, MultiplicationSignature,
5    MultiplicativeAbsorptionMonoidSignature, MultiplicativeMonoidSignature,
6    MultiplicativeMonoidSquareOpsSignature, OneSignature, RinglikeSpecializationSignature,
7    SemiRingSignature, TryReciprocalSignature, ZeroEqSignature, ZeroSignature,
8};
9use algebraeon_groups::structure::{CompositionSignature, GroupSignature};
10use algebraeon_nzq::{Natural, NaturalCanonicalStructure};
11use algebraeon_sets::structure::{
12    BorrowedStructure, EqSignature, MetaType, OrdSignature, SetSignature, Signature,
13};
14use std::fmt::{Debug, Display};
15use std::marker::PhantomData;
16
17#[derive(Debug, Clone)]
18pub struct NonZeroFactored<ObjectSet: Debug + Clone, ExponentSet: Debug + Clone> {
19    unit: ObjectSet,
20    powers: Vec<(ObjectSet, ExponentSet)>,
21}
22
23impl<ObjectSet: Debug + Clone, ExponentSet: Debug + Clone> NonZeroFactored<ObjectSet, ExponentSet> {
24    pub fn powers(&self) -> &Vec<(ObjectSet, ExponentSet)> {
25        &self.powers
26    }
27
28    pub fn into_powers(self) -> Vec<(ObjectSet, ExponentSet)> {
29        self.powers
30    }
31
32    pub fn unit(&self) -> &ObjectSet {
33        &self.unit
34    }
35
36    pub fn into_unit(self) -> ObjectSet {
37        self.unit
38    }
39
40    pub fn unit_and_powers(&self) -> (&ObjectSet, &Vec<(ObjectSet, ExponentSet)>) {
41        (&self.unit, &self.powers)
42    }
43
44    pub fn into_unit_and_powers(self) -> (ObjectSet, Vec<(ObjectSet, ExponentSet)>) {
45        (self.unit, self.powers)
46    }
47
48    pub fn distinct_irreducibles(&self) -> Vec<&ObjectSet> {
49        self.powers.iter().map(|(p, _)| p).collect()
50    }
51
52    pub fn into_distinct_irreducibles(self) -> Vec<ObjectSet> {
53        self.powers.into_iter().map(|(p, _)| p).collect()
54    }
55}
56
57#[derive(Debug, Clone)]
58pub enum Factored<ObjectSet: Debug + Clone, ExponentSet: Debug + Clone> {
59    Zero,
60    NonZero(NonZeroFactored<ObjectSet, ExponentSet>),
61}
62
63impl<
64    ObjectSet: Debug + Clone,
65    ExponentSet: Debug + Clone + MetaMultiplicativeMonoidSignature + PartialEq + Eq,
66> Display for Factored<ObjectSet, ExponentSet>
67where
68    ObjectSet: Display,
69    ExponentSet: Display,
70    ExponentSet::Signature: MultiplicativeMonoidSignature,
71{
72    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
73        match self {
74            Factored::Zero => {
75                write!(f, "0")?;
76            }
77            Factored::NonZero(non_zero_factored) => {
78                write!(f, "{}", non_zero_factored.unit)?;
79                for (factor, k) in &non_zero_factored.powers {
80                    write!(f, " * (")?;
81                    write!(f, "{}", factor)?;
82                    write!(f, ")")?;
83                    if k != &ExponentSet::one() {
84                        write!(f, "^")?;
85                        write!(f, "{}", k)?;
86                    }
87                }
88            }
89        }
90        Ok(())
91    }
92}
93
94impl<ObjectSet: Debug + Clone, ExponentSet: Debug + Clone> Factored<ObjectSet, ExponentSet> {
95    pub fn is_zero(&self) -> bool {
96        match self {
97            Factored::Zero => true,
98            Factored::NonZero(_) => false,
99        }
100    }
101
102    pub fn unwrap_nonzero(self) -> NonZeroFactored<ObjectSet, ExponentSet> {
103        match self {
104            Factored::Zero => panic!(),
105            Factored::NonZero(f) => f,
106        }
107    }
108
109    pub fn powers(&self) -> Option<&Vec<(ObjectSet, ExponentSet)>> {
110        match self {
111            Factored::Zero => None,
112            Factored::NonZero(a) => Some(a.powers()),
113        }
114    }
115
116    pub fn into_powers(self) -> Option<Vec<(ObjectSet, ExponentSet)>> {
117        match self {
118            Factored::Zero => None,
119            Factored::NonZero(a) => Some(a.into_powers()),
120        }
121    }
122
123    pub fn unit(&self) -> Option<&ObjectSet> {
124        match self {
125            Factored::Zero => None,
126            Factored::NonZero(a) => Some(a.unit()),
127        }
128    }
129
130    pub fn into_unit(self) -> Option<ObjectSet> {
131        match self {
132            Factored::Zero => None,
133            Factored::NonZero(a) => Some(a.into_unit()),
134        }
135    }
136
137    pub fn unit_and_powers(&self) -> Option<(&ObjectSet, &Vec<(ObjectSet, ExponentSet)>)> {
138        match self {
139            Factored::Zero => None,
140            Factored::NonZero(a) => Some(a.unit_and_powers()),
141        }
142    }
143
144    pub fn into_unit_and_powers(self) -> Option<(ObjectSet, Vec<(ObjectSet, ExponentSet)>)> {
145        match self {
146            Factored::Zero => None,
147            Factored::NonZero(a) => Some(a.into_unit_and_powers()),
148        }
149    }
150
151    pub fn distinct_irreducibles(&self) -> Option<Vec<&ObjectSet>> {
152        match self {
153            Factored::Zero => None,
154            Factored::NonZero(a) => Some(a.distinct_irreducibles()),
155        }
156    }
157
158    pub fn into_distinct_irreducibles(self) -> Option<Vec<ObjectSet>> {
159        match self {
160            Factored::Zero => None,
161            Factored::NonZero(a) => Some(a.into_distinct_irreducibles()),
162        }
163    }
164}
165
166#[derive(Debug, Clone, PartialEq, Eq)]
167pub struct FactoringStructure<
168    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
169    ObjectB: BorrowedStructure<Object>,
170    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
171    ExponentB: BorrowedStructure<Exponent>,
172> {
173    _objects: PhantomData<Object>,
174    objects: ObjectB,
175    _exponents: PhantomData<Exponent>,
176    exponents: ExponentB,
177}
178
179impl<
180    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
181    ObjectB: BorrowedStructure<Object>,
182    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
183    ExponentB: BorrowedStructure<Exponent>,
184> FactoringStructure<Object, ObjectB, Exponent, ExponentB>
185{
186    pub fn new(objects: ObjectB, exponents: ExponentB) -> Self {
187        Self {
188            _objects: PhantomData,
189            objects,
190            _exponents: PhantomData,
191            exponents,
192        }
193    }
194
195    pub fn objects(&self) -> &Object {
196        self.objects.borrow()
197    }
198
199    pub fn exponents(&self) -> &Exponent {
200        self.exponents.borrow()
201    }
202}
203
204// These methods are all completely unchecked, to be used by things which construct factorizations.
205impl<
206    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
207    ObjectB: BorrowedStructure<Object>,
208    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
209    ExponentB: BorrowedStructure<Exponent>,
210> FactoringStructure<Object, ObjectB, Exponent, ExponentB>
211{
212    pub(crate) fn mul_mut_impl(
213        &self,
214        a: &mut Factored<Object::Set, Exponent::Set>,
215        b: &Factored<Object::Set, Exponent::Set>,
216    ) {
217        match b {
218            Factored::Zero => {
219                *a = Factored::Zero;
220            }
221            Factored::NonZero(b) => match a {
222                Factored::Zero => {}
223                Factored::NonZero(a) => {
224                    a.unit = self.objects().units().compose(&a.unit, &b.unit);
225                    for (b_p, b_k) in &b.powers {
226                        debug_assert!(self.objects().is_fav_assoc(b_p));
227                        'A_LOOP: {
228                            for (a_p, a_k) in &mut a.powers {
229                                debug_assert!(self.objects().is_fav_assoc(a_p));
230                                if self.objects().equal(a_p, b_p) {
231                                    *a_k = self.exponents().add(a_k, b_k);
232                                    break 'A_LOOP;
233                                }
234                            }
235                            a.powers.push((b_p.clone(), b_k.clone()));
236                        }
237                    }
238                    a.powers.retain(|(_, k)| !self.exponents().is_zero(k));
239                }
240            },
241        }
242    }
243
244    pub(crate) fn mul_gcd_impl(
245        &self,
246        a: &mut Factored<Object::Set, Exponent::Set>,
247        b: &Factored<Object::Set, Exponent::Set>,
248    ) {
249        match b {
250            Factored::Zero => {}
251            Factored::NonZero(b) => match a {
252                Factored::Zero => {
253                    *a = Factored::NonZero(b.clone());
254                }
255                Factored::NonZero(a) => {
256                    a.unit = self.objects().units().compose(&a.unit, &b.unit);
257                    for (b_p, b_k) in &b.powers {
258                        debug_assert!(self.objects().is_fav_assoc(b_p));
259                        'A_LOOP: {
260                            for (a_p, a_k) in &mut a.powers {
261                                debug_assert!(self.objects().is_fav_assoc(a_p));
262                                if self.objects().equal(a_p, b_p) {
263                                    *a_k = self.exponents().min(a_k, b_k);
264                                    break 'A_LOOP;
265                                }
266                            }
267                            a.powers.push((b_p.clone(), b_k.clone()));
268                        }
269                    }
270                    a.powers.retain(|(_, k)| !self.exponents().is_zero(k));
271                }
272            },
273        }
274    }
275
276    pub(crate) fn mul_lcm_impl(
277        &self,
278        a: &mut NonZeroFactored<Object::Set, Exponent::Set>,
279        b: &NonZeroFactored<Object::Set, Exponent::Set>,
280    ) {
281        a.unit = self.objects().units().compose(&a.unit, &b.unit);
282        for (b_p, b_k) in &b.powers {
283            debug_assert!(self.objects().is_fav_assoc(b_p));
284            'A_LOOP: {
285                for (a_p, a_k) in &mut a.powers {
286                    debug_assert!(self.objects().is_fav_assoc(a_p));
287                    if self.objects().equal(a_p, b_p) {
288                        *a_k = self.exponents().max(a_k, b_k);
289                        break 'A_LOOP;
290                    }
291                }
292                a.powers.push((b_p.clone(), b_k.clone()));
293            }
294        }
295        a.powers.retain(|(_, k)| !self.exponents().is_zero(k));
296    }
297
298    pub(crate) fn try_divide_mut_impl(
299        &self,
300        a: &mut Option<Factored<Object::Set, Exponent::Set>>,
301        b: &Factored<Object::Set, Exponent::Set>,
302    ) {
303        match b {
304            Factored::Zero => {
305                *a = None;
306            }
307            Factored::NonZero(b) => match a {
308                None => {}
309                Some(Factored::Zero) => {}
310                Some(Factored::NonZero(a_nz)) => {
311                    a_nz.unit = self
312                        .objects()
313                        .units()
314                        .compose(&a_nz.unit, &self.objects().units().inverse(&b.unit));
315                    for (b_p, b_k) in &b.powers {
316                        debug_assert!(self.objects().is_fav_assoc(b_p));
317                        'A_LOOP: {
318                            for (a_p, a_k) in &mut a_nz.powers {
319                                debug_assert!(self.objects().is_fav_assoc(a_p));
320                                if self.objects().equal(a_p, b_p) {
321                                    if let Some(a_k_minus_b_k) = self.exponents().try_sub(a_k, b_k)
322                                    {
323                                        *a_k = a_k_minus_b_k;
324                                    } else {
325                                        *a = None;
326                                        return;
327                                    }
328                                    break 'A_LOOP;
329                                }
330                            }
331                            if let Some(b_k_neg) = self.exponents().try_neg(b_k) {
332                                a_nz.powers.push((b_p.clone(), b_k_neg));
333                            } else {
334                                *a = None;
335                                return;
336                            }
337                        }
338                    }
339                    a_nz.powers.retain(|(_, k)| !self.exponents().is_zero(k));
340                }
341            },
342        }
343    }
344
345    pub(crate) fn is_irreducible_impl(&self, a: &Factored<Object::Set, Exponent::Set>) -> bool {
346        match a {
347            Factored::Zero => {}
348            Factored::NonZero(a) => {
349                if a.powers.len() == 1 {
350                    let (_, k) = &a.powers[0];
351                    if self.exponents().equal(k, &self.exponents().one()) {
352                        return true;
353                    }
354                }
355            }
356        }
357        false
358    }
359}
360
361impl<
362    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
363    ObjectB: BorrowedStructure<Object>,
364    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
365    ExponentB: BorrowedStructure<Exponent>,
366> Signature for FactoringStructure<Object, ObjectB, Exponent, ExponentB>
367{
368}
369
370impl<
371    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
372    ObjectB: BorrowedStructure<Object>,
373    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
374    ExponentB: BorrowedStructure<Exponent>,
375> SetSignature for FactoringStructure<Object, ObjectB, Exponent, ExponentB>
376{
377    type Set = Factored<Object::Set, Exponent::Set>;
378
379    fn is_element(&self, x: &Self::Set) -> Result<(), String> {
380        match x {
381            Factored::Zero => Ok(()),
382            Factored::NonZero(x) => {
383                self.objects().units().is_element(&x.unit)?;
384                for (prime, exponent) in &x.powers {
385                    if !self.objects().is_fav_assoc(prime) {
386                        return Err("Factors should be their favorite associate".to_string());
387                    }
388                    if self.objects().try_is_irreducible(prime) == Some(false) {
389                        return Err("Failed to be irreducible".to_string());
390                    }
391                    self.exponents().is_element(exponent)?;
392                    if self.exponents().is_zero(exponent) {
393                        return Err("Exponent is zero".to_string());
394                    }
395                }
396
397                for i in 0..x.powers.len() {
398                    for j in 0..i {
399                        let (pi, _ki) = &x.powers[i];
400                        let (pj, _kj) = &x.powers[j];
401                        if self.objects().equal(pi, pj) {
402                            return Err("primes must be distinct".to_string());
403                        }
404                    }
405                }
406
407                Ok(())
408            }
409        }
410    }
411}
412
413impl<
414    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
415    ObjectB: BorrowedStructure<Object>,
416    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
417    ExponentB: BorrowedStructure<Exponent>,
418> EqSignature for FactoringStructure<Object, ObjectB, Exponent, ExponentB>
419{
420    fn equal(&self, a: &Self::Set, b: &Self::Set) -> bool {
421        #[cfg(debug_assertions)]
422        {
423            self.is_element(a).unwrap();
424            self.is_element(b).unwrap();
425        }
426        self.try_divide(a, b).is_some() && self.try_divide(b, a).is_some()
427    }
428}
429
430impl<
431    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
432    ObjectB: BorrowedStructure<Object>,
433    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
434    ExponentB: BorrowedStructure<Exponent>,
435> RinglikeSpecializationSignature for FactoringStructure<Object, ObjectB, Exponent, ExponentB>
436{
437}
438
439impl<
440    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
441    ObjectB: BorrowedStructure<Object>,
442    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
443    ExponentB: BorrowedStructure<Exponent>,
444> ZeroSignature for FactoringStructure<Object, ObjectB, Exponent, ExponentB>
445{
446    fn zero(&self) -> Self::Set {
447        Factored::Zero
448    }
449}
450
451impl<
452    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
453    ObjectB: BorrowedStructure<Object>,
454    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
455    ExponentB: BorrowedStructure<Exponent>,
456> OneSignature for FactoringStructure<Object, ObjectB, Exponent, ExponentB>
457{
458    fn one(&self) -> Self::Set {
459        Factored::NonZero(NonZeroFactored {
460            unit: self.objects().one(),
461            powers: vec![],
462        })
463    }
464}
465
466impl<
467    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
468    ObjectB: BorrowedStructure<Object>,
469    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
470    ExponentB: BorrowedStructure<Exponent>,
471> MultiplicationSignature for FactoringStructure<Object, ObjectB, Exponent, ExponentB>
472{
473    fn mul(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
474        #[cfg(debug_assertions)]
475        {
476            self.is_element(a).unwrap();
477            self.is_element(b).unwrap();
478        }
479        let mut s = a.clone();
480        self.mul_mut_impl(&mut s, b);
481        s
482    }
483}
484
485impl<
486    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
487    ObjectB: BorrowedStructure<Object>,
488    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
489    ExponentB: BorrowedStructure<Exponent>,
490> CommutativeMultiplicationSignature for FactoringStructure<Object, ObjectB, Exponent, ExponentB>
491{
492}
493
494impl<
495    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
496    ObjectB: BorrowedStructure<Object>,
497    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
498    ExponentB: BorrowedStructure<Exponent>,
499> MultiplicativeMonoidSignature for FactoringStructure<Object, ObjectB, Exponent, ExponentB>
500{
501}
502
503impl<
504    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
505    ObjectB: BorrowedStructure<Object>,
506    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
507    ExponentB: BorrowedStructure<Exponent>,
508> TryReciprocalSignature for FactoringStructure<Object, ObjectB, Exponent, ExponentB>
509{
510    fn try_reciprocal(&self, a: &Self::Set) -> Option<Self::Set> {
511        #[cfg(debug_assertions)]
512        self.is_element(a).unwrap();
513        match a {
514            Factored::Zero => None,
515            Factored::NonZero(a) => Some(Factored::NonZero(NonZeroFactored {
516                unit: self.objects().units().inverse(&a.unit),
517                powers: a
518                    .powers
519                    .iter()
520                    .map(|(p, k)| self.exponents().try_neg(k).map(|neg_k| (p.clone(), neg_k)))
521                    .collect::<Option<Vec<_>>>()?,
522            })),
523        }
524    }
525}
526
527impl<
528    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
529    ObjectB: BorrowedStructure<Object>,
530    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
531    ExponentB: BorrowedStructure<Exponent>,
532> CancellativeMultiplicationSignature for FactoringStructure<Object, ObjectB, Exponent, ExponentB>
533{
534    fn try_divide(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
535        let mut s = Some(a.clone());
536        self.try_divide_mut_impl(&mut s, b);
537        s
538    }
539}
540
541impl<
542    Object: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent>,
543    ObjectB: BorrowedStructure<Object>,
544    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
545    ExponentB: BorrowedStructure<Exponent>,
546> FactoringStructure<Object, ObjectB, Exponent, ExponentB>
547{
548    pub fn new_irreducible_unchecked(
549        &self,
550        p: Object::Set,
551    ) -> Factored<Object::Set, Exponent::Set> {
552        self.new_unit_and_powers_unchecked(self.objects().one(), vec![(p, self.exponents().one())])
553    }
554
555    pub fn new_unit_unchecked(&self, unit: Object::Set) -> Factored<Object::Set, Exponent::Set> {
556        self.new_unit_and_powers_unchecked(unit, vec![])
557    }
558
559    pub fn new_powers_unchecked(
560        &self,
561        powers: Vec<(Object::Set, Exponent::Set)>,
562    ) -> Factored<Object::Set, Exponent::Set> {
563        self.new_unit_and_powers_unchecked(self.objects().one(), powers)
564    }
565
566    pub fn new_unit_and_powers_unchecked(
567        &self,
568        mut unit: Object::Set,
569        powers: Vec<(Object::Set, Exponent::Set)>,
570    ) -> Factored<Object::Set, Exponent::Set> {
571        let mut fav_assoc_powers = vec![];
572        for (p, k) in powers {
573            let (u, p) = self.objects().factor_fav_assoc(&p);
574            self.objects()
575                .mul_mut(&mut unit, &self.objects().factorization_pow(&u, &k));
576            fav_assoc_powers.push((p, k));
577        }
578        let f = Factored::NonZero(NonZeroFactored {
579            unit,
580            powers: fav_assoc_powers,
581        });
582        #[cfg(debug_assertions)]
583        self.is_element(&f).unwrap();
584        f
585    }
586
587    pub fn gcd(
588        &self,
589        a: &Factored<Object::Set, Exponent::Set>,
590        b: &Factored<Object::Set, Exponent::Set>,
591    ) -> Factored<Object::Set, Exponent::Set> {
592        #[cfg(debug_assertions)]
593        {
594            self.is_element(a).unwrap();
595            self.is_element(b).unwrap();
596        }
597        let mut s = a.clone();
598        self.mul_gcd_impl(&mut s, b);
599        s
600    }
601
602    pub fn lcm(
603        &self,
604        a: &Factored<Object::Set, Exponent::Set>,
605        b: &Factored<Object::Set, Exponent::Set>,
606    ) -> Option<Factored<Object::Set, Exponent::Set>> {
607        #[cfg(debug_assertions)]
608        {
609            self.is_element(a).unwrap();
610            self.is_element(b).unwrap();
611        }
612        match (a, b) {
613            (Factored::Zero, Factored::Zero)
614            | (Factored::Zero, Factored::NonZero(_))
615            | (Factored::NonZero(_), Factored::Zero) => None,
616            (Factored::NonZero(a), Factored::NonZero(b)) => {
617                let mut s = a.clone();
618                self.mul_lcm_impl(&mut s, b);
619                Some(Factored::NonZero(s))
620            }
621        }
622    }
623
624    pub fn is_irreducible(&self, a: &Factored<Object::Set, Exponent::Set>) -> bool {
625        #[cfg(debug_assertions)]
626        self.is_element(a).unwrap();
627        self.is_irreducible_impl(a)
628    }
629
630    pub fn expand(&self, a: &Factored<Object::Set, Exponent::Set>) -> Object::Set {
631        #[cfg(debug_assertions)]
632        self.is_element(a).unwrap();
633        match a {
634            Factored::Zero => self.objects().zero(),
635            Factored::NonZero(a) => {
636                let mut prod = a.unit.clone();
637                for (p, k) in &a.powers {
638                    self.objects()
639                        .mul_mut(&mut prod, &self.objects().factorization_pow(p, k));
640                }
641                prod
642            }
643        }
644    }
645
646    pub fn expand_squarefree(&self, a: &Factored<Object::Set, Exponent::Set>) -> Object::Set {
647        #[cfg(debug_assertions)]
648        self.is_element(a).unwrap();
649        match a {
650            Factored::Zero => self.objects().zero(),
651            Factored::NonZero(a) => {
652                let mut prod = a.unit.clone();
653                for (p, _) in &a.powers {
654                    self.objects().mul_mut(&mut prod, p);
655                }
656                prod
657            }
658        }
659    }
660
661    pub fn pow(
662        &self,
663        f: &Factored<Object::Set, Exponent::Set>,
664        n: &Exponent::Set,
665    ) -> Factored<Object::Set, Exponent::Set> {
666        match f {
667            Factored::Zero => Factored::Zero,
668            Factored::NonZero(f) => Factored::NonZero(NonZeroFactored {
669                unit: self.objects().factorization_pow(&f.unit, n),
670                powers: f
671                    .powers
672                    .iter()
673                    .map(|(p, k)| (p.clone(), self.exponents().mul(n, k)))
674                    .collect(),
675            }),
676        }
677    }
678}
679
680impl<
681    Object: UniqueFactorizationMonoidSignature<FactoredExponent = NaturalCanonicalStructure>,
682    ObjectB: BorrowedStructure<Object>,
683    ExponentB: BorrowedStructure<NaturalCanonicalStructure>,
684> FactoringStructure<Object, ObjectB, NaturalCanonicalStructure, ExponentB>
685{
686    /// Return an iterator over all divisors of a factorization
687    pub fn divisors<'a>(
688        &'a self,
689        a: &'a Factored<Object::Set, Natural>,
690    ) -> Option<Box<dyn Iterator<Item = Object::Set> + 'a>> {
691        match a {
692            Factored::Zero => None,
693            Factored::NonZero(a) => {
694                let factors = &a.powers;
695                if factors.is_empty() {
696                    Some(Box::new(vec![self.objects().one()].into_iter()))
697                } else {
698                    let mut factor_powers = vec![];
699                    for (p, k) in factors {
700                        let j = factor_powers.len();
701                        factor_powers.push(vec![]);
702                        let mut p_pow = self.objects().one();
703                        let mut i = Natural::from(0u8);
704                        while &i <= k {
705                            factor_powers[j].push(p_pow.clone());
706                            p_pow = self.objects().mul(&p_pow, p);
707                            i += Natural::from(1u8);
708                        }
709                    }
710
711                    #[allow(clippy::redundant_closure_for_method_calls)]
712                    Some(Box::new(
713                        itertools::Itertools::multi_cartesian_product(
714                            factor_powers.into_iter().map(|p_pows| p_pows.into_iter()),
715                        )
716                        .map(move |prime_power_factors| {
717                            self.objects()
718                                .product(prime_power_factors.iter().collect())
719                                .clone()
720                        }),
721                    ))
722                }
723            }
724        }
725    }
726
727    /// The number of divisors of a factorization
728    pub fn count_divideisors(&self, a: &Factored<Object::Set, Natural>) -> Option<Natural> {
729        #[cfg(debug_assertions)]
730        self.is_element(a).unwrap();
731        match a {
732            Factored::Zero => None,
733            Factored::NonZero(a) => {
734                let factors = &a.powers;
735                let mut count = Natural::from(1u8);
736                for (_p, k) in factors {
737                    count *= k + Natural::ONE;
738                }
739                Some(count)
740            }
741        }
742    }
743
744    /// Determine whether it is the square of some element
745    #[allow(unused)]
746    fn is_square(&self, a: &Factored<Object::Set, Natural>) -> bool {
747        match a {
748            Factored::Zero => true,
749            Factored::NonZero(a) => a
750                .powers()
751                .iter()
752                .all(|(_, exponent)| exponent % Natural::TWO == Natural::ZERO),
753        }
754    }
755
756    /// Return true if non-zero and factors as a product of distinct primes
757    fn is_squarefree(&self, a: &Factored<Object::Set, Natural>) -> bool {
758        match a {
759            Factored::Zero => false,
760            Factored::NonZero(a) => a
761                .powers()
762                .iter()
763                .all(|(_, exponent)| exponent <= &Natural::ONE),
764        }
765    }
766}
767
768// TODO: generalize this to rings where we can take square-roots in the group of units
769impl<
770    Object: UniqueFactorizationMonoidSignature<FactoredExponent = NaturalCanonicalStructure>
771        + MultiplicativeMonoidSquareOpsSignature,
772    ObjectB: BorrowedStructure<Object>,
773    ExponentB: BorrowedStructure<NaturalCanonicalStructure>,
774> FactoringStructure<Object, ObjectB, NaturalCanonicalStructure, ExponentB>
775{
776    /// Return the element whose square equals the input, if it exists.
777    #[allow(unused)]
778    fn sqrt_if_square(
779        &self,
780        a: &Factored<Object::Set, Natural>,
781    ) -> Option<Factored<Object::Set, Natural>> {
782        #[cfg(debug_assertions)]
783        self.is_element(a).unwrap();
784        match a {
785            Factored::Zero => Some(self.zero()),
786            Factored::NonZero(a) => {
787                if let Some(unit_sqrt) = self.objects().sqrt_if_square(&a.unit) {
788                    let mut sqrt_factor_powers = vec![];
789                    for (prime, exponent) in a.powers() {
790                        if exponent.clone() % Natural::TWO != Natural::ZERO {
791                            return None;
792                        }
793                        let half = exponent / Natural::TWO;
794                        if half != Natural::ZERO {
795                            sqrt_factor_powers.push((prime.clone(), half.clone()));
796                        }
797                    }
798                    Some(self.new_unit_and_powers_unchecked(unit_sqrt, sqrt_factor_powers))
799                } else {
800                    None
801                }
802            }
803        }
804    }
805}
806
807pub trait UniqueFactorizationMonoidSignature:
808    MultiplicativeAbsorptionMonoidSignature + FavoriteAssociateSignature + EqSignature
809{
810    type FactoredExponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature;
811
812    fn factorization_exponents(&self) -> &Self::FactoredExponent;
813    fn into_factorization_exponents(self) -> Self::FactoredExponent;
814
815    fn factorizations(
816        &self,
817    ) -> FactoringStructure<Self, &Self, Self::FactoredExponent, &Self::FactoredExponent> {
818        FactoringStructure::new(self, self.factorization_exponents())
819    }
820    fn into_factorizations(
821        self,
822    ) -> FactoringStructure<Self, Self, Self::FactoredExponent, Self::FactoredExponent> {
823        FactoringStructure::new(self.clone(), self.into_factorization_exponents())
824    }
825
826    fn factorization_pow(
827        &self,
828        a: &Self::Set,
829        k: &<Self::FactoredExponent as SetSignature>::Set,
830    ) -> Self::Set;
831
832    /// This should determine whether a is irreducible _without_ factoring it.
833    /// Factoring a is not allowed because this function is used by factorizations to validate their state.
834    fn try_is_irreducible(&self, a: &Self::Set) -> Option<bool>;
835}
836pub trait MetaUniqueFactorizationMonoidSignature: MetaType
837where
838    Self::Signature: UniqueFactorizationMonoidSignature,
839{
840    fn try_is_irreducible(&self) -> Option<bool> {
841        Self::structure().try_is_irreducible(self)
842    }
843}
844impl<R: MetaType> MetaUniqueFactorizationMonoidSignature for R where
845    Self::Signature: UniqueFactorizationMonoidSignature
846{
847}
848
849pub trait FactoringMonoidSignature: UniqueFactorizationMonoidSignature {
850    fn is_irreducible(&self, a: &Self::Set) -> bool {
851        self.factorizations()
852            .is_irreducible_impl(&self.factor_unchecked(a))
853    }
854
855    fn factor_unchecked(
856        &self,
857        a: &Self::Set,
858    ) -> Factored<Self::Set, <Self::FactoredExponent as SetSignature>::Set>;
859
860    fn factor(
861        &self,
862        a: &Self::Set,
863    ) -> Factored<Self::Set, <Self::FactoredExponent as SetSignature>::Set> {
864        let f = self.factor_unchecked(a);
865        #[cfg(debug_assertions)]
866        {
867            self.factorizations().is_element(&f).unwrap();
868            assert!(self.equal(a, &self.factorizations().expand(&f)))
869        }
870        f
871    }
872}
873pub trait MetaFactoringMonoid: MetaType
874where
875    Self::Signature: FactoringMonoidSignature,
876{
877    fn is_irreducible(&self) -> bool {
878        Self::structure().is_irreducible(self)
879    }
880
881    fn factor_unchecked(&self) -> Factored<Self, <<Self::Signature as UniqueFactorizationMonoidSignature>::FactoredExponent as SetSignature>::Set>{
882        Self::structure().factor_unchecked(self)
883    }
884
885    fn factor(&self) -> Factored<Self, <<Self::Signature as UniqueFactorizationMonoidSignature>::FactoredExponent as SetSignature>::Set>{
886        Self::structure().factor(self)
887    }
888}
889impl<R: MetaType> MetaFactoringMonoid for R where Self::Signature: FactoringMonoidSignature {}
890
891pub trait FactoringMonoidNaturalExponentSignature:
892    FactoringMonoidSignature<FactoredExponent = NaturalCanonicalStructure>
893{
894    fn gcd_by_factor(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
895        self.factorizations()
896            .expand(&self.factorizations().gcd(&self.factor(a), &self.factor(b)))
897    }
898
899    fn lcm_by_factor(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
900        Some(
901            self.factorizations().expand(
902                &self
903                    .factorizations()
904                    .lcm(&self.factor(a), &self.factor(b))?,
905            ),
906        )
907    }
908
909    fn is_squarefree(&self, a: &Self::Set) -> bool {
910        self.factorizations().is_squarefree(&self.factor(a))
911    }
912}
913impl<S: FactoringMonoidSignature<FactoredExponent = NaturalCanonicalStructure>>
914    FactoringMonoidNaturalExponentSignature for S
915{
916}
917pub trait MetaFactoringMonoidNaturalExponent: MetaType
918where
919    Self::Signature: FactoringMonoidNaturalExponentSignature,
920{
921    fn gcd_by_factor(a: &Self, b: &Self) -> Self {
922        Self::structure().gcd_by_factor(a, b)
923    }
924
925    fn lcm_by_factor(a: &Self, b: &Self) -> Option<Self> {
926        Self::structure().lcm_by_factor(a, b)
927    }
928
929    fn is_squarefree(&self) -> bool {
930        Self::structure().is_squarefree(self)
931    }
932}
933impl<R: MetaType> MetaFactoringMonoidNaturalExponent for R where
934    Self::Signature: FactoringMonoidNaturalExponentSignature
935{
936}
937
938impl<FS: FieldSignature> UniqueFactorizationMonoidSignature for FS {
939    type FactoredExponent = NaturalCanonicalStructure;
940
941    fn factorization_exponents(&self) -> &Self::FactoredExponent {
942        Natural::structure_ref()
943    }
944
945    fn into_factorization_exponents(self) -> Self::FactoredExponent {
946        Natural::structure()
947    }
948
949    fn try_is_irreducible(&self, _a: &Self::Set) -> Option<bool> {
950        Some(false)
951    }
952
953    fn factorization_pow(&self, a: &Self::Set, k: &Natural) -> Self::Set {
954        self.nat_pow(a, k)
955    }
956}
957
958impl<FS: FieldSignature> FactoringMonoidSignature for FS {
959    fn factor_unchecked(
960        &self,
961        a: &Self::Set,
962    ) -> Factored<Self::Set, <Self::FactoredExponent as SetSignature>::Set> {
963        if self.is_zero(a) {
964            Factored::Zero
965        } else {
966            Factored::NonZero(NonZeroFactored {
967                unit: a.clone(),
968                powers: vec![],
969            })
970        }
971    }
972}
973
974#[derive(Debug)]
975pub enum FindFactorResult<Element> {
976    Irreducible,
977    Composite(Element, Element),
978}
979
980pub fn factorize_by_find_factor<
981    Exponent: SemiRingSignature + CancellativeAdditionSignature + OrdSignature,
982    RS: UniqueFactorizationMonoidSignature<FactoredExponent = Exponent> + ZeroEqSignature,
983>(
984    ring: &RS,
985    elem: RS::Set,
986    partial_factor: &impl Fn(RS::Set) -> FindFactorResult<RS::Set>,
987) -> Factored<RS::Set, Exponent::Set> {
988    debug_assert!(!ring.is_zero(&elem));
989    if ring.is_unit(&elem) {
990        ring.factorizations().new_unit_unchecked(elem)
991    } else {
992        debug_assert!(!ring.is_unit(&elem));
993        match partial_factor(elem.clone()) {
994            FindFactorResult::Composite(g, h) => ring.factorizations().mul(
995                &factorize_by_find_factor(ring, g, partial_factor),
996                &factorize_by_find_factor(ring, h, partial_factor),
997            ),
998            FindFactorResult::Irreducible => {
999                //f is irreducible
1000                ring.factorizations().new_irreducible_unchecked(elem)
1001            }
1002        }
1003    }
1004}
1005
1006#[cfg(test)]
1007mod tests {
1008    use super::*;
1009    use crate::structure::FactoringMonoidSignature;
1010    use algebraeon_nzq::{Integer, Natural};
1011    use algebraeon_sets::structure::MetaType;
1012
1013    #[test]
1014    fn factorization_invariants() {
1015        let f = Factored::NonZero(NonZeroFactored {
1016            unit: Integer::from(-1),
1017            powers: vec![
1018                (Integer::from(2), Natural::from(2u8)),
1019                (Integer::from(3), Natural::from(1u8)),
1020            ],
1021        });
1022        Integer::structure()
1023            .factorizations()
1024            .is_element(&f)
1025            .unwrap();
1026
1027        let f = Factored::NonZero(NonZeroFactored {
1028            unit: Integer::from(1),
1029            powers: vec![],
1030        });
1031        Integer::structure()
1032            .factorizations()
1033            .is_element(&f)
1034            .unwrap();
1035
1036        let f = Factored::NonZero(NonZeroFactored {
1037            unit: Integer::from(-1),
1038            powers: vec![
1039                (Integer::from(2), Natural::from(2u8)),
1040                (Integer::from(3), Natural::from(1u8)),
1041                (Integer::from(5), Natural::from(0u8)),
1042            ],
1043        });
1044        assert!(
1045            Integer::structure()
1046                .factorizations()
1047                .is_element(&f)
1048                .is_err(),
1049            "can't have a power of zero"
1050        );
1051
1052        let f = Factored::NonZero(NonZeroFactored {
1053            unit: Integer::from(3),
1054            powers: vec![(Integer::from(2), Natural::from(2u8))],
1055        });
1056        assert!(
1057            Integer::structure()
1058                .factorizations()
1059                .is_element(&f)
1060                .is_err(),
1061            "unit should be a unit"
1062        );
1063
1064        let f = Factored::NonZero(NonZeroFactored {
1065            unit: Integer::from(1),
1066            powers: vec![
1067                (Integer::from(0), Natural::from(1u8)),
1068                (Integer::from(3), Natural::from(1u8)),
1069            ],
1070        });
1071        assert!(
1072            Integer::structure()
1073                .factorizations()
1074                .is_element(&f)
1075                .is_err(),
1076            "prime factors must not be zero"
1077        );
1078
1079        let f = Factored::NonZero(NonZeroFactored {
1080            unit: Integer::from(-1),
1081            powers: vec![
1082                (Integer::from(4), Natural::from(1u8)),
1083                (Integer::from(3), Natural::from(1u8)),
1084            ],
1085        });
1086        assert!(
1087            Integer::structure()
1088                .factorizations()
1089                .is_element(&f)
1090                .is_err(),
1091            "prime factors must be prime"
1092        );
1093
1094        let f = Factored::NonZero(NonZeroFactored {
1095            unit: Integer::from(-1),
1096            powers: vec![
1097                (Integer::from(-2), Natural::from(2u8)),
1098                (Integer::from(3), Natural::from(1u8)),
1099            ],
1100        });
1101        assert!(
1102            Integer::structure()
1103                .factorizations()
1104                .is_element(&f)
1105                .is_err(),
1106            "prime factors must be favoriate associate"
1107        );
1108    }
1109
1110    #[test]
1111    fn test_count_divideisors() {
1112        for a in 1..25 {
1113            println!("a = {}", a);
1114            let b = Integer::from(a);
1115            println!("b = {}", b);
1116            let fs = Integer::structure().factor(&b);
1117            println!("fs = {:?}", fs);
1118            assert_eq!(
1119                Integer::structure()
1120                    .factorizations()
1121                    .count_divideisors(&fs)
1122                    .unwrap(),
1123                Natural::from(
1124                    Integer::structure()
1125                        .factorizations()
1126                        .divisors(&fs)
1127                        .unwrap()
1128                        .collect::<Vec<Integer>>()
1129                        .len()
1130                )
1131            );
1132        }
1133    }
1134}
algebraeon_rings/structure/factorization.rs

algebraeon_rings/structure/
factorization.rs
