algebraeon_rings/integer/
mod.rs1use crate::algebraic_number_field::AlgebraicIntegerRingSignature;
2use crate::structure::*;
3use algebraeon_nzq::traits::Abs;
4use algebraeon_nzq::traits::DivMod;
5use algebraeon_nzq::*;
6use algebraeon_sets::structure::BorrowedStructure;
7use algebraeon_sets::structure::CountableSetSignature;
8use algebraeon_sets::structure::EqSignature;
9use algebraeon_sets::structure::FiniteSetSignature;
10use algebraeon_sets::structure::MetaType;
11use std::collections::HashSet;
12
13pub mod berlekamp_zassenhaus;
14pub mod ideal;
15pub mod modulo;
16pub mod polynomial;
17pub mod zimmermann_polys;
18
19impl RinglikeSpecializationSignature for IntegerCanonicalStructure {
20 fn try_ring_restructure(&self) -> Option<impl EqSignature<Set = Self::Set> + RingSignature> {
21 Some(self.clone())
22 }
23
24 fn try_char_zero_ring_restructure(
25 &self,
26 ) -> Option<impl EqSignature<Set = Self::Set> + CharZeroRingSignature> {
27 Some(self.clone())
28 }
29}
30
31impl ZeroSignature for IntegerCanonicalStructure {
32 fn zero(&self) -> Self::Set {
33 Integer::ZERO
34 }
35}
36
37impl AdditionSignature for IntegerCanonicalStructure {
38 fn add(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
39 a + b
40 }
41}
42
43impl CancellativeAdditionSignature for IntegerCanonicalStructure {
44 fn try_sub(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
45 Some(self.sub(a, b))
46 }
47}
48
49impl TryNegateSignature for IntegerCanonicalStructure {
50 fn try_neg(&self, a: &Self::Set) -> Option<Self::Set> {
51 Some(self.neg(a))
52 }
53}
54
55impl AdditiveMonoidSignature for IntegerCanonicalStructure {}
56
57impl AdditiveGroupSignature for IntegerCanonicalStructure {
58 fn neg(&self, a: &Self::Set) -> Self::Set {
59 -a
60 }
61
62 fn sub(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
63 a - b
64 }
65}
66
67impl OneSignature for IntegerCanonicalStructure {
68 fn one(&self) -> Self::Set {
69 Integer::ONE
70 }
71}
72
73impl MultiplicationSignature for IntegerCanonicalStructure {
74 fn mul(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
75 a * b
76 }
77}
78
79impl CommutativeMultiplicationSignature for IntegerCanonicalStructure {}
80
81impl MultiplicativeMonoidSignature for IntegerCanonicalStructure {}
82
83impl MultiplicativeAbsorptionMonoidSignature for IntegerCanonicalStructure {}
84
85impl LeftDistributiveMultiplicationOverAddition for IntegerCanonicalStructure {}
86
87impl RightDistributiveMultiplicationOverAddition for IntegerCanonicalStructure {}
88
89impl SemiRingSignature for IntegerCanonicalStructure {}
90
91impl RingSignature for IntegerCanonicalStructure {
92 fn is_reduced(&self) -> Result<bool, String> {
93 Ok(true)
94 }
95}
96
97impl CharacteristicSignature for IntegerCanonicalStructure {
98 fn characteristic(&self) -> Natural {
99 Natural::ZERO
100 }
101}
102
103impl TryReciprocalSignature for IntegerCanonicalStructure {
104 fn try_reciprocal(&self, a: &Self::Set) -> Option<Self::Set> {
105 self.try_divide(&self.one(), a)
106 }
107}
108
109impl CancellativeMultiplicationSignature for IntegerCanonicalStructure {
110 fn try_divide(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
111 match self.quorem(a, b) {
112 Some((q, r)) => {
113 if r == self.zero() {
114 Some(q)
115 } else {
116 None
117 }
118 }
119 None => None,
120 }
121 }
122}
123
124impl MultiplicativeIntegralMonoidSignature for IntegerCanonicalStructure {}
125
126impl IntegralDomainSignature for IntegerCanonicalStructure {}
127
128impl OrderedRingSignature for IntegerCanonicalStructure {
129 fn ring_cmp(&self, a: &Self::Set, b: &Self::Set) -> std::cmp::Ordering {
130 Self::Set::cmp(a, b)
131 }
132}
133
134impl<B: BorrowedStructure<IntegerCanonicalStructure>> CountableSetSignature
135 for MultiplicativeMonoidUnitsStructure<IntegerCanonicalStructure, B>
136{
137 fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> + Clone {
138 self.list_all_elements().into_iter()
139 }
140}
141
142impl<B: BorrowedStructure<IntegerCanonicalStructure>> FiniteSetSignature
143 for MultiplicativeMonoidUnitsStructure<IntegerCanonicalStructure, B>
144{
145 fn list_all_elements(&self) -> Vec<Self::Set> {
146 vec![Integer::ONE, -Integer::ONE]
147 }
148}
149
150impl FavoriteAssociateSignature for IntegerCanonicalStructure {
151 fn factor_fav_assoc(&self, a: &Self::Set) -> (Self::Set, Self::Set) {
152 #[allow(clippy::comparison_chain)]
153 if a == &Integer::ZERO {
154 (Integer::ONE, Integer::ZERO)
155 } else if a < &Integer::ZERO {
156 (-Integer::ONE, -a)
157 } else {
158 (Integer::ONE, a.clone())
159 }
160 }
161}
162
163impl UniqueFactorizationMonoidSignature for IntegerCanonicalStructure {
164 type FactoredExponent = NaturalCanonicalStructure;
165
166 fn factorization_exponents(&self) -> &Self::FactoredExponent {
167 Natural::structure_ref()
168 }
169
170 fn into_factorization_exponents(self) -> Self::FactoredExponent {
171 Natural::structure()
172 }
173
174 fn try_is_irreducible(&self, a: &Self::Set) -> Option<bool> {
175 Some(Abs::abs(a).is_irreducible())
176 }
177
178 fn factorization_pow(&self, a: &Self::Set, k: &Natural) -> Self::Set {
179 self.nat_pow(a, k)
180 }
181}
182
183impl FactoringMonoidSignature for IntegerCanonicalStructure {
184 fn factor_unchecked(&self, a: &Self::Set) -> Factored<Integer, Natural> {
185 if a == &Integer::ZERO {
186 Factored::Zero
187 } else {
188 let unit = if a < &Integer::ZERO {
189 Integer::from(-1)
190 } else {
191 Integer::from(1)
192 };
193 let f = Abs::abs(a).factor();
194 Integer::structure()
195 .factorizations()
196 .new_unit_and_powers_unchecked(
197 unit,
198 f.into_powers()
199 .unwrap()
200 .into_iter()
201 .map(|(p, k)| (Integer::from(p), k))
202 .collect(),
203 )
204 }
205 }
206}
207
208impl EuclideanDivisionSignature for IntegerCanonicalStructure {
209 fn norm(&self, elem: &Self::Set) -> Option<Natural> {
210 if elem == &Integer::ZERO {
211 None
212 } else {
213 Some(Abs::abs(elem))
214 }
215 }
216
217 fn quorem(&self, a: &Self::Set, b: &Self::Set) -> Option<(Self::Set, Self::Set)> {
218 if b == &Integer::ZERO {
219 None
220 } else {
221 Some(a.div_mod(b.clone()))
222 }
223 }
224}
225
226impl GreatestCommonDivisorSignature for IntegerCanonicalStructure {
227 fn gcd(&self, x: &Self::Set, y: &Self::Set) -> Self::Set {
228 Integer::structure().euclidean_gcd(x.clone(), y.clone())
229 }
230}
231
232impl BezoutDomainSignature for IntegerCanonicalStructure {
233 fn xgcd(&self, x: &Self::Set, y: &Self::Set) -> (Self::Set, Self::Set, Self::Set) {
234 Integer::euclidean_xgcd(x.clone(), y.clone())
235 }
236}
237
238impl DedekindDomainSignature for IntegerCanonicalStructure {}
239
240impl CharZeroRingSignature for IntegerCanonicalStructure {
241 fn try_to_int(&self, x: &Integer) -> Option<Integer> {
242 Some(x.clone())
243 }
244}
245
246impl AlgebraicIntegerRingSignature<RationalCanonicalStructure> for IntegerCanonicalStructure {
247 fn anf(&self) -> &RationalCanonicalStructure {
248 Rational::structure_ref()
249 }
250
251 fn to_anf(&self, x: &Integer) -> Rational {
252 Rational::from(x)
253 }
254
255 fn try_from_anf(&self, y: &Rational) -> Option<Integer> {
256 Integer::try_from_rat(y)
257 }
258
259 fn integral_basis(&self) -> Vec<Integer> {
260 vec![Integer::ONE]
261 }
262}
263
264impl ComplexSubsetSignature for IntegerCanonicalStructure {
265 fn as_f64_real_and_imaginary_parts(&self, z: &Self::Set) -> (f64, f64) {
266 (self.as_f64(z), 0.0)
267 }
268
269 fn as_f32_real_and_imaginary_parts(&self, z: &Self::Set) -> (f32, f32) {
270 (self.as_f32(z), 0.0)
271 }
272}
273
274impl RealSubsetSignature for IntegerCanonicalStructure {
275 fn as_f64(&self, x: &Self::Set) -> f64 {
276 x.into()
277 }
278
279 fn as_f32(&self, x: &Self::Set) -> f32 {
280 x.into()
281 }
282}
283
284impl MultiplicativeMonoidSquareOpsSignature for IntegerCanonicalStructure {
285 fn sqrt_if_square(&self, a: &Integer) -> Option<Integer> {
286 a.sqrt_if_square().map(|n: Natural| Integer::from(n))
287 }
288
289 fn is_square(&self, a: &Integer) -> bool {
290 a.is_square()
291 }
292}
293
294#[derive(Debug, Clone, PartialEq, Eq, Hash)]
295pub enum IntegerInitialRingGeneratorNeverType {}
296
297impl FreeRingSignature for IntegerCanonicalStructure {
298 type Generator = IntegerInitialRingGeneratorNeverType;
299
300 fn free_generators(&self) -> HashSet<Self::Generator> {
301 HashSet::new()
302 }
303}
304
305#[cfg(test)]
306mod tests {
307 use super::*;
308
309 #[test]
310 fn integer_gcd() {
311 assert_eq!(
312 Integer::euclidean_gcd(Integer::from(0), Integer::from(0)),
313 Integer::from(0)
314 );
315
316 assert_eq!(
317 Integer::euclidean_gcd(Integer::from(12), Integer::from(0)),
318 Integer::from(12)
319 );
320
321 assert_eq!(
322 Integer::euclidean_gcd(Integer::from(0), Integer::from(12)),
323 Integer::from(12)
324 );
325
326 assert_eq!(
327 Integer::euclidean_gcd(Integer::from(12), Integer::from(18)),
328 Integer::from(6)
329 );
330
331 assert_eq!(
332 Integer::gcd_by_factor(&Integer::from(0), &Integer::from(0)),
333 Integer::from(0)
334 );
335
336 assert_eq!(
337 Integer::gcd_by_factor(&Integer::from(12), &Integer::from(0)),
338 Integer::from(12)
339 );
340
341 assert_eq!(
342 Integer::gcd_by_factor(&Integer::from(0), &Integer::from(12)),
343 Integer::from(12)
344 );
345
346 assert_eq!(
347 Integer::gcd_by_factor(&Integer::from(12), &Integer::from(18)),
348 Integer::from(6)
349 );
350
351 assert_eq!(
352 Integer::lcm_by_factor(&Integer::from(12), &Integer::from(18)),
353 Some(Integer::from(36))
354 );
355
356 assert_eq!(
357 Integer::lcm_by_factor(&Integer::from(0), &Integer::from(18)),
358 None
359 );
360
361 assert_eq!(
362 Integer::lcm_by_factor(&Integer::from(12), &Integer::from(0)),
363 None
364 );
365
366 assert_eq!(
367 Integer::lcm_by_factor(&Integer::from(0), &Integer::from(0)),
368 None
369 );
370 }
371}