feanor_math/rings/zn/
mod.rs

1use crate::divisibility::DivisibilityRingStore;
2use crate::pid::EuclideanRingStore;
3use crate::pid::PrincipalIdealRing;
4use crate::primitive_int::StaticRing;
5use crate::ring::*;
6use crate::divisibility::DivisibilityRing;
7use crate::algorithms;
8use crate::integer::*;
9use crate::homomorphism::*;
10use crate::ordered::*;
11use super::field::AsFieldBase;
12use super::finite::FiniteRing;
13use crate::rings::finite::FiniteRingStore;
14use crate::pid::*;
15
16///
17/// This module contains [`zn_big::Zn`], a general-purpose implementation of
18/// Barett reduction. It is relatively slow when instantiated with small fixed-size
19/// integer type. 
20/// 
21pub mod zn_big;
22///
23/// This module contains [`zn_64::Zn`], the new, heavily optimized implementation of `Z/nZ`
24/// for moduli `n` of size slightly smaller than 64 bits.
25/// 
26pub mod zn_64;
27///
28/// This module contains [`zn_static::Zn`], an implementation of `Z/nZ` for a small `n`
29/// that is known at compile-time.
30/// 
31pub mod zn_static;
32///
33/// This module contains [`zn_rns::Zn`], a residue number system (RNS) implementation of
34/// `Z/nZ` for highly composite `n`. 
35/// 
36pub mod zn_rns;
37
38///
39/// Trait for all rings that represent a quotient of the integers `Z/nZ` for some integer `n`.
40/// 
41pub trait ZnRing: PrincipalIdealRing + FiniteRing + CanHomFrom<Self::IntegerRingBase> {
42
43    /// 
44    /// there seems to be a problem with associated type bounds, hence we cannot use `Integers: IntegerRingStore`
45    /// or `Integers: RingStore<Type: IntegerRing>`
46    /// 
47    type IntegerRingBase: IntegerRing + ?Sized;
48    type IntegerRing: RingStore<Type = Self::IntegerRingBase>;
49
50    fn integer_ring(&self) -> &Self::IntegerRing;
51    fn modulus(&self) -> &El<Self::IntegerRing>;
52
53    ///
54    /// Computes the smallest positive lift for some `x` in `Z/nZ`, i.e. the smallest positive integer `m` such that
55    /// `m = x mod n`.
56    /// 
57    /// This will be one of `0, 1, ..., n - 1`. If an integer in `-(n - 1)/2, ..., -1, 0, 1, ..., (n - 1)/2` (for odd `n`)
58    /// is needed instead, use [`ZnRing::smallest_lift()`].
59    /// 
60    fn smallest_positive_lift(&self, el: Self::Element) -> El<Self::IntegerRing>;
61
62    ///
63    /// Computes any lift for some `x` in `Z/nZ`, i.e. the some integer `m` such that `m = x mod n`.
64    /// 
65    /// The only requirement is that `m` is a valid element of the integer ring, in particular that
66    /// it fits within the required amount of bits, if [`ZnRing::IntegerRing`] is a fixed-size integer ring.
67    /// 
68    fn any_lift(&self, el: Self::Element) -> El<Self::IntegerRing> {
69        self.smallest_positive_lift(el)
70    }
71
72    ///
73    /// If the given integer is within `{ 0, ..., n - 1 }`, returns the corresponding
74    /// element in `Z/nZ`. Any other input is considered a logic error.
75    /// 
76    /// Unless the context is absolutely performance-critical, it might be safer to use
77    /// the homomorphism provided by [`CanHomFrom`] which performs proper modular reduction
78    /// of the input.
79    /// 
80    /// This function never causes undefined behavior, but an invalid input leads to
81    /// a logic error. In particular, the result in such a case does not have to be
82    /// congruent to the input mod `n`, nor does it even have to be a valid element
83    /// of the ring (i.e. operations involving it may not follow the ring axioms).
84    /// Implementors are strongly encouraged to check the element during debug builds. 
85    /// 
86    fn from_int_promise_reduced(&self, x: El<Self::IntegerRing>) -> Self::Element;
87
88    ///
89    /// Computes the smallest lift for some `x` in `Z/nZ`, i.e. the smallest integer `m` such that
90    /// `m = x mod n`.
91    /// 
92    /// This will be one of `-(n - 1)/2, ..., -1, 0, 1, ..., (n - 1)/2` (for odd `n`). If an integer 
93    /// in `0, 1, ..., n - 1` is needed instead, use [`ZnRing::smallest_positive_lift()`].
94    /// 
95    fn smallest_lift(&self, el: Self::Element) -> El<Self::IntegerRing> {
96        let result = self.smallest_positive_lift(el);
97        let mut mod_half = self.integer_ring().clone_el(self.modulus());
98        self.integer_ring().euclidean_div_pow_2(&mut mod_half, 1);
99        if self.integer_ring().is_gt(&result, &mod_half) {
100            return self.integer_ring().sub_ref_snd(result, self.modulus());
101        } else {
102            return result;
103        }
104    }
105
106    ///
107    /// Returns whether this ring is a field, i.e. whether `n` is prime.
108    /// 
109    fn is_field(&self) -> bool {
110        algorithms::miller_rabin::is_prime_base(RingRef::new(self), 10)
111    }
112}
113
114///
115/// Trait for implementations of [`ZnRing`] that can be created (possibly with a 
116/// default configuration) from just the integer modulus.
117/// 
118/// I am not yet sure whether to use this trait, or opt for a factory trait (which
119/// would then offer more flexibility).
120/// 
121#[stability::unstable(feature = "enable")]
122pub trait FromModulusCreateableZnRing: Sized + ZnRing {
123
124    fn create<F, E>(create_modulus: F) -> Result<Self, E>
125        where F: FnOnce(&Self::IntegerRingBase) -> Result<El<Self::IntegerRing>, E>;
126}
127
128pub mod generic_impls {
129    use std::alloc::Global;
130    use std::marker::PhantomData;
131
132    use crate::algorithms::convolution::STANDARD_CONVOLUTION;
133    use crate::algorithms::int_bisect;
134    use crate::ordered::*;
135    use crate::primitive_int::{StaticRing, StaticRingBase};
136    use crate::field::*;
137    use crate::rings::zn::*;
138    use crate::divisibility::DivisibilityRingStore;
139    use crate::integer::{IntegerRing, IntegerRingStore};
140    use crate::rings::extension::galois_field::{GaloisField, GaloisFieldOver};
141
142    ///
143    /// A generic `ZZ -> Z/nZ` homomorphism. Optimized for the case that values of `ZZ` can be very
144    /// large, but allow for efficient estimation of their approximate size.
145    /// 
146    pub struct BigIntToZnHom<I: ?Sized + IntegerRing, J: ?Sized + IntegerRing, R: ?Sized + ZnRing>
147        where I: CanIsoFromTo<R::IntegerRingBase> + CanIsoFromTo<J>
148    {
149        highbit_mod: usize,
150        highbit_bound: usize,
151        int_ring: PhantomData<I>,
152        to_large_int_ring: PhantomData<J>,
153        hom: <I as CanHomFrom<R::IntegerRingBase>>::Homomorphism,
154        iso: <I as CanIsoFromTo<R::IntegerRingBase>>::Isomorphism,
155        iso2: <I as CanIsoFromTo<J>>::Isomorphism
156    }
157
158    ///
159    /// See [`map_in_from_bigint()`].
160    /// 
161    /// This will only ever return `None` if one of the integer ring `has_canonical_hom/iso` returns `None`.
162    /// 
163    #[stability::unstable(feature = "enable")]
164    pub fn has_canonical_hom_from_bigint<I: ?Sized + IntegerRing, J: ?Sized + IntegerRing, R: ?Sized + ZnRing>(from: &I, to: &R, to_large_int_ring: &J, bounded_reduce_bound: Option<&J::Element>) -> Option<BigIntToZnHom<I, J, R>>
165        where I: CanIsoFromTo<R::IntegerRingBase> + CanIsoFromTo<J>
166    {
167        if let Some(bound) = bounded_reduce_bound {
168            Some(BigIntToZnHom {
169                highbit_mod: to.integer_ring().abs_highest_set_bit(to.modulus()).unwrap(),
170                highbit_bound: to_large_int_ring.abs_highest_set_bit(bound).unwrap(),
171                int_ring: PhantomData,
172                to_large_int_ring: PhantomData,
173                hom: from.has_canonical_hom(to.integer_ring().get_ring())?,
174                iso: from.has_canonical_iso(to.integer_ring().get_ring())?,
175                iso2: from.has_canonical_iso(to_large_int_ring)?
176            })
177        } else {
178            Some(BigIntToZnHom {
179                highbit_mod: to.integer_ring().abs_highest_set_bit(to.modulus()).unwrap(),
180                highbit_bound: usize::MAX,
181                int_ring: PhantomData,
182                to_large_int_ring: PhantomData,
183                hom: from.has_canonical_hom(to.integer_ring().get_ring())?,
184                iso: from.has_canonical_iso(to.integer_ring().get_ring())?,
185                iso2: from.has_canonical_iso(to_large_int_ring)?
186            })
187        }
188    }
189
190    ///
191    /// A parameterized, generic variant of the reduction `Z -> Z/nZ`.
192    /// It considers the following situations:
193    ///  - the source ring `Z` might not be large enough to represent `n`
194    ///  - the integer ring associated to the destination ring `Z/nZ` might not be large enough to represent the input
195    ///  - the destination ring might use Barett reductions (or similar) for fast modular reduction if the input is bounded by some fixed bound `B`
196    ///  - general modular reduction modulo `n` is only performed in the source ring if necessary
197    /// 
198    /// In particular, we use the following additional parameters:
199    ///  - `to_large_int_ring`: an integer ring that can represent all integers for which we can perform fast modular reduction (i.e. those bounded by `B`)
200    ///  - `from_positive_representative_exact`: a function that performs the restricted reduction `{0, ..., n - 1} -> Z/nZ`
201    ///  - `from_positive_representative_bounded`: a function that performs the restricted reduction `{0, ..., B - 1} -> Z/nZ`
202    /// 
203    /// It first estimates the size of numbers by their bitlength, so don't use this for small integers (i.e. `ixx`-types), as the estimation
204    /// is likely to take longer than the actual modular reduction.
205    /// 
206    /// Note that the input size estimates consider only the bitlength of numbers, and so there is a small margin in which a reduction method for larger
207    /// numbers than necessary is used. Furthermore, if the integer rings used can represent some but not all positive numbers of a certain bitlength, 
208    /// there might be rare edge cases with panics/overflows. 
209    /// 
210    /// In particular, if the input integer ring `Z` can represent the input `x`, but not `n` AND `x` and `n` have the same bitlength, this function might
211    /// decide that we have to perform generic modular reduction (even though `x < n`), and try to map `n` into `Z`. This is never a problem if the primitive
212    /// integer rings `StaticRing::<ixx>::RING` are used, or if `B >= 2n`.
213    /// 
214    #[stability::unstable(feature = "enable")]
215    pub fn map_in_from_bigint<I: ?Sized + IntegerRing, J: ?Sized + IntegerRing, R: ?Sized + ZnRing, F, G>(from: &I, to: &R, to_large_int_ring: &J, el: I::Element, hom: &BigIntToZnHom<I, J, R>, from_positive_representative_exact: F, from_positive_representative_bounded: G) -> R::Element
216        where I: CanIsoFromTo<R::IntegerRingBase> + CanIsoFromTo<J>,
217            F: FnOnce(El<R::IntegerRing>) -> R::Element,
218            G: FnOnce(J::Element) -> R::Element
219    {
220        let (neg, n) = if from.is_neg(&el) {
221            (true, from.negate(el))
222        } else {
223            (false, el)
224        };
225        let ZZ = to.integer_ring().get_ring();
226        let highbit_el = from.abs_highest_set_bit(&n).unwrap_or(0);
227
228        let reduced = if highbit_el < hom.highbit_mod {
229            from_positive_representative_exact(from.map_out(ZZ, n, &hom.iso))
230        } else if highbit_el < hom.highbit_bound {
231            from_positive_representative_bounded(from.map_out(to_large_int_ring, n, &hom.iso2))
232        } else {
233            from_positive_representative_exact(from.map_out(ZZ, from.euclidean_rem(n, &from.map_in_ref(ZZ, to.modulus(), &hom.hom)), &hom.iso))
234        };
235        if neg {
236            to.negate(reduced)
237        } else {
238            reduced
239        }
240    }
241
242    ///
243    /// Generates a uniformly random element of `Z/nZ` using the randomness of `rng`.
244    /// Designed to be used when implementing [`crate::rings::finite::FiniteRing::random_element()`].
245    /// 
246    #[stability::unstable(feature = "enable")]
247    pub fn random_element<R: ZnRing, G: FnMut() -> u64>(ring: &R, rng: G) -> R::Element {
248        ring.map_in(
249            ring.integer_ring().get_ring(), 
250            ring.integer_ring().get_uniformly_random(ring.modulus(), rng), 
251            &ring.has_canonical_hom(ring.integer_ring().get_ring()).unwrap()
252        )
253    }
254
255    ///
256    /// Computes the checked division in `Z/nZ`. Designed to be used when implementing
257    /// [`crate::divisibility::DivisibilityRing::checked_left_div()`].
258    /// 
259    #[stability::unstable(feature = "enable")]
260    pub fn checked_left_div<R: ZnRingStore>(ring: R, lhs: &El<R>, rhs: &El<R>) -> Option<El<R>>
261        where R::Type: ZnRing
262    {
263        if ring.is_zero(lhs) {
264            return Some(ring.zero());
265        }
266        let int_ring = ring.integer_ring();
267        let lhs_lift = ring.smallest_positive_lift(ring.clone_el(lhs));
268        let rhs_lift = ring.smallest_positive_lift(ring.clone_el(rhs));
269        let (s, _, d) = int_ring.extended_ideal_gen(&rhs_lift, ring.modulus());
270        if let Some(quotient) = int_ring.checked_div(&lhs_lift, &d) {
271            Some(ring.mul(ring.coerce(int_ring, quotient), ring.coerce(int_ring, s)))
272        } else {
273            None
274        }
275    }
276    
277    #[stability::unstable(feature = "enable")]
278    pub fn checked_div_min<R: ZnRingStore>(ring: R, lhs: &El<R>, rhs: &El<R>) -> Option<El<R>>
279        where R::Type: ZnRing
280    {
281        if ring.is_zero(lhs) && ring.is_zero(rhs) {
282            return Some(ring.one());
283        }
284        assert!(ring.is_noetherian());
285        let int_ring = ring.integer_ring();
286        let rhs_ann = int_ring.checked_div(ring.modulus(), &int_ring.ideal_gen(ring.modulus(), &ring.smallest_positive_lift(ring.clone_el(rhs)))).unwrap();
287        let some_sol = ring.smallest_positive_lift(ring.checked_div(lhs, rhs)?);
288        let minimal_solution = int_ring.euclidean_rem(some_sol, &rhs_ann);
289        if int_ring.is_zero(&minimal_solution) {
290            return Some(ring.coerce(&int_ring, rhs_ann));
291        } else {
292            return Some(ring.coerce(&int_ring, minimal_solution));
293        }
294    }
295
296    #[stability::unstable(feature = "enable")]
297    pub fn interpolation_ring<R: ZnRingStore>(ring: R, count: usize) -> GaloisFieldOver<R>
298        where R: Clone,
299            R::Type: ZnRing + Field + SelfIso + CanHomFrom<StaticRingBase<i64>>
300    {
301        let ZZbig = BigIntRing::RING;
302        let modulus = int_cast(ring.integer_ring().clone_el(ring.modulus()), ZZbig, ring.integer_ring());
303        let count = int_cast(count as i64, ZZbig, StaticRing::<i64>::RING);
304        let degree = int_bisect::find_root_floor(StaticRing::<i64>::RING, 1, |d| if *d > 0 && ZZbig.is_gt(&ZZbig.pow(ZZbig.clone_el(&modulus), *d as usize), &count) {
305            1
306        } else {
307            -1
308        }) + 1;
309        assert!(degree >= 1);
310        return GaloisField::new_with(ring, degree as usize, Global, STANDARD_CONVOLUTION);
311    }
312}
313
314///
315/// The [`crate::ring::RingStore`] corresponding to [`ZnRing`].
316/// 
317pub trait ZnRingStore: FiniteRingStore
318    where Self::Type: ZnRing
319{    
320    delegate!{ ZnRing, fn integer_ring(&self) -> &<Self::Type as ZnRing>::IntegerRing }
321    delegate!{ ZnRing, fn modulus(&self) -> &El<<Self::Type as ZnRing>::IntegerRing> }
322    delegate!{ ZnRing, fn smallest_positive_lift(&self, el: El<Self>) -> El<<Self::Type as ZnRing>::IntegerRing> }
323    delegate!{ ZnRing, fn smallest_lift(&self, el: El<Self>) -> El<<Self::Type as ZnRing>::IntegerRing> }
324    delegate!{ ZnRing, fn any_lift(&self, el: El<Self>) -> El<<Self::Type as ZnRing>::IntegerRing> }
325    delegate!{ ZnRing, fn is_field(&self) -> bool }
326
327    fn as_field(self) -> Result<RingValue<AsFieldBase<Self>>, Self> 
328        where Self: Sized
329    {
330        if self.is_field() {
331            Ok(RingValue::from(AsFieldBase::promise_is_perfect_field(self)))
332        } else {
333            Err(self)
334        }
335    }
336}
337
338impl<R: RingStore> ZnRingStore for R
339    where R::Type: ZnRing
340{}
341
342///
343/// Trait for algorithms that require some implementation of
344/// `Z/nZ`, but do not care which. 
345/// 
346/// See [`choose_zn_impl()`] for details.
347/// 
348pub trait ZnOperation {
349    
350    type Output<'a>
351        where Self: 'a;
352
353    fn call<'a, R>(self, ring: R) -> Self::Output<'a>
354        where Self: 'a, 
355            R: 'a + RingStore + Send + Sync, 
356            R::Type: ZnRing, 
357            El<R>: Send;
358}
359
360///
361/// Calls the given function with some implementation of the ring
362/// `Z/nZ`, chosen depending on `n` to provide best performance.
363/// 
364/// It is currently necessary to write all the boilerplate code that
365/// comes with manually implementing [`ZnOperation`]. I experimented with
366/// macros, but currently something simple seems like the best solution.
367/// 
368/// # Example
369/// ```
370/// # use feanor_math::ring::*;
371/// # use feanor_math::homomorphism::*;
372/// # use feanor_math::rings::zn::*;
373/// # use feanor_math::primitive_int::*;
374/// # use feanor_math::integer::*;
375/// # use feanor_math::assert_el_eq;
376/// 
377/// let int_value = 4;
378/// // work in Z/17Z without explicitly choosing an implementation
379/// struct DoStuff { int_value: i64 }
380/// impl ZnOperation for DoStuff {
381///     type Output<'a> = ()
382///         where Self: 'a;
383/// 
384///     fn call<'a, R>(self, Zn: R) -> ()
385///         where Self: 'a,
386///             R: 'a + RingStore,
387///             R::Type: ZnRing
388///     {
389///         let value = Zn.coerce(Zn.integer_ring(), int_cast(self.int_value, Zn.integer_ring(), &StaticRing::<i64>::RING));
390///         assert_el_eq!(Zn, Zn.int_hom().map(-1), Zn.mul_ref(&value, &value));
391///     } 
392/// }
393/// choose_zn_impl(StaticRing::<i64>::RING, 17, DoStuff { int_value });
394/// ```
395/// 
396pub fn choose_zn_impl<'a, I, F>(ZZ: I, n: El<I>, f: F) -> F::Output<'a>
397    where I: 'a + RingStore,
398        I::Type: IntegerRing,
399        F: ZnOperation
400{
401    if ZZ.abs_highest_set_bit(&n).unwrap_or(0) < 57 {
402        f.call(zn_64::Zn::new(StaticRing::<i64>::RING.coerce(&ZZ, n) as u64))
403    } else {
404        f.call(zn_big::Zn::new(BigIntRing::RING, int_cast(n, &BigIntRing::RING, &ZZ)))
405    }
406}
407
408#[test]
409fn test_choose_zn_impl() {
410    let int_value = 4;
411    // work in Z/17Z without explicitly choosing an implementation
412    struct DoStuff { int_value: i64 }
413    impl ZnOperation for DoStuff {
414
415        type Output<'a> = ()
416            where Self: 'a;
417
418        fn call<'a, R>(self, Zn: R)
419            where R: 'a + RingStore, R::Type: ZnRing
420        {
421            let value = Zn.coerce(Zn.integer_ring(), int_cast(self.int_value, Zn.integer_ring(), &StaticRing::<i64>::RING));
422            assert_el_eq!(Zn, Zn.int_hom().map(-1), Zn.mul_ref(&value, &value));
423        } 
424    }
425    choose_zn_impl(StaticRing::<i64>::RING, 17, DoStuff { int_value });
426}
427
428#[derive(Debug, Clone, Copy, PartialEq, Eq)]
429enum ReductionMapRequirements {
430    SmallestLift,
431    ExplicitReduce
432}
433
434///
435/// The homomorphism `Z/nZ -> Z/mZ` that exists whenever `m | n`. In
436/// addition to the map, this also provides a function [`ZnReductionMap::smallest_lift()`]
437/// that computes the "smallest" preimage under the map, and a function
438/// [`ZnReductionMap::mul_quotient_fraction()`], that computes the multiplication
439/// with `n/m` while also changing from `Z/mZ` to `Z/nZ`. This is very
440/// useful in many number theoretic applications, where one often has to switch
441/// between `Z/nZ` and `Z/mZ`.
442/// 
443/// Furthermore, many implementations of `ZnRing` currently do not support
444/// [`CanHomFrom`]-homomorphisms when the moduli are different (but divide each
445/// other).
446/// 
447pub struct ZnReductionMap<R, S>
448    where R: RingStore,
449        R::Type: ZnRing,
450        S: RingStore,
451        S::Type: ZnRing
452{
453    from: R,
454    to: S,
455    fraction_of_quotients: El<R>,
456    to_modulus: El<<R::Type as ZnRing>::IntegerRing>,
457    to_from_int: <S::Type as CanHomFrom<<S::Type as ZnRing>::IntegerRingBase>>::Homomorphism,
458    from_from_int: <R::Type as CanHomFrom<<R::Type as ZnRing>::IntegerRingBase>>::Homomorphism,
459    map_forward_requirement: ReductionMapRequirements
460}
461
462impl<R, S> ZnReductionMap<R, S>
463    where R: RingStore,
464        R::Type: ZnRing,
465        S: RingStore,
466        S::Type: ZnRing
467{
468    pub fn new(from: R, to: S) -> Option<Self> {
469        let from_char = from.characteristic(&BigIntRing::RING).unwrap();
470        let to_char = to.characteristic(&BigIntRing::RING).unwrap();
471        if let Some(frac) = BigIntRing::RING.checked_div(&from_char, &to_char) {
472            let map_forward_requirement: ReductionMapRequirements = if to.integer_ring().get_ring().representable_bits().is_none() || BigIntRing::RING.is_lt(&from_char, &BigIntRing::RING.power_of_two(to.integer_ring().get_ring().representable_bits().unwrap())) {
473                ReductionMapRequirements::SmallestLift
474            } else {
475                ReductionMapRequirements::ExplicitReduce
476            };
477            Some(Self {
478                map_forward_requirement: map_forward_requirement,
479                to_modulus: int_cast(to.integer_ring().clone_el(to.modulus()), from.integer_ring(), to.integer_ring()),
480                to_from_int: to.get_ring().has_canonical_hom(to.integer_ring().get_ring()).unwrap(),
481                from_from_int: from.get_ring().has_canonical_hom(from.integer_ring().get_ring()).unwrap(),
482                fraction_of_quotients: from.can_hom(from.integer_ring()).unwrap().map(int_cast(frac, from.integer_ring(), BigIntRing::RING)),
483                from: from,
484                to: to,
485            })
486        } else {
487            None
488        }
489    }
490
491    ///
492    /// Computes the additive group homomorphism `Z/mZ -> Z/nZ, x -> (n/m)x`.
493    /// 
494    /// # Example
495    /// ```
496    /// # use feanor_math::assert_el_eq;
497    /// # use feanor_math::ring::*;
498    /// # use feanor_math::homomorphism::*;
499    /// # use feanor_math::rings::zn::*;
500    /// # use feanor_math::rings::zn::zn_64::*;
501    /// let Z5 = Zn::new(5);
502    /// let Z25 = Zn::new(25);
503    /// let f = ZnReductionMap::new(&Z25, &Z5).unwrap();
504    /// assert_el_eq!(Z25, Z25.int_hom().map(15), f.mul_quotient_fraction(Z5.int_hom().map(3)));
505    /// ```
506    /// 
507    pub fn mul_quotient_fraction(&self, x: El<S>) -> El<R> {
508        self.from.mul_ref_snd(self.any_preimage(x), &self.fraction_of_quotients)
509    }
510
511    ///
512    /// Computes the smallest preimage under the reduction map `Z/nZ -> Z/mZ`, where
513    /// "smallest" refers to the element that has the smallest lift to `Z`.
514    /// 
515    /// # Example
516    /// ```
517    /// # use feanor_math::assert_el_eq;
518    /// # use feanor_math::ring::*;
519    /// # use feanor_math::homomorphism::*;
520    /// # use feanor_math::rings::zn::*;
521    /// # use feanor_math::rings::zn::zn_64::*;
522    /// let Z5 = Zn::new(5);
523    /// let Z25 = Zn::new(25);
524    /// let f = ZnReductionMap::new(&Z25, &Z5).unwrap();
525    /// assert_el_eq!(Z25, Z25.int_hom().map(-2), f.smallest_lift(Z5.int_hom().map(3)));
526    /// ```
527    /// 
528    pub fn smallest_lift(&self, x: El<S>) -> El<R> {
529        self.from.get_ring().map_in(self.from.integer_ring().get_ring(), int_cast(self.to.smallest_lift(x), self.from.integer_ring(), self.to.integer_ring()), &self.from_from_int)
530    }
531
532    pub fn any_preimage(&self, x: El<S>) -> El<R> {
533        // the problem is that we don't know if `to.any_lift(x)` will fit into `from.integer_ring()`;
534        // furthermore, profiling indicates that it won't help a lot anyway, since taking the smallest lift
535        // now will usually make reduction cheaper later
536        self.smallest_lift(x)
537    }
538
539    pub fn smallest_lift_ref(&self, x: &El<S>) -> El<R> {
540        self.smallest_lift(self.codomain().clone_el(x))
541    }
542}
543
544impl<R, S> Homomorphism<R::Type, S::Type> for ZnReductionMap<R, S>
545    where R: RingStore,
546        R::Type: ZnRing,
547        S: RingStore,
548        S::Type: ZnRing
549{
550    type CodomainStore = S;
551    type DomainStore = R;
552
553    fn map(&self, x: El<R>) -> El<S> {
554        let value = match self.map_forward_requirement {
555            ReductionMapRequirements::SmallestLift => self.from.smallest_lift(x),
556            ReductionMapRequirements::ExplicitReduce => self.from.integer_ring().euclidean_rem(self.from.any_lift(x), &self.to_modulus)
557        };
558        self.to.get_ring().map_in(self.to.integer_ring().get_ring(), int_cast(value, self.to.integer_ring(), self.from.integer_ring()), &self.to_from_int)
559    }
560
561    fn codomain<'a>(&'a self) -> &'a Self::CodomainStore {
562        &self.to
563    }
564
565    fn domain<'a>(&'a self) -> &'a Self::DomainStore {
566        &self.from
567    }
568}
569
570#[cfg(any(test, feature = "generic_tests"))]
571pub mod generic_tests {
572
573    use super::*;
574    use crate::primitive_int::{StaticRingBase, StaticRing};
575
576    pub fn test_zn_axioms<R: RingStore>(R: R)
577        where R::Type: ZnRing,
578            <R::Type as ZnRing>::IntegerRingBase: CanIsoFromTo<StaticRingBase<i128>> + CanIsoFromTo<StaticRingBase<i32>>
579    {
580        let ZZ = R.integer_ring();
581        let n = R.modulus();
582
583        assert!(R.is_zero(&R.coerce(ZZ, ZZ.clone_el(n))));
584        assert!(R.is_field() == algorithms::miller_rabin::is_prime(ZZ, n, 10));
585
586        let mut k = ZZ.one();
587        while ZZ.is_lt(&k, &n) {
588            assert!(!R.is_zero(&R.coerce(ZZ, ZZ.clone_el(&k))));
589            ZZ.add_assign(&mut k, ZZ.one());
590        }
591
592        let all_elements = R.elements().collect::<Vec<_>>();
593        assert_eq!(int_cast(ZZ.clone_el(n), &StaticRing::<i128>::RING, &ZZ) as usize, all_elements.len());
594        for (i, x) in all_elements.iter().enumerate() {
595            for (j, y) in all_elements.iter().enumerate() {
596                assert!(i == j || !R.eq_el(x, y));
597            }
598        }
599    }
600
601    pub fn test_map_in_large_int<R: RingStore>(R: R)
602        where <R as RingStore>::Type: ZnRing + CanHomFrom<BigIntRingBase>
603    {
604        let ZZ_big = BigIntRing::RING;
605        let n = ZZ_big.power_of_two(1000);
606        let x = R.coerce(&ZZ_big, n);
607        assert!(R.eq_el(&R.pow(R.int_hom().map(2), 1000), &x));
608    }
609}
610
611#[test]
612fn test_reduction_map_large_value() {
613    let ring1 = zn_64::Zn::new(1 << 42);
614    let ring2 = zn_big::Zn::new(BigIntRing::RING, BigIntRing::RING.power_of_two(666));
615    let reduce = ZnReductionMap::new(&ring2, ring1).unwrap();
616    assert_el_eq!(ring1, ring1.zero(), reduce.map(ring2.pow(ring2.int_hom().map(2), 665)));
617}
618
619#[test]
620fn test_reduction_map() {
621    let ring1 = zn_64::Zn::new(257);
622    let ring2 = zn_big::Zn::new(StaticRing::<i128>::RING, 257 * 7);
623
624    crate::homomorphism::generic_tests::test_homomorphism_axioms(ZnReductionMap::new(&ring2, &ring1).unwrap(), ring2.elements().step_by(8));
625
626    let ring1 = zn_big::Zn::new(StaticRing::<i16>::RING, 3);
627    let ring2 = zn_big::Zn::new(BigIntRing::RING, BigIntRing::RING.int_hom().map(65537 * 3));
628
629    crate::homomorphism::generic_tests::test_homomorphism_axioms(ZnReductionMap::new(&ring2, &ring1).unwrap(), ring2.elements().step_by(1024));
630}
631
632#[test]
633fn test_generic_impl_checked_div_min() {
634    let ring = zn_64::Zn::new(5 * 7 * 11 * 13);
635    let actual = ring.annihilator(&ring.int_hom().map(1001));
636    let expected = ring.int_hom().map(5);
637    assert!(ring.checked_div(&expected, &actual).is_some());
638    assert!(ring.checked_div(&actual, &expected).is_some());
639
640    let actual = ring.annihilator(&ring.zero());
641    let expected = ring.one();
642    assert!(ring.checked_div(&expected, &actual).is_some());
643    assert!(ring.checked_div(&actual, &expected).is_some());
644}
feanor_math/rings/zn/mod.rs

feanor_math/rings/zn/
mod.rs
