algebraeon_rings/structure/
quotient.rs

1use crate::structure::*;
2use algebraeon_sets::structure::*;
3use std::{borrow::Borrow, marker::PhantomData};
4
5/// A quotient of a Euclidean domain by a non-zero element.
6#[derive(Debug, Clone)]
7pub struct EuclideanRemainderQuotientStructure<
8    RS: EuclideanDomainSignature,
9    RSB: BorrowedStructure<RS>,
10    const IS_FIELD: bool,
11> {
12    _ring: PhantomData<RS>,
13    ring: RSB,
14    modulus: RS::Set,
15}
16
17impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
18    EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
19{
20    pub fn new_unchecked(ring: RSB, modulus: RS::Set) -> Self {
21        assert!(!ring.borrow().is_zero(&modulus));
22        Self {
23            _ring: PhantomData,
24            ring,
25            modulus,
26        }
27    }
28
29    pub fn ring(&self) -> &RS {
30        self.ring.borrow()
31    }
32
33    pub fn modulus(&self) -> &RS::Set {
34        &self.modulus
35    }
36
37    pub fn reduce(&self, a: impl Borrow<RS::Set>) -> RS::Set {
38        self.ring().rem(a.borrow(), &self.modulus)
39    }
40}
41
42impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>>
43    EuclideanRemainderQuotientStructure<RS, RSB, false>
44{
45    fn new_ring(ring: RSB, modulus: RS::Set) -> Self {
46        Self::new_unchecked(ring, modulus)
47    }
48}
49
50impl<RS: EuclideanDomainSignature + FactoringMonoidSignature, RSB: BorrowedStructure<RS>>
51    EuclideanRemainderQuotientStructure<RS, RSB, true>
52{
53    fn new_field_unchecked(ring: RSB, modulus: RS::Set) -> Self {
54        debug_assert!(ring.borrow().is_irreducible(&modulus));
55        Self::new_unchecked(ring, modulus)
56    }
57
58    fn new_field(ring: RSB, modulus: RS::Set) -> Result<Self, ()> {
59        if ring.borrow().is_irreducible(&modulus) {
60            Ok(Self::new_unchecked(ring, modulus))
61        } else {
62            Err(())
63        }
64    }
65}
66
67pub trait RingToQuotientRingSignature: EuclideanDomainSignature {
68    fn quotient_ring(
69        &self,
70        modulus: Self::Set,
71    ) -> EuclideanRemainderQuotientStructure<Self, &Self, false> {
72        EuclideanRemainderQuotientStructure::new_ring(self, modulus)
73    }
74
75    fn into_quotient_ring(
76        self,
77        modulus: Self::Set,
78    ) -> EuclideanRemainderQuotientStructure<Self, Self, false> {
79        EuclideanRemainderQuotientStructure::new_ring(self, modulus)
80    }
81}
82impl<Ring: EuclideanDomainSignature> RingToQuotientRingSignature for Ring {}
83
84pub trait RingToQuotientFieldSignature:
85    EuclideanDomainSignature + FactoringMonoidSignature
86{
87    fn quotient_field(
88        &self,
89        modulus: Self::Set,
90    ) -> Result<EuclideanRemainderQuotientStructure<Self, &Self, true>, ()> {
91        EuclideanRemainderQuotientStructure::new_field(self, modulus)
92    }
93
94    fn into_quotient_field(
95        self,
96        modulus: Self::Set,
97    ) -> Result<EuclideanRemainderQuotientStructure<Self, Self, true>, ()> {
98        EuclideanRemainderQuotientStructure::new_field(self, modulus)
99    }
100
101    fn quotient_field_unchecked(
102        &self,
103        modulus: Self::Set,
104    ) -> EuclideanRemainderQuotientStructure<Self, &Self, true> {
105        EuclideanRemainderQuotientStructure::new_field_unchecked(self, modulus)
106    }
107
108    fn into_quotient_field_unchecked(
109        self,
110        modulus: Self::Set,
111    ) -> EuclideanRemainderQuotientStructure<Self, Self, true> {
112        EuclideanRemainderQuotientStructure::new_field_unchecked(self, modulus)
113    }
114}
115impl<Ring: EuclideanDomainSignature + FactoringMonoidSignature> RingToQuotientFieldSignature
116    for Ring
117{
118}
119
120impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool> PartialEq
121    for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
122{
123    fn eq(&self, other: &Self) -> bool {
124        if self.ring == other.ring {
125            debug_assert_eq!(
126                self.ring().equal(&self.modulus, &other.modulus),
127                other.ring().equal(&self.modulus, &other.modulus)
128            );
129            self.ring().equal(&self.modulus, &other.modulus)
130        } else {
131            false
132        }
133    }
134}
135
136impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool> Eq
137    for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
138{
139}
140
141impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool> Signature
142    for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
143{
144}
145
146impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool> SetSignature
147    for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
148{
149    type Set = RS::Set;
150
151    fn is_element(&self, _x: &Self::Set) -> Result<(), String> {
152        Ok(())
153    }
154}
155
156impl<
157    RS: EuclideanDomainSignature + ToStringSignature,
158    RSB: BorrowedStructure<RS>,
159    const IS_FIELD: bool,
160> ToStringSignature for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
161{
162    fn to_string(&self, elem: &Self::Set) -> String {
163        self.ring().to_string(elem)
164    }
165}
166
167impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool> EqSignature
168    for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
169{
170    fn equal(&self, a: &Self::Set, b: &Self::Set) -> bool {
171        self.ring().is_zero(
172            &self
173                .ring()
174                .rem(&self.ring().add(a, &self.ring().neg(b)), &self.modulus),
175        )
176    }
177}
178
179impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
180    RinglikeSpecializationSignature for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
181{
182    fn try_ring_restructure(&self) -> Option<impl EqSignature<Set = Self::Set> + RingSignature> {
183        Some(self.clone())
184    }
185}
186
187impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool> ZeroSignature
188    for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
189{
190    fn zero(&self) -> Self::Set {
191        self.ring().zero()
192    }
193}
194
195impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
196    AdditionSignature for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
197{
198    fn add(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
199        self.ring().rem(&self.ring().add(a, b), &self.modulus)
200    }
201}
202
203impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
204    CancellativeAdditionSignature for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
205{
206    fn try_sub(&self, a: &Self::Set, b: &Self::Set) -> Option<Self::Set> {
207        Some(self.sub(a, b))
208    }
209}
210
211impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
212    TryNegateSignature for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
213{
214    fn try_neg(&self, a: &Self::Set) -> Option<Self::Set> {
215        Some(self.neg(a))
216    }
217}
218
219impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
220    AdditiveMonoidSignature for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
221{
222}
223
224impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
225    AdditiveGroupSignature for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
226{
227    fn neg(&self, a: &Self::Set) -> Self::Set {
228        self.ring().neg(a)
229    }
230
231    fn sub(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
232        self.ring().sub(a, b)
233    }
234}
235
236impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool> OneSignature
237    for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
238{
239    fn one(&self) -> Self::Set {
240        self.ring().one()
241    }
242}
243
244impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
245    MultiplicationSignature for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
246{
247    fn mul(&self, a: &Self::Set, b: &Self::Set) -> Self::Set {
248        self.ring().rem(&self.ring().mul(a, b), &self.modulus)
249    }
250}
251
252impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
253    CommutativeMultiplicationSignature for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
254{
255}
256
257impl<
258    RS: EuclideanDomainSignature + FavoriteAssociateSignature,
259    RSB: BorrowedStructure<RS>,
260    const IS_FIELD: bool,
261> TryReciprocalSignature for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
262{
263    fn try_reciprocal(&self, x: &Self::Set) -> Option<Self::Set> {
264        if self.is_zero(x) {
265            None
266        } else {
267            let (g, a, b) = self.ring().euclidean_xgcd(x.clone(), self.modulus.clone());
268            debug_assert!(
269                self.ring().equal(
270                    &g,
271                    &self
272                        .ring()
273                        .add(&self.ring().mul(&a, x), &self.ring().mul(&b, &self.modulus))
274                )
275            );
276            if self.equal(&g, &self.one()) {
277                Some(self.reduce(a))
278            } else {
279                None
280            }
281        }
282    }
283}
284
285impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
286    MultiplicativeMonoidSignature for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
287{
288}
289
290impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
291    MultiplicativeAbsorptionMonoidSignature
292    for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
293{
294}
295
296impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
297    LeftDistributiveMultiplicationOverAddition
298    for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
299{
300}
301
302impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
303    RightDistributiveMultiplicationOverAddition
304    for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
305{
306}
307
308impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool>
309    SemiRingSignature for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
310{
311}
312
313impl<RS: EuclideanDomainSignature, RSB: BorrowedStructure<RS>, const IS_FIELD: bool> RingSignature
314    for EuclideanRemainderQuotientStructure<RS, RSB, IS_FIELD>
315{
316    fn is_reduced(&self) -> Result<bool, String> {
317        if IS_FIELD {
318            return Ok(true);
319        }
320        Err("not implemented yet: is_reduced for quotient rings that are not fields".to_string())
321    }
322}
323
324impl<RS: EuclideanDomainSignature + FavoriteAssociateSignature, RSB: BorrowedStructure<RS>>
325    CancellativeMultiplicationSignature for EuclideanRemainderQuotientStructure<RS, RSB, true>
326{
327    fn try_divide(&self, top: &Self::Set, bot: &Self::Set) -> Option<Self::Set> {
328        Some(self.mul(top, &self.try_reciprocal(bot)?))
329    }
330}
331
332impl<RS: EuclideanDomainSignature + FavoriteAssociateSignature, RSB: BorrowedStructure<RS>>
333    MultiplicativeIntegralMonoidSignature for EuclideanRemainderQuotientStructure<RS, RSB, true>
334{
335}
336
337impl<RS: EuclideanDomainSignature + FavoriteAssociateSignature, RSB: BorrowedStructure<RS>>
338    IntegralDomainSignature for EuclideanRemainderQuotientStructure<RS, RSB, true>
339{
340}
341
342impl<RS: EuclideanDomainSignature + FavoriteAssociateSignature, RSB: BorrowedStructure<RS>>
343    FieldSignature for EuclideanRemainderQuotientStructure<RS, RSB, true>
344{
345}
346
347#[cfg(test)]
348mod tests {
349    use super::*;
350    use algebraeon_nzq::*;
351
352    #[test]
353    fn test() {
354        let mod5 =
355            EuclideanRemainderQuotientStructure::new_field(Integer::structure(), Integer::from(5))
356                .unwrap();
357
358        assert!(
359            mod5.equal(
360                &mod5
361                    .try_divide(&Integer::from(3), &Integer::from(2))
362                    .unwrap(),
363                &Integer::from(9)
364            )
365        );
366    }
367}
algebraeon_rings/structure/quotient.rs

algebraeon_rings/structure/
quotient.rs
