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 from_modulus<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    
147        pub struct BigIntToZnHom<I: ?Sized + IntegerRing, J: ?Sized + IntegerRing, R: ?Sized + ZnRing>
148        where I: CanIsoFromTo<R::IntegerRingBase> + CanIsoFromTo<J>
149    {
150        highbit_mod: usize,
151        highbit_bound: usize,
152        int_ring: PhantomData<I>,
153        to_large_int_ring: PhantomData<J>,
154        hom: <I as CanHomFrom<R::IntegerRingBase>>::Homomorphism,
155        iso: <I as CanIsoFromTo<R::IntegerRingBase>>::Isomorphism,
156        iso2: <I as CanIsoFromTo<J>>::Isomorphism
157    }
158
159    ///
160    /// See [`map_in_from_bigint()`].
161    /// 
162    /// This will only ever return `None` if one of the integer ring `has_canonical_hom/iso` returns `None`.
163    /// 
164    #[stability::unstable(feature = "enable")]
165    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>>
166        where I: CanIsoFromTo<R::IntegerRingBase> + CanIsoFromTo<J>
167    {
168        if let Some(bound) = bounded_reduce_bound {
169            Some(BigIntToZnHom {
170                highbit_mod: to.integer_ring().abs_highest_set_bit(to.modulus()).unwrap(),
171                highbit_bound: to_large_int_ring.abs_highest_set_bit(bound).unwrap(),
172                int_ring: PhantomData,
173                to_large_int_ring: PhantomData,
174                hom: from.has_canonical_hom(to.integer_ring().get_ring())?,
175                iso: from.has_canonical_iso(to.integer_ring().get_ring())?,
176                iso2: from.has_canonical_iso(to_large_int_ring)?
177            })
178        } else {
179            Some(BigIntToZnHom {
180                highbit_mod: to.integer_ring().abs_highest_set_bit(to.modulus()).unwrap(),
181                highbit_bound: usize::MAX,
182                int_ring: PhantomData,
183                to_large_int_ring: PhantomData,
184                hom: from.has_canonical_hom(to.integer_ring().get_ring())?,
185                iso: from.has_canonical_iso(to.integer_ring().get_ring())?,
186                iso2: from.has_canonical_iso(to_large_int_ring)?
187            })
188        }
189    }
190
191    ///
192    /// A parameterized, generic variant of the reduction `Z -> Z/nZ`.
193    /// It considers the following situations:
194    ///  - the source ring `Z` might not be large enough to represent `n`
195    ///  - the integer ring associated to the destination ring `Z/nZ` might not be large enough to represent the input
196    ///  - the destination ring might use Barett reductions (or similar) for fast modular reduction if the input is bounded by some fixed bound `B`
197    ///  - general modular reduction modulo `n` is only performed in the source ring if necessary
198    /// 
199    /// In particular, we use the following additional parameters:
200    ///  - `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`)
201    ///  - `from_positive_representative_exact`: a function that performs the restricted reduction `{0, ..., n - 1} -> Z/nZ`
202    ///  - `from_positive_representative_bounded`: a function that performs the restricted reduction `{0, ..., B - 1} -> Z/nZ`
203    /// 
204    /// 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
205    /// is likely to take longer than the actual modular reduction.
206    /// 
207    /// 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
208    /// numbers than necessary is used. Furthermore, if the integer rings used can represent some but not all positive numbers of a certain bitlength, 
209    /// there might be rare edge cases with panics/overflows. 
210    /// 
211    /// 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
212    /// 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
213    /// integer rings `StaticRing::<ixx>::RING` are used, or if `B >= 2n`.
214    /// 
215    #[stability::unstable(feature = "enable")]
216    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
217        where I: CanIsoFromTo<R::IntegerRingBase> + CanIsoFromTo<J>,
218            F: FnOnce(El<R::IntegerRing>) -> R::Element,
219            G: FnOnce(J::Element) -> R::Element
220    {
221        let (neg, n) = if from.is_neg(&el) {
222            (true, from.negate(el))
223        } else {
224            (false, el)
225        };
226        let ZZ = to.integer_ring().get_ring();
227        let highbit_el = from.abs_highest_set_bit(&n).unwrap_or(0);
228
229        let reduced = if highbit_el < hom.highbit_mod {
230            from_positive_representative_exact(from.map_out(ZZ, n, &hom.iso))
231        } else if highbit_el < hom.highbit_bound {
232            from_positive_representative_bounded(from.map_out(to_large_int_ring, n, &hom.iso2))
233        } else {
234            from_positive_representative_exact(from.map_out(ZZ, from.euclidean_rem(n, &from.map_in_ref(ZZ, to.modulus(), &hom.hom)), &hom.iso))
235        };
236        if neg {
237            to.negate(reduced)
238        } else {
239            reduced
240        }
241    }
242
243    ///
244    /// Generates a uniformly random element of `Z/nZ` using the randomness of `rng`.
245    /// Designed to be used when implementing [`crate::rings::finite::FiniteRing::random_element()`].
246    /// 
247    #[stability::unstable(feature = "enable")]
248    pub fn random_element<R: ZnRing, G: FnMut() -> u64>(ring: &R, rng: G) -> R::Element {
249        ring.map_in(
250            ring.integer_ring().get_ring(), 
251            ring.integer_ring().get_uniformly_random(ring.modulus(), rng), 
252            &ring.has_canonical_hom(ring.integer_ring().get_ring()).unwrap()
253        )
254    }
255
256    ///
257    /// Computes the checked division in `Z/nZ`. Designed to be used when implementing
258    /// [`crate::divisibility::DivisibilityRing::checked_left_div()`].
259    /// 
260    #[stability::unstable(feature = "enable")]
261    pub fn checked_left_div<R: ZnRingStore>(ring: R, lhs: &El<R>, rhs: &El<R>) -> Option<El<R>>
262        where R::Type: ZnRing
263    {
264        if ring.is_zero(lhs) {
265            return Some(ring.zero());
266        }
267        let int_ring = ring.integer_ring();
268        let lhs_lift = ring.smallest_positive_lift(ring.clone_el(lhs));
269        let rhs_lift = ring.smallest_positive_lift(ring.clone_el(rhs));
270        let (s, _, d) = int_ring.extended_ideal_gen(&rhs_lift, ring.modulus());
271        if let Some(quotient) = int_ring.checked_div(&lhs_lift, &d) {
272            Some(ring.mul(ring.coerce(int_ring, quotient), ring.coerce(int_ring, s)))
273        } else {
274            None
275        }
276    }
277    
278    #[stability::unstable(feature = "enable")]
279    pub fn checked_div_min<R: ZnRingStore>(ring: R, lhs: &El<R>, rhs: &El<R>) -> Option<El<R>>
280        where R::Type: ZnRing
281    {
282        if ring.is_zero(lhs) && ring.is_zero(rhs) {
283            return Some(ring.one());
284        }
285        assert!(ring.is_noetherian());
286        let int_ring = ring.integer_ring();
287        let rhs_ann = int_ring.checked_div(ring.modulus(), &int_ring.ideal_gen(ring.modulus(), &ring.smallest_positive_lift(ring.clone_el(rhs)))).unwrap();
288        let some_sol = ring.smallest_positive_lift(ring.checked_div(lhs, rhs)?);
289        let minimal_solution = int_ring.euclidean_rem(some_sol, &rhs_ann);
290        if int_ring.is_zero(&minimal_solution) {
291            return Some(ring.coerce(&int_ring, rhs_ann));
292        } else {
293            return Some(ring.coerce(&int_ring, minimal_solution));
294        }
295    }
296
297    #[stability::unstable(feature = "enable")]
298    pub fn interpolation_ring<R: ZnRingStore>(ring: R, count: usize) -> GaloisFieldOver<R>
299        where R: Clone,
300            R::Type: ZnRing + Field + SelfIso + CanHomFrom<StaticRingBase<i64>>
301    {
302        let ZZbig = BigIntRing::RING;
303        let modulus = int_cast(ring.integer_ring().clone_el(ring.modulus()), ZZbig, ring.integer_ring());
304        let count = int_cast(count.try_into().unwrap(), ZZbig, StaticRing::<i64>::RING);
305        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) {
306            1
307        } else {
308            -1
309        }) + 1;
310        assert!(degree >= 1);
311        return GaloisField::new_with_convolution(ring, degree as usize, Global, STANDARD_CONVOLUTION);
312    }
313}
314
315///
316/// The [`crate::ring::RingStore`] corresponding to [`ZnRing`].
317/// 
318pub trait ZnRingStore: FiniteRingStore
319    where Self::Type: ZnRing
320{    
321    delegate!{ ZnRing, fn integer_ring(&self) -> &<Self::Type as ZnRing>::IntegerRing }
322    delegate!{ ZnRing, fn modulus(&self) -> &El<<Self::Type as ZnRing>::IntegerRing> }
323    delegate!{ ZnRing, fn smallest_positive_lift(&self, el: El<Self>) -> El<<Self::Type as ZnRing>::IntegerRing> }
324    delegate!{ ZnRing, fn smallest_lift(&self, el: El<Self>) -> El<<Self::Type as ZnRing>::IntegerRing> }
325    delegate!{ ZnRing, fn any_lift(&self, el: El<Self>) -> El<<Self::Type as ZnRing>::IntegerRing> }
326    delegate!{ ZnRing, fn is_field(&self) -> bool }
327
328    fn as_field(self) -> Result<RingValue<AsFieldBase<Self>>, Self> 
329        where Self: Sized
330    {
331        if self.is_field() {
332            Ok(RingValue::from(AsFieldBase::promise_is_perfect_field(self)))
333        } else {
334            Err(self)
335        }
336    }
337}
338
339impl<R: RingStore> ZnRingStore for R
340    where R::Type: ZnRing
341{}
342
343///
344/// Trait for algorithms that require some implementation of
345/// `Z/nZ`, but do not care which. 
346/// 
347/// See [`choose_zn_impl()`] for details.
348/// 
349pub trait ZnOperation {
350    
351    type Output<'a>
352        where Self: 'a;
353
354    fn call<'a, R>(self, ring: R) -> Self::Output<'a>
355        where Self: 'a, 
356            R: 'a + RingStore + Send + Sync, 
357            R::Type: ZnRing, 
358            El<R>: Send;
359}
360
361///
362/// Calls the given function with some implementation of the ring
363/// `Z/nZ`, chosen depending on `n` to provide best performance.
364/// 
365/// It is currently necessary to write all the boilerplate code that
366/// comes with manually implementing [`ZnOperation`]. I experimented with
367/// macros, but currently something simple seems like the best solution.
368/// 
369/// # Example
370/// ```rust
371/// # use feanor_math::ring::*;
372/// # use feanor_math::homomorphism::*;
373/// # use feanor_math::rings::zn::*;
374/// # use feanor_math::primitive_int::*;
375/// # use feanor_math::integer::*;
376/// # use feanor_math::assert_el_eq;
377/// 
378/// let int_value = 4;
379/// // work in Z/17Z without explicitly choosing an implementation
380/// struct DoStuff { int_value: i64 }
381/// impl ZnOperation for DoStuff {
382///     type Output<'a> = ()
383///         where Self: 'a;
384/// 
385///     fn call<'a, R>(self, Zn: R) -> ()
386///         where Self: 'a,
387///             R: 'a + RingStore,
388///             R::Type: ZnRing
389///     {
390///         let value = Zn.coerce(Zn.integer_ring(), int_cast(self.int_value, Zn.integer_ring(), &StaticRing::<i64>::RING));
391///         assert_el_eq!(Zn, Zn.int_hom().map(-1), Zn.mul_ref(&value, &value));
392///     } 
393/// }
394/// choose_zn_impl(StaticRing::<i64>::RING, 17, DoStuff { int_value });
395/// ```
396/// 
397pub fn choose_zn_impl<'a, I, F>(ZZ: I, n: El<I>, f: F) -> F::Output<'a>
398    where I: 'a + RingStore,
399        I::Type: IntegerRing,
400        F: ZnOperation
401{
402    if ZZ.abs_highest_set_bit(&n).unwrap_or(0) < 57 {
403        f.call(zn_64::Zn::new(StaticRing::<i64>::RING.coerce(&ZZ, n) as u64))
404    } else {
405        f.call(zn_big::Zn::new(BigIntRing::RING, int_cast(n, &BigIntRing::RING, &ZZ)))
406    }
407}
408
409#[test]
410fn test_choose_zn_impl() {
411    let int_value = 4;
412    // work in Z/17Z without explicitly choosing an implementation
413    struct DoStuff { int_value: i64 }
414    impl ZnOperation for DoStuff {
415
416        type Output<'a> = ()
417            where Self: 'a;
418
419        fn call<'a, R>(self, Zn: R)
420            where R: 'a + RingStore, R::Type: ZnRing
421        {
422            let value = Zn.coerce(Zn.integer_ring(), int_cast(self.int_value, Zn.integer_ring(), &StaticRing::<i64>::RING));
423            assert_el_eq!(Zn, Zn.int_hom().map(-1), Zn.mul_ref(&value, &value));
424        } 
425    }
426    choose_zn_impl(StaticRing::<i64>::RING, 17, DoStuff { int_value });
427}
428
429#[derive(Debug, Clone, Copy, PartialEq, Eq)]
430enum ReductionMapRequirements {
431    SmallestLift,
432    ExplicitReduce
433}
434
435///
436/// The homomorphism `Z/nZ -> Z/mZ` that exists whenever `m | n`. In
437/// addition to the map, this also provides a function [`ZnReductionMap::smallest_lift()`]
438/// that computes the "smallest" preimage under the map, and a function
439/// [`ZnReductionMap::mul_quotient_fraction()`], that computes the multiplication
440/// with `n/m` while also changing from `Z/mZ` to `Z/nZ`. This is very
441/// useful in many number theoretic applications, where one often has to switch
442/// between `Z/nZ` and `Z/mZ`.
443/// 
444/// Furthermore, many implementations of `ZnRing` currently do not support
445/// [`CanHomFrom`]-homomorphisms when the moduli are different (but divide each
446/// other).
447/// 
448pub struct ZnReductionMap<R, S>
449    where R: RingStore,
450        R::Type: ZnRing,
451        S: RingStore,
452        S::Type: ZnRing
453{
454    from: R,
455    to: S,
456    fraction_of_quotients: El<R>,
457    to_modulus: El<<R::Type as ZnRing>::IntegerRing>,
458    to_from_int: <S::Type as CanHomFrom<<S::Type as ZnRing>::IntegerRingBase>>::Homomorphism,
459    from_from_int: <R::Type as CanHomFrom<<R::Type as ZnRing>::IntegerRingBase>>::Homomorphism,
460    map_forward_requirement: ReductionMapRequirements
461}
462
463impl<R, S> ZnReductionMap<R, S>
464    where R: RingStore,
465        R::Type: ZnRing,
466        S: RingStore,
467        S::Type: ZnRing
468{
469    pub fn new(from: R, to: S) -> Option<Self> {
470        let from_char = from.characteristic(&BigIntRing::RING).unwrap();
471        let to_char = to.characteristic(&BigIntRing::RING).unwrap();
472        if let Some(frac) = BigIntRing::RING.checked_div(&from_char, &to_char) {
473            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())) {
474                ReductionMapRequirements::SmallestLift
475            } else {
476                ReductionMapRequirements::ExplicitReduce
477            };
478            Some(Self {
479                map_forward_requirement: map_forward_requirement,
480                to_modulus: int_cast(to.integer_ring().clone_el(to.modulus()), from.integer_ring(), to.integer_ring()),
481                to_from_int: to.get_ring().has_canonical_hom(to.integer_ring().get_ring()).unwrap(),
482                from_from_int: from.get_ring().has_canonical_hom(from.integer_ring().get_ring()).unwrap(),
483                fraction_of_quotients: from.can_hom(from.integer_ring()).unwrap().map(int_cast(frac, from.integer_ring(), BigIntRing::RING)),
484                from: from,
485                to: to,
486            })
487        } else {
488            None
489        }
490    }
491
492    ///
493    /// Computes the additive group homomorphism `Z/mZ -> Z/nZ, x -> (n/m)x`.
494    /// 
495    /// # Example
496    /// ```rust
497    /// # use feanor_math::assert_el_eq;
498    /// # use feanor_math::ring::*;
499    /// # use feanor_math::homomorphism::*;
500    /// # use feanor_math::rings::zn::*;
501    /// # use feanor_math::rings::zn::zn_64::*;
502    /// let Z5 = Zn::new(5);
503    /// let Z25 = Zn::new(25);
504    /// let f = ZnReductionMap::new(&Z25, &Z5).unwrap();
505    /// assert_el_eq!(Z25, Z25.int_hom().map(15), f.mul_quotient_fraction(Z5.int_hom().map(3)));
506    /// ```
507    /// 
508    pub fn mul_quotient_fraction(&self, x: El<S>) -> El<R> {
509        self.from.mul_ref_snd(self.any_preimage(x), &self.fraction_of_quotients)
510    }
511
512    ///
513    /// Computes the smallest preimage under the reduction map `Z/nZ -> Z/mZ`, where
514    /// "smallest" refers to the element that has the smallest lift to `Z`.
515    /// 
516    /// # Example
517    /// ```rust
518    /// # use feanor_math::assert_el_eq;
519    /// # use feanor_math::ring::*;
520    /// # use feanor_math::homomorphism::*;
521    /// # use feanor_math::rings::zn::*;
522    /// # use feanor_math::rings::zn::zn_64::*;
523    /// let Z5 = Zn::new(5);
524    /// let Z25 = Zn::new(25);
525    /// let f = ZnReductionMap::new(&Z25, &Z5).unwrap();
526    /// assert_el_eq!(Z25, Z25.int_hom().map(-2), f.smallest_lift(Z5.int_hom().map(3)));
527    /// ```
528    /// 
529    pub fn smallest_lift(&self, x: El<S>) -> El<R> {
530        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)
531    }
532
533    pub fn any_preimage(&self, x: El<S>) -> El<R> {
534        // the problem is that we don't know if `to.any_lift(x)` will fit into `from.integer_ring()`;
535        // furthermore, profiling indicates that it won't help a lot anyway, since taking the smallest lift
536        // now will usually make reduction cheaper later
537        self.smallest_lift(x)
538    }
539
540    pub fn smallest_lift_ref(&self, x: &El<S>) -> El<R> {
541        self.smallest_lift(self.codomain().clone_el(x))
542    }
543}
544
545impl<R, S> Homomorphism<R::Type, S::Type> for ZnReductionMap<R, S>
546    where R: RingStore,
547        R::Type: ZnRing,
548        S: RingStore,
549        S::Type: ZnRing
550{
551    type CodomainStore = S;
552    type DomainStore = R;
553
554    fn map(&self, x: El<R>) -> El<S> {
555        let value = match self.map_forward_requirement {
556            ReductionMapRequirements::SmallestLift => self.from.smallest_lift(x),
557            ReductionMapRequirements::ExplicitReduce => self.from.integer_ring().euclidean_rem(self.from.any_lift(x), &self.to_modulus)
558        };
559        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)
560    }
561
562    fn codomain<'a>(&'a self) -> &'a Self::CodomainStore {
563        &self.to
564    }
565
566    fn domain<'a>(&'a self) -> &'a Self::DomainStore {
567        &self.from
568    }
569}
570
571#[cfg(any(test, feature = "generic_tests"))]
572pub mod generic_tests {
573
574    use super::*;
575    use crate::primitive_int::{StaticRingBase, StaticRing};
576
577    pub fn test_zn_axioms<R: RingStore>(R: R)
578        where R::Type: ZnRing,
579            <R::Type as ZnRing>::IntegerRingBase: CanIsoFromTo<StaticRingBase<i128>> + CanIsoFromTo<StaticRingBase<i32>>
580    {
581        let ZZ = R.integer_ring();
582        let n = R.modulus();
583
584        assert!(R.is_zero(&R.coerce(ZZ, ZZ.clone_el(n))));
585        assert!(R.is_field() == algorithms::miller_rabin::is_prime(ZZ, n, 10));
586
587        let mut k = ZZ.one();
588        while ZZ.is_lt(&k, &n) {
589            assert!(!R.is_zero(&R.coerce(ZZ, ZZ.clone_el(&k))));
590            ZZ.add_assign(&mut k, ZZ.one());
591        }
592
593        let all_elements = R.elements().collect::<Vec<_>>();
594        assert_eq!(int_cast(ZZ.clone_el(n), &StaticRing::<i128>::RING, &ZZ) as usize, all_elements.len());
595        for (i, x) in all_elements.iter().enumerate() {
596            for (j, y) in all_elements.iter().enumerate() {
597                assert!(i == j || !R.eq_el(x, y));
598            }
599        }
600    }
601
602    pub fn test_map_in_large_int<R: RingStore>(R: R)
603        where <R as RingStore>::Type: ZnRing + CanHomFrom<BigIntRingBase>
604    {
605        let ZZ_big = BigIntRing::RING;
606        let n = ZZ_big.power_of_two(1000);
607        let x = R.coerce(&ZZ_big, n);
608        assert!(R.eq_el(&R.pow(R.int_hom().map(2), 1000), &x));
609    }
610}
611
612#[test]
613fn test_reduction_map_large_value() {
614    let ring1 = zn_64::Zn::new(1 << 42);
615    let ring2 = zn_big::Zn::new(BigIntRing::RING, BigIntRing::RING.power_of_two(666));
616    let reduce = ZnReductionMap::new(&ring2, ring1).unwrap();
617    assert_el_eq!(ring1, ring1.zero(), reduce.map(ring2.pow(ring2.int_hom().map(2), 665)));
618}
619
620#[test]
621fn test_reduction_map() {
622    let ring1 = zn_64::Zn::new(257);
623    let ring2 = zn_big::Zn::new(StaticRing::<i128>::RING, 257 * 7);
624
625    crate::homomorphism::generic_tests::test_homomorphism_axioms(ZnReductionMap::new(&ring2, &ring1).unwrap(), ring2.elements().step_by(8));
626
627    let ring1 = zn_big::Zn::new(StaticRing::<i16>::RING, 3);
628    let ring2 = zn_big::Zn::new(BigIntRing::RING, BigIntRing::RING.int_hom().map(65537 * 3));
629
630    crate::homomorphism::generic_tests::test_homomorphism_axioms(ZnReductionMap::new(&ring2, &ring1).unwrap(), ring2.elements().step_by(1024));
631}
632
633#[test]
634fn test_generic_impl_checked_div_min() {
635    let ring = zn_64::Zn::new(5 * 7 * 11 * 13);
636    let actual = ring.annihilator(&ring.int_hom().map(1001));
637    let expected = ring.int_hom().map(5);
638    assert!(ring.checked_div(&expected, &actual).is_some());
639    assert!(ring.checked_div(&actual, &expected).is_some());
640
641    let actual = ring.annihilator(&ring.zero());
642    let expected = ring.one();
643    assert!(ring.checked_div(&expected, &actual).is_some());
644    assert!(ring.checked_div(&actual, &expected).is_some());
645}
feanor_math/rings/zn/mod.rs

feanor_math/rings/zn/
mod.rs
