feanor_math/rings/zn/
zn_big.rs

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

feanor_math/rings/zn/
zn_big.rs
