feanor_math/rings/zn/
zn_big.rs

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

feanor_math/rings/zn/
zn_big.rs
