algebraeon_rings/finite_fields/
modulo.rs

1use crate::structure::*;
2use algebraeon_nzq::traits::Abs;
3use algebraeon_nzq::*;
4use algebraeon_sets::structure::*;
5use std::{fmt::Display, hash::Hash};
6
7fn xgcd(mut x: usize, mut y: usize) -> (usize, isize, isize) {
8    let mut pa = 1;
9    let mut a = 0;
10    let mut pb = 0;
11    let mut b = 1;
12    while y != 0 {
13        let (q, r) = (x / y, x % y);
14        let new_a = pa - q as isize * a;
15        (a, pa) = (new_a, a);
16        let new_b = pb - q as isize * b;
17        (b, pb) = (new_b, b);
18        (x, y) = (y, r);
19    }
20    (x, pa, pb)
21}
22
23fn modulo(a: isize, n: usize) -> usize {
24    let mut a = a % n as isize;
25    if a < 0 {
26        a += n as isize;
27    }
28    a as usize
29}
30
31#[derive(Clone)]
32pub struct Modulo<const N: usize> {
33    x: usize,
34}
35
36impl<const N: usize> Modulo<N> {
37    pub const fn new(x: usize) -> Self {
38        Self { x }
39    }
40}
41
42impl<const N: usize> std::fmt::Debug for Modulo<N> {
43    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
44        f.debug_struct("Modulo")
45            .field("x", &self.x)
46            .field("N", &N)
47            .finish()
48    }
49}
50
51impl<const N: usize> Modulo<N> {
52    pub fn lift_nat(&self) -> Natural {
53        Natural::from(self.x)
54    }
55    pub fn lift_int(&self) -> Integer {
56        Integer::from(self.x)
57    }
58}
59
60impl<const N: usize> From<&Integer> for Modulo<N> {
61    fn from(value: &Integer) -> Self {
62        let value = value % Integer::from(N);
63        let value = value.abs();
64        Self {
65            x: value.try_into().unwrap(),
66        }
67    }
68}
69impl<const N: usize> From<Integer> for Modulo<N> {
70    fn from(value: Integer) -> Self {
71        let value = value % Integer::from(N);
72        let value = value.abs();
73        Self {
74            x: value.try_into().unwrap(),
75        }
76    }
77}
78impl<const N: usize> From<usize> for Modulo<N> {
79    fn from(value: usize) -> Self {
80        Self { x: value % N }
81    }
82}
83impl<const N: usize> From<isize> for Modulo<N> {
84    fn from(value: isize) -> Self {
85        Self {
86            x: modulo(value, N),
87        }
88    }
89}
90impl<const N: usize> From<i32> for Modulo<N> {
91    fn from(value: i32) -> Self {
92        Self {
93            x: modulo(value as isize, N),
94        }
95    }
96}
97
98impl<const N: usize> From<Modulo<N>> for usize {
99    fn from(value: Modulo<N>) -> Self {
100        value.x
101    }
102}
103
104impl<const N: usize> PartialEq for Modulo<N> {
105    fn eq(&self, other: &Self) -> bool {
106        self.x == other.x
107    }
108}
109impl<const N: usize> Eq for Modulo<N> {}
110impl<const N: usize> Hash for Modulo<N> {
111    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
112        self.x.hash(state);
113    }
114}
115
116impl<const N: usize> Display for Modulo<N> {
117    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
118        write!(f, "{}", self.x)
119    }
120}
121
122#[derive(Debug, Clone, PartialEq, Eq)]
123pub struct ModuloCanonicalStructure<const N: usize> {}
124
125impl<const N: usize> Signature for ModuloCanonicalStructure<N> {}
126
127impl<const N: usize> SetSignature for ModuloCanonicalStructure<N> {
128    type Set = Modulo<N>;
129
130    fn is_element(&self, _x: &Self::Set) -> Result<(), String> {
131        Ok(())
132    }
133}
134
135impl<const N: usize> MetaType for Modulo<N> {
136    type Signature = ModuloCanonicalStructure<N>;
137
138    fn structure() -> Self::Signature {
139        ModuloCanonicalStructure {}
140    }
141}
142
143impl<const N: usize> EqSignature for ModuloCanonicalStructure<N> {
144    fn equal(&self, a: &Self::Set, b: &Self::Set) -> bool {
145        a == b
146    }
147}
148
149impl<const N: usize> ToStringSignature for ModuloCanonicalStructure<N> {
150    fn to_string(&self, elem: &Self::Set) -> String {
151        format!("{}", elem)
152    }
153}
154
155impl<const N: usize> RinglikeSpecializationSignature for ModuloCanonicalStructure<N> {}
156
157impl<const N: usize> ZeroSignature for ModuloCanonicalStructure<N> {
158    fn zero(&self) -> Self::Set {
159        Modulo { x: 0 }
160    }
161}
162
163impl<const N: usize> AdditionSignature for ModuloCanonicalStructure<N> {
164    fn add(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
165        Modulo { x: (a.x + b.x) % N }
166    }
167}
168
169impl<const N: usize> CancellativeAdditionSignature for ModuloCanonicalStructure<N> {
170    fn try_sub(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
171        Some(self.sub(a, b))
172    }
173}
174
175impl<const N: usize> TryNegateSignature for ModuloCanonicalStructure<N> {
176    fn try_neg(&self, a: &Self::Set) -> Option<Self::Set> {
177        Some(self.neg(a))
178    }
179}
180
181impl<const N: usize> AdditiveMonoidSignature for ModuloCanonicalStructure<N> {}
182
183impl<const N: usize> AdditiveGroupSignature for ModuloCanonicalStructure<N> {
184    fn neg(&self, a: &Self::Set) -> Self::Set {
185        if a.x == 0 {
186            Modulo { x: 0 }
187        } else {
188            Modulo { x: N - a.x }
189        }
190    }
191}
192
193impl<const N: usize> OneSignature for ModuloCanonicalStructure<N> {
194    fn one(&self) -> Self::Set {
195        if N == 1 {
196            Modulo { x: 0 }
197        } else {
198            Modulo { x: 1 }
199        }
200    }
201}
202
203impl<const N: usize> MultiplicationSignature for ModuloCanonicalStructure<N> {
204    fn mul(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
205        Modulo { x: (a.x * b.x) % N }
206    }
207}
208
209impl<const N: usize> CommutativeMultiplicationSignature for ModuloCanonicalStructure<N> {}
210
211impl<const N: usize> MultiplicativeMonoidSignature for ModuloCanonicalStructure<N> {}
212
213impl<const N: usize> MultiplicativeAbsorptionMonoidSignature for ModuloCanonicalStructure<N> {}
214
215impl<const N: usize> LeftDistributiveMultiplicationOverAddition for ModuloCanonicalStructure<N> {}
216
217impl<const N: usize> RightDistributiveMultiplicationOverAddition for ModuloCanonicalStructure<N> {}
218
219impl<const N: usize> SemiRingSignature for ModuloCanonicalStructure<N> {}
220
221impl<const N: usize> RingSignature for ModuloCanonicalStructure<N> {}
222
223impl<const N: usize> CharacteristicSignature for ModuloCanonicalStructure<N> {
224    fn characteristic(&self) -> Natural {
225        Natural::from(N)
226    }
227}
228
229impl<const N: usize> TryReciprocalSignature for ModuloCanonicalStructure<N> {
230    fn try_reciprocal(&self, x: &Self::Set) -> Option<Self::Set> {
231        if x == &self.zero() {
232            None
233        } else {
234            let (g, a, b) = xgcd(x.x, N);
235            debug_assert_eq!(g as isize, a * x.x as isize + b * N as isize);
236            if g == 1 {
237                Some(Modulo { x: modulo(a, N) })
238            } else {
239                None
240            }
241        }
242    }
243}
244
245impl<const N: usize> CountableSetSignature for ModuloCanonicalStructure<N> {
246    fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> + Clone {
247        (0..N).map(Modulo::new)
248    }
249}
250
251impl<const N: usize> FiniteSetSignature for ModuloCanonicalStructure<N> {
252    fn size(&self) -> usize {
253        N
254    }
255}
256
257macro_rules! impl_field {
258    ($N: literal) => {
259        impl CancellativeMultiplicationSignature for ModuloCanonicalStructure<$N> {
260            fn try_divide(&self, top: &Self::Set, bot: &Self::Set) -> Option<Self::Set> {
261                Some(self.mul(top, &self.try_reciprocal(bot)?))
262            }
263        }
264
265        impl MultiplicativeIntegralMonoidSignature for ModuloCanonicalStructure<$N> {}
266
267        impl IntegralDomainSignature for ModuloCanonicalStructure<$N> {}
268
269        impl FieldSignature for ModuloCanonicalStructure<$N> {}
270
271        impl<B: BorrowedStructure<ModuloCanonicalStructure<$N>>> CountableSetSignature
272            for MultiplicativeMonoidUnitsStructure<ModuloCanonicalStructure<$N>, B>
273        {
274            fn generate_all_elements(
275                &self,
276            ) -> impl std::iter::Iterator<Item = Modulo<$N>> + std::clone::Clone {
277                (1..$N).map(|i| Modulo { x: i })
278            }
279        }
280
281        impl<B: BorrowedStructure<ModuloCanonicalStructure<$N>>> FiniteSetSignature
282            for MultiplicativeMonoidUnitsStructure<ModuloCanonicalStructure<$N>, B>
283        {
284        }
285
286        impl FiniteFieldSignature for ModuloCanonicalStructure<$N> {
287            fn characteristic_and_power(&self) -> (Natural, Natural) {
288                (Natural::from($N as usize), Natural::from(1u8))
289            }
290        }
291    };
292}
293
294impl_field!(2);
295impl_field!(3);
296impl_field!(5);
297impl_field!(7);
298impl_field!(11);
299impl_field!(13);
300impl_field!(17);
301impl_field!(19);
302impl_field!(23);
303impl_field!(29);
304impl_field!(31);
305impl_field!(37);
306impl_field!(41);
307impl_field!(43);
308impl_field!(47);
309impl_field!(53);
310impl_field!(59);
311impl_field!(61);
312impl_field!(67);
313impl_field!(71);
314impl_field!(73);
315impl_field!(79);
316impl_field!(83);
317impl_field!(89);
318impl_field!(97);
319impl_field!(101);
320impl_field!(103);
321impl_field!(107);
322impl_field!(109);
323impl_field!(113);
324impl_field!(127);
325impl_field!(131);
326impl_field!(137);
327impl_field!(139);
328impl_field!(149);
329impl_field!(151);
330impl_field!(157);
331impl_field!(163);
332impl_field!(167);
333impl_field!(173);
334impl_field!(179);
335impl_field!(181);
336impl_field!(191);
337impl_field!(193);
338impl_field!(197);
339impl_field!(199);
340impl_field!(211);
341impl_field!(223);
342impl_field!(227);
343impl_field!(229);
344impl_field!(233);
345impl_field!(239);
346impl_field!(241);
347impl_field!(251);
348impl_field!(257);
349impl_field!(263);
350impl_field!(269);
351impl_field!(271);
352impl_field!(277);
353impl_field!(281);
354impl_field!(283);
355impl_field!(293);
356impl_field!(307);
357impl_field!(311);
358impl_field!(313);
359impl_field!(317);
360impl_field!(331);
361impl_field!(337);
362impl_field!(347);
363impl_field!(349);
364impl_field!(353);
365impl_field!(359);
366impl_field!(367);
367impl_field!(373);
368impl_field!(379);
369impl_field!(383);
370impl_field!(389);
371impl_field!(397);
372impl_field!(401);
373impl_field!(409);
374impl_field!(419);
375impl_field!(421);
376impl_field!(431);
377impl_field!(433);
378impl_field!(439);
379impl_field!(443);
380impl_field!(449);
381impl_field!(457);
382impl_field!(461);
383impl_field!(463);
384impl_field!(467);
385impl_field!(479);
386impl_field!(487);
387impl_field!(491);
388impl_field!(499);
389impl_field!(503);
390impl_field!(509);
391impl_field!(521);
392impl_field!(523);
393impl_field!(541);
394impl_field!(547);
395impl_field!(557);
396impl_field!(563);
397impl_field!(569);
398impl_field!(571);
399impl_field!(577);
400impl_field!(587);
401impl_field!(593);
402impl_field!(599);
403impl_field!(601);
404impl_field!(607);
405impl_field!(613);
406impl_field!(617);
407impl_field!(619);
408impl_field!(631);
409impl_field!(641);
410impl_field!(643);
411impl_field!(647);
412impl_field!(653);
413impl_field!(659);
414impl_field!(661);
415impl_field!(673);
416impl_field!(677);
417impl_field!(683);
418impl_field!(691);
419impl_field!(701);
420impl_field!(709);
421impl_field!(719);
422impl_field!(727);
423impl_field!(733);
424impl_field!(739);
425impl_field!(743);
426impl_field!(751);
427impl_field!(757);
428impl_field!(761);
429impl_field!(769);
430impl_field!(773);
431impl_field!(787);
432impl_field!(797);
433impl_field!(809);
434impl_field!(811);
435impl_field!(821);
436impl_field!(823);
437impl_field!(827);
438impl_field!(829);
439impl_field!(839);
440impl_field!(853);
441impl_field!(857);
442impl_field!(859);
443impl_field!(863);
444impl_field!(877);
445impl_field!(881);
446impl_field!(883);
447impl_field!(887);
448impl_field!(907);
449impl_field!(911);
450impl_field!(919);
451impl_field!(929);
452impl_field!(937);
453impl_field!(941);
454impl_field!(947);
455impl_field!(953);
456impl_field!(967);
457impl_field!(971);
458impl_field!(977);
459impl_field!(983);
460impl_field!(991);
461impl_field!(997);
462//TODO: add more or generate these with a proc macro
463
464#[cfg(test)]
465mod tests {
466    use super::*;
467
468    #[test]
469    fn test_gcd_lcm() {
470        for x in 0..100 {
471            for y in 0..100 {
472                let (g, a, b) = xgcd(x, y);
473                assert_eq!(g as isize, a * x as isize + b * y as isize);
474            }
475        }
476    }
477
478    #[test]
479    fn count_elements() {
480        assert_eq!(Modulo::<26>::structure().list_all_elements().len(), 26);
481    }
482}
algebraeon_rings/finite_fields/modulo.rs

algebraeon_rings/finite_fields/
modulo.rs
