algebraeon_rings/integer/
ideal.rs

1use crate::structure::*;
2use algebraeon_nzq::{traits::Abs, *};
3use algebraeon_sets::structure::{
4    BorrowedStructure, EqSignature, MetaType, SetSignature, Signature,
5};
6
7#[derive(Debug, Clone, PartialEq, Eq)]
8pub struct IntegerIdealsStructure<B: BorrowedStructure<IntegerCanonicalStructure>> {
9    integers: B,
10}
11
12impl RingToIdealsSignature for IntegerCanonicalStructure {
13    type Ideals<SelfB: BorrowedStructure<IntegerCanonicalStructure>> =
14        IntegerIdealsStructure<SelfB>;
15
16    fn ideals(&self) -> Self::Ideals<&Self> {
17        IntegerIdealsStructure { integers: self }
18    }
19
20    fn into_ideals(self) -> Self::Ideals<Self> {
21        IntegerIdealsStructure { integers: self }
22    }
23}
24
25impl<B: BorrowedStructure<IntegerCanonicalStructure>> Signature for IntegerIdealsStructure<B> {}
26
27impl<B: BorrowedStructure<IntegerCanonicalStructure>> SetSignature for IntegerIdealsStructure<B> {
28    type Set = Natural;
29    fn is_element(&self, _x: &Self::Set) -> Result<(), String> {
30        Ok(())
31    }
32}
33
34impl<B: BorrowedStructure<IntegerCanonicalStructure>> IdealsSignature<IntegerCanonicalStructure, B>
35    for IntegerIdealsStructure<B>
36{
37    fn ring(&self) -> &IntegerCanonicalStructure {
38        self.integers.borrow()
39    }
40}
41
42impl<B: BorrowedStructure<IntegerCanonicalStructure>> EqSignature for IntegerIdealsStructure<B> {
43    fn equal(&self, a: &Self::Set, b: &Self::Set) -> bool {
44        a == b
45    }
46}
47
48impl<B: BorrowedStructure<IntegerCanonicalStructure>> RinglikeSpecializationSignature
49    for IntegerIdealsStructure<B>
50{
51}
52
53impl<B: BorrowedStructure<IntegerCanonicalStructure>> ZeroSignature for IntegerIdealsStructure<B> {
54    fn zero(&self) -> Self::Set {
55        Natural::ZERO
56    }
57}
58
59impl<B: BorrowedStructure<IntegerCanonicalStructure>> AdditionSignature
60    for IntegerIdealsStructure<B>
61{
62    fn add(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
63        gcd(a.clone(), b.clone())
64    }
65}
66
67impl<B: BorrowedStructure<IntegerCanonicalStructure>> AdditiveMonoidSignature
68    for IntegerIdealsStructure<B>
69{
70}
71
72impl<B: BorrowedStructure<IntegerCanonicalStructure>> TryNegateSignature
73    for IntegerIdealsStructure<B>
74{
75    fn try_neg(&self, a: &Self::Set) -> Option<Self::Set> {
76        if self.is_zero(a) {
77            Some(self.zero())
78        } else {
79            None
80        }
81    }
82}
83
84impl<B: BorrowedStructure<IntegerCanonicalStructure>> OneSignature for IntegerIdealsStructure<B> {
85    fn one(&self) -> Self::Set {
86        Natural::ONE
87    }
88}
89
90impl<B: BorrowedStructure<IntegerCanonicalStructure>> MultiplicationSignature
91    for IntegerIdealsStructure<B>
92{
93    fn mul(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
94        a * b
95    }
96}
97
98impl<B: BorrowedStructure<IntegerCanonicalStructure>> CommutativeMultiplicationSignature
99    for IntegerIdealsStructure<B>
100{
101}
102
103impl<B: BorrowedStructure<IntegerCanonicalStructure>> MultiplicativeMonoidSignature
104    for IntegerIdealsStructure<B>
105{
106}
107
108impl<B: BorrowedStructure<IntegerCanonicalStructure>> MultiplicativeAbsorptionMonoidSignature
109    for IntegerIdealsStructure<B>
110{
111}
112
113impl<B: BorrowedStructure<IntegerCanonicalStructure>> LeftDistributiveMultiplicationOverAddition
114    for IntegerIdealsStructure<B>
115{
116}
117
118impl<B: BorrowedStructure<IntegerCanonicalStructure>> RightDistributiveMultiplicationOverAddition
119    for IntegerIdealsStructure<B>
120{
121}
122
123impl<B: BorrowedStructure<IntegerCanonicalStructure>> SemiRingSignature
124    for IntegerIdealsStructure<B>
125{
126}
127
128impl<B: BorrowedStructure<IntegerCanonicalStructure>>
129    IdealsArithmeticSignature<IntegerCanonicalStructure, B> for IntegerIdealsStructure<B>
130{
131    fn principal_ideal(&self, a: &Integer) -> Self::Set {
132        Abs::abs(a)
133    }
134
135    fn contains_ideal(&self, a: &Self::Set, b: &Self::Set) -> bool {
136        b % a == Natural::ZERO
137    }
138
139    fn intersect(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
140        lcm(a.clone(), b.clone())
141    }
142
143    fn quotient(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
144        if b == &Natural::ZERO {
145            Natural::ONE
146        } else {
147            a / gcd(a.clone(), b.clone())
148        }
149    }
150}
151
152impl<B: BorrowedStructure<IntegerCanonicalStructure>>
153    PrincipalIdealsSignature<IntegerCanonicalStructure, B> for IntegerIdealsStructure<B>
154{
155    fn ideal_generator(&self, ideal: &Natural) -> Integer {
156        Integer::from(ideal)
157    }
158}
159
160impl<B: BorrowedStructure<IntegerCanonicalStructure>>
161    DedekindDomainIdealsSignature<IntegerCanonicalStructure, B> for IntegerIdealsStructure<B>
162{
163}
164
165impl<B: BorrowedStructure<IntegerCanonicalStructure>> TryReciprocalSignature
166    for IntegerIdealsStructure<B>
167{
168    fn try_reciprocal(&self, a: &Self::Set) -> Option<Self::Set> {
169        self.factorization_exponents().try_reciprocal(a)
170    }
171}
172
173impl<B: BorrowedStructure<IntegerCanonicalStructure>> FavoriteAssociateSignature
174    for IntegerIdealsStructure<B>
175{
176    fn factor_fav_assoc(&self, a: &Self::Set) -> (Self::Set, Self::Set) {
177        self.factorization_exponents().factor_fav_assoc(a)
178    }
179}
180
181impl<B: BorrowedStructure<IntegerCanonicalStructure>> UniqueFactorizationMonoidSignature
182    for IntegerIdealsStructure<B>
183{
184    type FactoredExponent = NaturalCanonicalStructure;
185
186    fn factorization_exponents(&self) -> &Self::FactoredExponent {
187        Natural::structure_ref()
188    }
189
190    fn into_factorization_exponents(self) -> Self::FactoredExponent {
191        Natural::structure()
192    }
193
194    fn factorization_pow(&self, a: &Self::Set, k: &Natural) -> Self::Set {
195        self.factorization_exponents().nat_pow(a, k)
196    }
197
198    fn try_is_irreducible(&self, a: &Self::Set) -> Option<bool> {
199        self.factorization_exponents().try_is_irreducible(a)
200    }
201}
202
203impl<B: BorrowedStructure<IntegerCanonicalStructure>> FactoringMonoidSignature
204    for IntegerIdealsStructure<B>
205{
206    fn factor_unchecked(&self, ideal: &Natural) -> Factored<Natural, Natural> {
207        Natural::structure().factor_unchecked(ideal)
208    }
209}
210
211#[cfg(test)]
212mod tests {
213    use super::*;
214
215    #[test]
216    fn integer_ideals() {
217        assert!(Integer::ideals().equal(&Natural::from(3u32), &Natural::from(3u32)));
218
219        assert!(!Integer::ideals().equal(&Natural::from(2u32), &Natural::from(3u32)));
220
221        assert!(Integer::ideals().contains_ideal(&Natural::from(2u32), &Natural::from(6u32)));
222
223        assert!(!Integer::ideals().contains_ideal(&Natural::from(6u32), &Natural::from(2u32)));
224
225        assert!(!Integer::ideals().contains_ideal(&Natural::from(5u32), &Natural::from(7u32)));
226
227        assert!(Integer::ideals().equal(
228            &Integer::ideals().add(&Natural::from(6u32), &Natural::from(15u32)),
229            &Natural::from(3u32)
230        ));
231
232        assert!(Integer::ideals().equal(
233            &Integer::ideals().intersect(&Natural::from(6u32), &Natural::from(15u32)),
234            &Natural::from(30u32)
235        ));
236
237        assert!(Integer::ideals().equal(
238            &Integer::ideals().mul(&Natural::from(6u32), &Natural::from(15u32)),
239            &Natural::from(90u32)
240        ));
241
242        assert_eq!(Integer::ideals().generated_ideal(vec![-15, 6]), 3u32.into());
243    }
244
245    #[test]
246    fn factor_integer_ideal() {
247        let f = Integer::ideals().factor(&Integer::ideals().principal_ideal(&Integer::from(0)));
248        println!("{:?}", f);
249        assert!(f.is_zero());
250
251        let f = Integer::ideals().factor(&Integer::ideals().principal_ideal(&Integer::from(18)));
252        println!("{:?}", f);
253        assert!(!f.is_zero());
254    }
255}
algebraeon_rings/integer/ideal.rs

algebraeon_rings/integer/
ideal.rs
