feanor_math/rings/zn/
zn_big.rs

1use std::cell::OnceCell;
2use std::fmt::Debug;
3use std::marker::PhantomData;
4
5use feanor_serde::dependent_tuple::DeserializeSeedDependentTuple;
6use feanor_serde::newtype_struct::*;
7use serde::de::{DeserializeSeed, Error};
8use serde::{Deserialize, Deserializer, Serialize, Serializer};
9
10use crate::delegate::DelegateRing;
11use crate::divisibility::DivisibilityRing;
12use crate::homomorphism::*;
13use crate::integer::*;
14use crate::ordered::OrderedRingStore;
15use crate::pid::*;
16use crate::reduce_lift::poly_eval::InterpolationBaseRing;
17use crate::ring::*;
18use crate::rings::extension::FreeAlgebraStore;
19use crate::rings::extension::galois_field::*;
20use crate::rings::zn::*;
21use crate::seq::*;
22use crate::serialization::*;
23use crate::specialization::*;
24use crate::{
25    impl_field_wrap_unwrap_homs, impl_field_wrap_unwrap_isos, impl_localpir_wrap_unwrap_homs,
26    impl_localpir_wrap_unwrap_isos,
27};
28
29/// Ring representing `Z/nZ`, computing the modular reductions
30/// via a Barett-reduction algorithm. This is a general-purpose
31/// method, but note that it is required that `n^3` fits into the
32/// supplied integer type.]
33///
34/// # Performance
35///
36/// This implementation is optimized for use with large integer
37/// rings. If the moduli are small, consider using specialized implementations
38/// (like [`crate::rings::zn::zn_64::Zn`]), which will be much faster.
39///
40/// # Example
41/// ```rust
42/// # use feanor_math::ring::*;
43/// # use feanor_math::homomorphism::*;
44/// # use feanor_math::rings::zn::*;
45/// # use feanor_math::rings::zn::zn_big::*;
46/// # use feanor_math::primitive_int::*;
47/// let R = Zn::new(StaticRing::<i64>::RING, 257);
48/// let a = R.int_hom().map(16);
49/// assert!(R.eq_el(&R.int_hom().map(-1), &R.mul_ref(&a, &a)));
50/// assert!(R.is_one(&R.pow(a, 4)));
51/// ```
52/// However, this will panic as `2053^3 > i32::MAX`.
53/// ```rust,should_panic
54/// # use feanor_math::ring::*;
55/// # use feanor_math::rings::zn::*;
56/// # use feanor_math::rings::zn::zn_big::*;
57/// # use feanor_math::primitive_int::*;
58/// let R = Zn::new(StaticRing::<i32>::RING, 2053);
59/// ```
60///
61/// # Canonical mappings
62/// This ring has a canonical homomorphism from any integer ring
63/// ```rust
64/// # use feanor_math::ring::*;
65/// # use feanor_math::homomorphism::*;
66/// # use feanor_math::rings::zn::*;
67/// # use feanor_math::rings::zn::zn_big::*;
68/// # use feanor_math::integer::*;
69/// # use feanor_math::primitive_int::*;
70/// let R = Zn::new(StaticRing::<i16>::RING, 7);
71/// let S = BigIntRing::RING;
72/// assert!(R.eq_el(
73///     &R.int_hom().map(120493),
74///     &R.coerce(&S, S.int_hom().map(120493))
75/// ));
76/// ```
77pub struct ZnBase<I: RingStore>
78where
79    I::Type: IntegerRing,
80{
81    integer_ring: I,
82    modulus: El<I>,
83    twice_modulus: El<I>,
84    inverse_modulus: El<I>,
85    inverse_modulus_bitshift: usize,
86}
87
88/// Ring representing `Z/nZ`, computing the modular reductions
89/// via a Barett-reduction algorithm. For details, see [`ZnBase`].
90pub type Zn<I> = RingValue<ZnBase<I>>;
91
92impl<I: RingStore> Zn<I>
93where
94    I::Type: IntegerRing,
95{
96    pub fn new(integer_ring: I, modulus: El<I>) -> Self { RingValue::from(ZnBase::new(integer_ring, modulus)) }
97}
98
99impl<I: RingStore> ZnBase<I>
100where
101    I::Type: IntegerRing,
102{
103    pub fn new(integer_ring: I, modulus: El<I>) -> Self {
104        assert!(integer_ring.is_geq(&modulus, &integer_ring.int_hom().map(2)));
105
106        // have k such that `2^k >= (2 * modulus)^2`
107        // then `floor(2^k / modulus) * x >> k` differs at most 1 from `floor(x / modulus)`
108        // if `x <= 2^k`, which is the case after multiplication
109        let k = integer_ring
110            .abs_log2_ceil(&integer_ring.mul_ref(&modulus, &modulus))
111            .unwrap()
112            + 2;
113        let mod_square_bound = integer_ring.power_of_two(k);
114        let inverse_modulus = integer_ring.euclidean_div(mod_square_bound, &modulus);
115
116        // check that this expression does not overflow
117        _ = integer_ring.mul_ref_snd(integer_ring.pow(integer_ring.clone_el(&modulus), 2), &inverse_modulus);
118
119        return ZnBase {
120            twice_modulus: integer_ring.add_ref(&modulus, &modulus),
121            integer_ring,
122            modulus,
123            inverse_modulus,
124            inverse_modulus_bitshift: k,
125        };
126    }
127
128    fn bounded_reduce(&self, n: &mut El<I>) {
129        debug_assert!(
130            self.integer_ring
131                .is_leq(n, &self.integer_ring.mul_ref(&self.twice_modulus, &self.twice_modulus))
132        );
133        debug_assert!(!self.integer_ring.is_neg(n));
134
135        let mut subtract = self.integer_ring.mul_ref(n, &self.inverse_modulus);
136        self.integer_ring
137            .euclidean_div_pow_2(&mut subtract, self.inverse_modulus_bitshift);
138        self.integer_ring.mul_assign_ref(&mut subtract, &self.modulus);
139        self.integer_ring.sub_assign(n, subtract);
140
141        debug_assert!(self.integer_ring.is_lt(n, &self.twice_modulus));
142    }
143}
144
145pub struct ZnEl<I: RingStore>(
146    // allow it to grow up to 2 * modulus(), inclusively
147    El<I>,
148)
149where
150    I::Type: IntegerRing;
151
152impl<I> Debug for ZnBase<I>
153where
154    I: RingStore,
155    I::Type: IntegerRing,
156{
157    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
158        write!(f, "Z/{}Z", self.integer_ring().format(self.modulus()))
159    }
160}
161
162impl<I: RingStore> Debug for ZnEl<I>
163where
164    El<I>: Clone + Debug,
165    I::Type: IntegerRing,
166{
167    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.debug_tuple("ZnEl").field(&self.0).finish() }
168}
169
170impl<I: RingStore> Clone for ZnEl<I>
171where
172    El<I>: Clone,
173    I::Type: IntegerRing,
174{
175    fn clone(&self) -> Self { ZnEl(self.0.clone()) }
176}
177
178impl<I: RingStore> Copy for ZnEl<I>
179where
180    El<I>: Copy,
181    I::Type: IntegerRing,
182{
183}
184
185impl<I: RingStore> RingBase for ZnBase<I>
186where
187    I::Type: IntegerRing,
188{
189    type Element = ZnEl<I>;
190
191    fn clone_el(&self, val: &Self::Element) -> Self::Element { ZnEl(self.integer_ring().clone_el(&val.0)) }
192
193    fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
194        debug_assert!(self.integer_ring.is_leq(&lhs.0, &self.twice_modulus));
195        debug_assert!(self.integer_ring.is_leq(&rhs.0, &self.twice_modulus));
196
197        self.integer_ring.add_assign_ref(&mut lhs.0, &rhs.0);
198        if self.integer_ring.is_geq(&lhs.0, &self.twice_modulus) {
199            self.integer_ring.sub_assign_ref(&mut lhs.0, &self.twice_modulus);
200        }
201
202        debug_assert!(self.integer_ring.is_leq(&lhs.0, &self.twice_modulus));
203    }
204
205    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
206        debug_assert!(self.integer_ring.is_leq(&lhs.0, &self.twice_modulus));
207        debug_assert!(self.integer_ring.is_leq(&rhs.0, &self.twice_modulus));
208
209        self.integer_ring.add_assign(&mut lhs.0, rhs.0);
210        if self.integer_ring.is_geq(&lhs.0, &self.twice_modulus) {
211            self.integer_ring.sub_assign_ref(&mut lhs.0, &self.twice_modulus);
212        }
213
214        debug_assert!(self.integer_ring.is_leq(&lhs.0, &self.twice_modulus));
215    }
216
217    fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
218        debug_assert!(self.integer_ring.is_leq(&lhs.0, &self.twice_modulus));
219        debug_assert!(self.integer_ring.is_leq(&rhs.0, &self.twice_modulus));
220
221        self.integer_ring.sub_assign_ref(&mut lhs.0, &rhs.0);
222        if self.integer_ring.is_neg(&lhs.0) {
223            self.integer_ring.add_assign_ref(&mut lhs.0, &self.twice_modulus);
224        }
225
226        debug_assert!(self.integer_ring.is_leq(&lhs.0, &self.twice_modulus));
227        debug_assert!(!self.integer_ring.is_neg(&lhs.0));
228    }
229
230    fn negate_inplace(&self, lhs: &mut Self::Element) {
231        debug_assert!(self.integer_ring.is_leq(&lhs.0, &self.twice_modulus));
232
233        self.integer_ring.negate_inplace(&mut lhs.0);
234        self.integer_ring.add_assign_ref(&mut lhs.0, &self.twice_modulus);
235
236        debug_assert!(self.integer_ring.is_leq(&lhs.0, &self.twice_modulus));
237        debug_assert!(!self.integer_ring.is_neg(&lhs.0));
238    }
239
240    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
241        debug_assert!(self.integer_ring.is_leq(&lhs.0, &self.twice_modulus));
242        debug_assert!(self.integer_ring.is_leq(&rhs.0, &self.twice_modulus));
243
244        self.integer_ring.mul_assign(&mut lhs.0, rhs.0);
245        self.bounded_reduce(&mut lhs.0);
246    }
247
248    fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
249        debug_assert!(self.integer_ring.is_leq(&lhs.0, &self.twice_modulus));
250        debug_assert!(self.integer_ring.is_leq(&rhs.0, &self.twice_modulus));
251
252        self.integer_ring.mul_assign_ref(&mut lhs.0, &rhs.0);
253        self.bounded_reduce(&mut lhs.0);
254    }
255
256    fn from_int(&self, value: i32) -> Self::Element { RingRef::new(self).coerce(&StaticRing::<i32>::RING, value) }
257
258    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
259        debug_assert!(self.integer_ring.is_leq(&lhs.0, &self.twice_modulus));
260        debug_assert!(self.integer_ring.is_leq(&rhs.0, &self.twice_modulus));
261
262        if self.integer_ring.eq_el(&lhs.0, &rhs.0) {
263            return true;
264        }
265        let difference = self.integer_ring.abs(self.integer_ring.sub_ref(&lhs.0, &rhs.0));
266        return self.integer_ring.eq_el(&difference, &self.modulus)
267            || self.integer_ring.eq_el(&difference, &self.twice_modulus);
268    }
269
270    fn is_zero(&self, value: &Self::Element) -> bool {
271        debug_assert!(self.integer_ring.is_leq(&value.0, &self.twice_modulus));
272
273        self.integer_ring.is_zero(&value.0)
274            || self.integer_ring.eq_el(&value.0, &self.modulus)
275            || self.integer_ring.eq_el(&value.0, &self.twice_modulus)
276    }
277
278    fn is_one(&self, value: &Self::Element) -> bool {
279        debug_assert!(self.integer_ring.is_leq(&value.0, &self.twice_modulus));
280
281        self.integer_ring.is_one(&value.0)
282            || self.integer_ring.eq_el(
283                &value.0,
284                &self.integer_ring.add_ref_fst(&self.modulus, self.integer_ring.one()),
285            )
286    }
287
288    fn is_commutative(&self) -> bool { true }
289    fn is_noetherian(&self) -> bool { true }
290
291    fn dbg_within<'a>(
292        &self,
293        value: &Self::Element,
294        out: &mut std::fmt::Formatter<'a>,
295        _: EnvBindingStrength,
296    ) -> std::fmt::Result {
297        if self.integer_ring.is_geq(&value.0, &self.modulus) {
298            let reduced_value = self.integer_ring.sub_ref(&value.0, &self.modulus);
299            if self.integer_ring.eq_el(&reduced_value, &self.modulus) {
300                self.integer_ring.get_ring().dbg(&self.integer_ring.zero(), out)
301            } else {
302                self.integer_ring.get_ring().dbg(&reduced_value, out)
303            }
304        } else {
305            self.integer_ring.get_ring().dbg(&value.0, out)
306        }
307    }
308
309    fn characteristic<J: RingStore + Copy>(&self, ZZ: J) -> Option<El<J>>
310    where
311        J::Type: IntegerRing,
312    {
313        self.size(ZZ)
314    }
315
316    fn is_approximate(&self) -> bool { false }
317}
318
319impl<I: RingStore> Clone for ZnBase<I>
320where
321    I: Clone,
322    I::Type: IntegerRing,
323{
324    fn clone(&self) -> Self {
325        ZnBase {
326            integer_ring: self.integer_ring.clone(),
327            modulus: self.integer_ring.clone_el(&self.modulus),
328            inverse_modulus: self.integer_ring.clone_el(&self.inverse_modulus),
329            inverse_modulus_bitshift: self.inverse_modulus_bitshift,
330            twice_modulus: self.integer_ring.clone_el(&self.twice_modulus),
331        }
332    }
333}
334
335impl<I: RingStore> InterpolationBaseRing for AsFieldBase<Zn<I>>
336where
337    I::Type: IntegerRing,
338{
339    type ExtendedRingBase<'a>
340        = GaloisFieldBaseOver<RingRef<'a, Self>>
341    where
342        Self: 'a;
343
344    type ExtendedRing<'a>
345        = GaloisFieldOver<RingRef<'a, Self>>
346    where
347        Self: 'a;
348
349    fn in_base<'a, S>(&self, ext_ring: S, el: El<S>) -> Option<Self::Element>
350    where
351        Self: 'a,
352        S: RingStore<Type = Self::ExtendedRingBase<'a>>,
353    {
354        let wrt_basis = ext_ring.wrt_canonical_basis(&el);
355        if wrt_basis.iter().skip(1).all(|x| self.is_zero(&x)) {
356            return Some(wrt_basis.at(0));
357        } else {
358            return None;
359        }
360    }
361
362    fn in_extension<'a, S>(&self, ext_ring: S, el: Self::Element) -> El<S>
363    where
364        Self: 'a,
365        S: RingStore<Type = Self::ExtendedRingBase<'a>>,
366    {
367        ext_ring.inclusion().map(el)
368    }
369
370    fn interpolation_points<'a>(&'a self, count: usize) -> (Self::ExtendedRing<'a>, Vec<El<Self::ExtendedRing<'a>>>) {
371        let ring = super::generic_impls::interpolation_ring(RingRef::new(self), count);
372        let points = ring.elements().take(count).collect();
373        return (ring, points);
374    }
375}
376impl<I: RingStore> Copy for ZnBase<I>
377where
378    I: Copy,
379    El<I>: Copy,
380    I::Type: IntegerRing,
381{
382}
383
384impl<I: RingStore> HashableElRing for ZnBase<I>
385where
386    I::Type: IntegerRing,
387{
388    fn hash<H: std::hash::Hasher>(&self, el: &Self::Element, h: &mut H) {
389        self.integer_ring()
390            .hash(&self.smallest_positive_lift(self.clone_el(el)), h)
391    }
392}
393
394impl<I: RingStore + Default> FromModulusCreateableZnRing for ZnBase<I>
395where
396    I::Type: IntegerRing,
397{
398    fn from_modulus<F, E>(create_modulus: F) -> Result<Self, E>
399    where
400        F: FnOnce(&Self::IntegerRingBase) -> Result<El<Self::IntegerRing>, E>,
401    {
402        let ZZ = I::default();
403        let modulus = create_modulus(ZZ.get_ring())?;
404        Ok(Self::new(ZZ, modulus))
405    }
406}
407
408impl<I: RingStore> DivisibilityRing for ZnBase<I>
409where
410    I::Type: IntegerRing,
411{
412    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
413        super::generic_impls::checked_left_div(RingRef::new(self), lhs, rhs)
414    }
415}
416
417impl<I: RingStore, J: RingStore> CanHomFrom<ZnBase<J>> for ZnBase<I>
418where
419    I::Type: IntegerRing + CanHomFrom<J::Type>,
420    J::Type: IntegerRing,
421{
422    type Homomorphism = <I::Type as CanHomFrom<J::Type>>::Homomorphism;
423
424    fn has_canonical_hom(&self, from: &ZnBase<J>) -> Option<Self::Homomorphism> {
425        let base_hom = <I::Type as CanHomFrom<J::Type>>::has_canonical_hom(
426            self.integer_ring.get_ring(),
427            from.integer_ring.get_ring(),
428        )?;
429        if self.integer_ring.eq_el(
430            &self.modulus,
431            &<I::Type as CanHomFrom<J::Type>>::map_in(
432                self.integer_ring.get_ring(),
433                from.integer_ring.get_ring(),
434                from.integer_ring().clone_el(&from.modulus),
435                &base_hom,
436            ),
437        ) {
438            Some(base_hom)
439        } else {
440            None
441        }
442    }
443
444    fn map_in(
445        &self,
446        from: &ZnBase<J>,
447        el: <ZnBase<J> as RingBase>::Element,
448        hom: &Self::Homomorphism,
449    ) -> Self::Element {
450        ZnEl(<I::Type as CanHomFrom<J::Type>>::map_in(
451            self.integer_ring.get_ring(),
452            from.integer_ring.get_ring(),
453            el.0,
454            hom,
455        ))
456    }
457}
458
459impl<I: RingStore> CanHomFrom<zn_64::ZnBase> for ZnBase<I>
460where
461    I::Type: IntegerRing,
462{
463    type Homomorphism = <zn_64::ZnBase as CanIsoFromTo<ZnBase<I>>>::Isomorphism;
464
465    fn has_canonical_hom(&self, from: &zn_64::ZnBase) -> Option<Self::Homomorphism> { from.has_canonical_iso(self) }
466
467    fn map_in(
468        &self,
469        from: &zn_64::ZnBase,
470        el: <zn_64::ZnBase as RingBase>::Element,
471        hom: &Self::Homomorphism,
472    ) -> Self::Element {
473        from.map_out(self, el, hom)
474    }
475}
476
477impl<I: RingStore> CanIsoFromTo<zn_64::ZnBase> for ZnBase<I>
478where
479    I::Type: IntegerRing,
480{
481    type Isomorphism = <zn_64::ZnBase as CanHomFrom<ZnBase<I>>>::Homomorphism;
482
483    fn has_canonical_iso(&self, from: &zn_64::ZnBase) -> Option<Self::Isomorphism> { from.has_canonical_hom(self) }
484
485    fn map_out(
486        &self,
487        from: &zn_64::ZnBase,
488        el: Self::Element,
489        iso: &Self::Isomorphism,
490    ) -> <zn_64::ZnBase as RingBase>::Element {
491        from.map_in(self, el, iso)
492    }
493}
494
495impl<I: RingStore> PartialEq for ZnBase<I>
496where
497    I::Type: IntegerRing,
498{
499    fn eq(&self, other: &Self) -> bool {
500        self.integer_ring.get_ring() == other.integer_ring.get_ring()
501            && self.integer_ring.eq_el(&self.modulus, &other.modulus)
502    }
503}
504
505impl<I: RingStore, J: RingStore> CanIsoFromTo<ZnBase<J>> for ZnBase<I>
506where
507    I::Type: IntegerRing + CanIsoFromTo<J::Type>,
508    J::Type: IntegerRing,
509{
510    type Isomorphism = <I::Type as CanIsoFromTo<J::Type>>::Isomorphism;
511
512    fn has_canonical_iso(&self, from: &ZnBase<J>) -> Option<Self::Isomorphism> {
513        let base_iso = <I::Type as CanIsoFromTo<J::Type>>::has_canonical_iso(
514            self.integer_ring.get_ring(),
515            from.integer_ring.get_ring(),
516        )?;
517        if from.integer_ring().eq_el(
518            from.modulus(),
519            &<I::Type as CanIsoFromTo<J::Type>>::map_out(
520                self.integer_ring.get_ring(),
521                from.integer_ring.get_ring(),
522                self.integer_ring().clone_el(self.modulus()),
523                &base_iso,
524            ),
525        ) {
526            Some(base_iso)
527        } else {
528            None
529        }
530    }
531
532    fn map_out(
533        &self,
534        from: &ZnBase<J>,
535        el: Self::Element,
536        iso: &Self::Isomorphism,
537    ) -> <ZnBase<J> as RingBase>::Element {
538        ZnEl(<I::Type as CanIsoFromTo<J::Type>>::map_out(
539            self.integer_ring.get_ring(),
540            from.integer_ring.get_ring(),
541            el.0,
542            iso,
543        ))
544    }
545}
546
547impl<I: RingStore, J: IntegerRing + ?Sized> CanHomFrom<J> for ZnBase<I>
548where
549    I::Type: IntegerRing,
550    J: CanIsoFromTo<I::Type>,
551{
552    type Homomorphism = super::generic_impls::BigIntToZnHom<J, I::Type, ZnBase<I>>;
553
554    fn has_canonical_hom(&self, from: &J) -> Option<Self::Homomorphism> {
555        super::generic_impls::has_canonical_hom_from_bigint(
556            from,
557            self,
558            self.integer_ring.get_ring(),
559            Some(&self.integer_ring.mul_ref(&self.twice_modulus, &self.twice_modulus)),
560        )
561    }
562
563    fn map_in(&self, from: &J, el: J::Element, hom: &Self::Homomorphism) -> Self::Element {
564        super::generic_impls::map_in_from_bigint(
565            from,
566            self,
567            self.integer_ring.get_ring(),
568            el,
569            hom,
570            |n| {
571                debug_assert!(self.integer_ring.is_lt(&n, &self.modulus));
572                ZnEl(n)
573            },
574            |mut n| {
575                debug_assert!(
576                    self.integer_ring
577                        .is_lt(&n, &self.integer_ring.mul_ref(&self.twice_modulus, &self.twice_modulus))
578                );
579                self.bounded_reduce(&mut n);
580                ZnEl(n)
581            },
582        )
583    }
584}
585
586pub struct ZnBaseElementsIter<'a, I>
587where
588    I: RingStore,
589    I::Type: IntegerRing,
590{
591    ring: &'a ZnBase<I>,
592    current: El<I>,
593}
594
595impl<'a, I> Clone for ZnBaseElementsIter<'a, I>
596where
597    I: RingStore,
598    I::Type: IntegerRing,
599{
600    fn clone(&self) -> Self {
601        Self {
602            ring: self.ring,
603            current: self.ring.integer_ring().clone_el(&self.current),
604        }
605    }
606}
607
608impl<'a, I> Iterator for ZnBaseElementsIter<'a, I>
609where
610    I: RingStore,
611    I::Type: IntegerRing,
612{
613    type Item = ZnEl<I>;
614
615    fn next(&mut self) -> Option<Self::Item> {
616        if self.ring.integer_ring().is_lt(&self.current, self.ring.modulus()) {
617            let result = self.ring.integer_ring().clone_el(&self.current);
618            self.ring
619                .integer_ring()
620                .add_assign(&mut self.current, self.ring.integer_ring().one());
621            return Some(ZnEl(result));
622        } else {
623            return None;
624        }
625    }
626}
627
628impl<I> Serialize for ZnBase<I>
629where
630    I: RingStore + Serialize,
631    I::Type: IntegerRing + SerializableElementRing,
632{
633    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
634    where
635        S: Serializer,
636    {
637        SerializableNewtypeStruct::new(
638            "Zn",
639            (
640                self.integer_ring(),
641                SerializeWithRing::new(self.modulus(), self.integer_ring()),
642            ),
643        )
644        .serialize(serializer)
645    }
646}
647
648impl<'de, I> Deserialize<'de> for ZnBase<I>
649where
650    I: RingStore + Deserialize<'de>,
651    I::Type: IntegerRing + SerializableElementRing,
652{
653    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
654    where
655        D: Deserializer<'de>,
656    {
657        let ring_cell = OnceCell::new();
658        let modulus = <_ as DeserializeSeed<'de>>::deserialize(
659            DeserializeSeedNewtypeStruct::new(
660                "Zn",
661                DeserializeSeedDependentTuple::new(PhantomData::<I>, |ring| {
662                    ring_cell.set(ring).ok().unwrap();
663                    DeserializeWithRing::new(ring_cell.get().unwrap())
664                }),
665            ),
666            deserializer,
667        )?;
668        let ring = ring_cell.into_inner().unwrap();
669        return Ok(Zn::new(ring, modulus).into());
670    }
671}
672
673impl<I: RingStore> SerializableElementRing for ZnBase<I>
674where
675    I::Type: IntegerRing + SerializableElementRing,
676{
677    fn deserialize<'de, D>(&self, deserializer: D) -> Result<Self::Element, D::Error>
678    where
679        D: Deserializer<'de>,
680    {
681        self.integer_ring()
682            .get_ring()
683            .deserialize(deserializer)
684            .and_then(|x| {
685                if self.integer_ring().is_neg(&x) || self.integer_ring().is_geq(&x, self.modulus()) {
686                    Err(Error::custom("ring element value out of bounds for ring Z/nZ"))
687                } else {
688                    Ok(x)
689                }
690            })
691            .map(|x| self.from_int_promise_reduced(x))
692    }
693
694    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
695    where
696        S: Serializer,
697    {
698        self.integer_ring()
699            .get_ring()
700            .serialize(&self.smallest_positive_lift(self.clone_el(el)), serializer)
701    }
702}
703
704impl<I: RingStore> FiniteRing for ZnBase<I>
705where
706    I::Type: IntegerRing,
707{
708    type ElementsIter<'a>
709        = ZnBaseElementsIter<'a, I>
710    where
711        Self: 'a;
712
713    fn elements<'a>(&'a self) -> ZnBaseElementsIter<'a, I> {
714        ZnBaseElementsIter {
715            ring: self,
716            current: self.integer_ring().zero(),
717        }
718    }
719
720    fn random_element<G: FnMut() -> u64>(&self, rng: G) -> <Self as RingBase>::Element {
721        super::generic_impls::random_element(self, rng)
722    }
723
724    fn size<J: RingStore + Copy>(&self, ZZ: J) -> Option<El<J>>
725    where
726        J::Type: IntegerRing,
727    {
728        if ZZ.get_ring().representable_bits().is_none()
729            || self.integer_ring().abs_log2_ceil(self.modulus()) < ZZ.get_ring().representable_bits()
730        {
731            Some(int_cast(
732                self.integer_ring().clone_el(self.modulus()),
733                ZZ,
734                self.integer_ring(),
735            ))
736        } else {
737            None
738        }
739    }
740}
741
742impl<I: RingStore> PrincipalIdealRing for ZnBase<I>
743where
744    I::Type: IntegerRing,
745{
746    fn checked_div_min(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
747        super::generic_impls::checked_div_min(RingRef::new(self), lhs, rhs)
748    }
749
750    fn extended_ideal_gen(
751        &self,
752        lhs: &Self::Element,
753        rhs: &Self::Element,
754    ) -> (Self::Element, Self::Element, Self::Element) {
755        let (s, t, d) = self.integer_ring().extended_ideal_gen(&lhs.0, &rhs.0);
756        let quo = RingRef::new(self).into_can_hom(self.integer_ring()).ok().unwrap();
757        (quo.map(s), quo.map(t), quo.map(d))
758    }
759}
760
761impl<I> FiniteRingSpecializable for ZnBase<I>
762where
763    I: RingStore,
764    I::Type: IntegerRing,
765{
766    fn specialize<O: FiniteRingOperation<Self>>(op: O) -> O::Output { op.execute() }
767}
768
769impl<I: RingStore> ZnRing for ZnBase<I>
770where
771    I::Type: IntegerRing,
772{
773    type IntegerRingBase = I::Type;
774    type IntegerRing = I;
775
776    fn integer_ring(&self) -> &Self::IntegerRing { &self.integer_ring }
777
778    fn modulus(&self) -> &El<Self::IntegerRing> { &self.modulus }
779
780    fn smallest_positive_lift(&self, mut el: Self::Element) -> El<Self::IntegerRing> {
781        if self.integer_ring.eq_el(&el.0, &self.twice_modulus) {
782            return self.integer_ring.zero();
783        }
784        if self.integer_ring.is_geq(&el.0, &self.modulus) {
785            self.integer_ring.sub_assign_ref(&mut el.0, &self.modulus);
786        }
787        debug_assert!(self.integer_ring.is_lt(&el.0, &self.modulus));
788        return el.0;
789    }
790
791    fn from_int_promise_reduced(&self, x: El<Self::IntegerRing>) -> Self::Element {
792        debug_assert!(!self.integer_ring().is_neg(&x));
793        debug_assert!(self.integer_ring().is_lt(&x, self.modulus()));
794        ZnEl(x)
795    }
796}
797
798impl_field_wrap_unwrap_homs! { <{I, J}> ZnBase<I>, ZnBase<J> where I: RingStore, I::Type: IntegerRing, J: RingStore, J::Type: IntegerRing }
799impl_field_wrap_unwrap_isos! { <{I, J}> ZnBase<I>, ZnBase<J> where I: RingStore, I::Type: IntegerRing, J: RingStore, J::Type: IntegerRing }
800impl_localpir_wrap_unwrap_homs! { <{I, J}> ZnBase<I>, ZnBase<J> where I: RingStore, I::Type: IntegerRing, J: RingStore, J::Type: IntegerRing }
801impl_localpir_wrap_unwrap_isos! { <{I, J}> ZnBase<I>, ZnBase<J> where I: RingStore, I::Type: IntegerRing, J: RingStore, J::Type: IntegerRing }
802
803#[cfg(test)]
804use crate::integer::BigIntRing;
805#[cfg(test)]
806use crate::rings::rust_bigint::*;
807
808#[test]
809fn test_mul() {
810    const ZZ: BigIntRing = BigIntRing::RING;
811    let Z257 = Zn::new(ZZ, ZZ.int_hom().map(257));
812    let x = Z257.coerce(&ZZ, ZZ.int_hom().map(256));
813    assert_el_eq!(Z257, Z257.one(), Z257.mul_ref(&x, &x));
814}
815
816#[test]
817fn test_project() {
818    const ZZ: StaticRing<i64> = StaticRing::RING;
819    let Z17 = Zn::new(ZZ, 17);
820    for k in 0..289 {
821        assert_el_eq!(Z17, Z17.int_hom().map((289 - k) % 17), Z17.coerce(&ZZ, -k as i64));
822    }
823}
824
825#[test]
826fn test_ring_axioms_znbase() {
827    let ring = Zn::new(StaticRing::<i64>::RING, 63);
828    crate::ring::generic_tests::test_ring_axioms(&ring, ring.elements())
829}
830
831#[test]
832fn test_hash_axioms() {
833    let ring = Zn::new(StaticRing::<i64>::RING, 63);
834    crate::ring::generic_tests::test_hash_axioms(&ring, ring.elements())
835}
836
837#[test]
838fn test_canonical_iso_axioms_zn_big() {
839    let from = Zn::new(StaticRing::<i128>::RING, 7 * 11);
840    let to = Zn::new(BigIntRing::RING, BigIntRing::RING.int_hom().map(7 * 11));
841    crate::ring::generic_tests::test_hom_axioms(&from, &to, from.elements());
842    crate::ring::generic_tests::test_iso_axioms(&from, &to, from.elements());
843    assert!(from.can_hom(&Zn::new(StaticRing::<i64>::RING, 19)).is_none());
844}
845
846#[test]
847fn test_canonical_hom_axioms_static_int() {
848    let from = StaticRing::<i32>::RING;
849    let to = Zn::new(StaticRing::<i128>::RING, 7 * 11);
850    crate::ring::generic_tests::test_hom_axioms(&from, to, 0..=(2 * 7 * 11));
851}
852
853#[test]
854fn test_zn_ring_axioms_znbase() {
855    super::generic_tests::test_zn_axioms(Zn::new(StaticRing::<i64>::RING, 17));
856    super::generic_tests::test_zn_axioms(Zn::new(StaticRing::<i64>::RING, 63));
857}
858
859#[test]
860fn test_zn_map_in_large_int_znbase() {
861    super::generic_tests::test_map_in_large_int(Zn::new(StaticRing::<i64>::RING, 63));
862}
863
864#[test]
865fn test_zn_map_in_small_int() {
866    let ring = Zn::new(StaticRing::<i64>::RING, 257);
867    assert_el_eq!(ring, ring.one(), ring.coerce(&StaticRing::<i8>::RING, 1));
868}
869
870#[test]
871fn test_divisibility_axioms() {
872    let R = Zn::new(StaticRing::<i64>::RING, 17);
873    crate::divisibility::generic_tests::test_divisibility_axioms(&R, R.elements());
874}
875
876#[test]
877fn test_principal_ideal_ring_axioms() {
878    let R = Zn::new(StaticRing::<i64>::RING, 17);
879    crate::pid::generic_tests::test_principal_ideal_ring_axioms(&R, R.elements());
880    let R = Zn::new(StaticRing::<i64>::RING, 63);
881    crate::pid::generic_tests::test_principal_ideal_ring_axioms(&R, R.elements());
882}
883
884#[test]
885fn test_canonical_iso_axioms_as_field() {
886    let R = Zn::new(StaticRing::<i128>::RING, 17);
887    let R2 = R.clone().as_field().ok().unwrap();
888    crate::ring::generic_tests::test_hom_axioms(&R, &R2, R.elements());
889    crate::ring::generic_tests::test_iso_axioms(&R, &R2, R.elements());
890    crate::ring::generic_tests::test_hom_axioms(&R2, &R, R2.elements());
891    crate::ring::generic_tests::test_iso_axioms(&R2, &R, R2.elements());
892}
893
894#[test]
895fn test_canonical_iso_axioms_zn_64() {
896    let R = Zn::new(StaticRing::<i128>::RING, 17);
897    let R2 = zn_64::Zn::new(17);
898    crate::ring::generic_tests::test_hom_axioms(&R, &R2, R.elements());
899    crate::ring::generic_tests::test_iso_axioms(&R, &R2, R.elements());
900    crate::ring::generic_tests::test_hom_axioms(&R2, &R, R2.elements());
901    crate::ring::generic_tests::test_iso_axioms(&R2, &R, R2.elements());
902}
903
904#[test]
905fn test_finite_field_axioms() {
906    crate::rings::finite::generic_tests::test_finite_ring_axioms(&Zn::new(&StaticRing::<i64>::RING, 128));
907    crate::rings::finite::generic_tests::test_finite_ring_axioms(&Zn::new(&StaticRing::<i64>::RING, 15));
908    crate::rings::finite::generic_tests::test_finite_ring_axioms(&Zn::new(&StaticRing::<i128>::RING, 1 << 32));
909}
910
911#[test]
912fn test_serialize() {
913    let ring = Zn::new(&StaticRing::<i64>::RING, 128);
914    crate::serialization::generic_tests::test_serialization(ring, ring.elements())
915}
916#[test]
917fn test_unreduced() {
918    let ZZbig = RustBigintRing::RING;
919    let ring = Zn::new(
920        ZZbig,
921        ZZbig.prod(
922            [
923                72057594035352641,
924                72057594035418113,
925                72057594036334721,
926                72057594036945793,
927            ]
928            .iter()
929            .map(|p| int_cast(*p, ZZbig, StaticRing::<i64>::RING)),
930        ),
931    );
932    let value = ZZbig
933        .get_ring()
934        .parse(
935            "26959946664284515451292772736873168147996033528710027874998326058050",
936            10,
937        )
938        .unwrap();
939
940    let x: ZnEl<RustBigintRing> = ZnEl(value);
941    // this means this is a valid representative, although it is > ring.modulus()
942    assert!(ZZbig.is_lt(&x.0, &ring.get_ring().twice_modulus));
943
944    assert!(ring.is_one(&x));
945    assert!(ring.is_one(&ring.mul_ref(&x, &x)));
946    assert!(ring.eq_el(&x, &ring.mul_ref(&x, &x)));
947    assert_eq!("1", format!("{}", ring.format(&x)));
948}
949
950#[test]
951fn test_serialize_deserialize() {
952    crate::serialization::generic_tests::test_serialize_deserialize(Zn::new(StaticRing::<i64>::RING, 128).into());
953    crate::serialization::generic_tests::test_serialize_deserialize(Zn::new(StaticRing::<i64>::RING, 129).into());
954    crate::serialization::generic_tests::test_serialize_deserialize(
955        Zn::new(BigIntRing::RING, BigIntRing::RING.power_of_two(10)).into(),
956    );
957}
feanor_math/rings/zn/zn_big.rs

feanor_math/rings/zn/
zn_big.rs
