feanor_math/rings/zn/

mod.rs

use super::field::AsFieldBase;
use super::finite::FiniteRing;
use crate::algorithms;
use crate::divisibility::{DivisibilityRing, DivisibilityRingStore};
use crate::homomorphism::*;
use crate::integer::*;
use crate::ordered::*;
use crate::pid::{EuclideanRingStore, PrincipalIdealRing, *};
use crate::primitive_int::StaticRing;
use crate::ring::*;
use crate::rings::finite::FiniteRingStore;

/// This module contains [`zn_64::Zn`], the new, heavily optimized implementation of `Z/nZ`
/// for moduli `n` of size slightly smaller than 64 bits.
pub mod zn_64;

/// This module contains [`zn_big::Zn`], a general-purpose implementation of
/// Barett reduction. It is relatively slow when instantiated with small fixed-size
/// integer type.
pub mod zn_big;

/// This module contains [`zn_pow2::Zn`], an implementation of `Z/nZ` for moduli of the form `2^k`.
pub mod zn_pow2;

/// This module contains [`zn_rns::Zn`], a residue number system (RNS) implementation of
/// `Z/nZ` for highly composite `n`.
pub mod zn_rns;

/// This module contains [`zn_static::Zn`], an implementation of `Z/nZ` for a small `n`
/// that is known at compile-time.
pub mod zn_static;

/// Trait for all rings that represent a quotient of the integers `Z/nZ` for some integer `n`.
pub trait ZnRing: PrincipalIdealRing + FiniteRing + CanHomFrom<Self::IntegerRingBase> {
    /// there seems to be a problem with associated type bounds, hence we cannot use `Integers:
    /// IntegerRingStore` or `Integers: RingStore<Type: IntegerRing>`
    type IntegerRingBase: IntegerRing + ?Sized;
    type IntegerRing: RingStore<Type = Self::IntegerRingBase>;

    fn integer_ring(&self) -> &Self::IntegerRing;
    fn modulus(&self) -> &El<Self::IntegerRing>;

    /// Computes the smallest positive lift for some `x` in `Z/nZ`, i.e. the smallest positive
    /// integer `m` such that `m = x mod n`.
    ///
    /// 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`) is needed instead, use [`ZnRing::smallest_lift()`].
    fn smallest_positive_lift(&self, el: Self::Element) -> El<Self::IntegerRing>;

    /// Computes any lift for some `x` in `Z/nZ`, i.e. the some integer `m` such that `m = x mod n`.
    ///
    /// The only requirement is that `m` is a valid element of the integer ring, in particular that
    /// it fits within the required amount of bits, if [`ZnRing::IntegerRing`] is a fixed-size
    /// integer ring.
    fn any_lift(&self, el: Self::Element) -> El<Self::IntegerRing> { self.smallest_positive_lift(el) }

    /// If the given integer is within `{ 0, ..., n - 1 }`, returns the corresponding
    /// element in `Z/nZ`. Any other input is considered a logic error.
    ///
    /// Unless the context is absolutely performance-critical, it might be safer to use
    /// the homomorphism provided by [`CanHomFrom`] which performs proper modular reduction
    /// of the input.
    ///
    /// This function never causes undefined behavior, but an invalid input leads to
    /// a logic error. In particular, the result in such a case does not have to be
    /// congruent to the input mod `n`, nor does it even have to be a valid element
    /// of the ring (i.e. operations involving it may not follow the ring axioms).
    /// Implementors are strongly encouraged to check the element during debug builds.
    fn from_int_promise_reduced(&self, x: El<Self::IntegerRing>) -> Self::Element;

    /// Computes the smallest lift for some `x` in `Z/nZ`, i.e. the smallest integer `m` such that
    /// `m = x mod n`.
    ///
    /// This will be one of `-(n - 1)/2, ..., -1, 0, 1, ..., (n - 1)/2` (for odd `n`). If an integer
    /// in `0, 1, ..., n - 1` is needed instead, use [`ZnRing::smallest_positive_lift()`].
    fn smallest_lift(&self, el: Self::Element) -> El<Self::IntegerRing> {
        let result = self.smallest_positive_lift(el);
        let mut mod_half = self.integer_ring().clone_el(self.modulus());
        self.integer_ring().euclidean_div_pow_2(&mut mod_half, 1);
        if self.integer_ring().is_gt(&result, &mod_half) {
            return self.integer_ring().sub_ref_snd(result, self.modulus());
        } else {
            return result;
        }
    }

    /// Returns whether this ring is a field, i.e. whether `n` is prime.
    fn is_field(&self) -> bool { algorithms::miller_rabin::is_prime_base(RingRef::new(self), 10) }
}

/// Trait for implementations of [`ZnRing`] that can be created (possibly with a
/// default configuration) from just the integer modulus.
///
/// I am not yet sure whether to use this trait, or opt for a factory trait (which
/// would then offer more flexibility).
#[stability::unstable(feature = "enable")]
pub trait FromModulusCreateableZnRing: Sized + ZnRing {
    fn from_modulus<F, E>(create_modulus: F) -> Result<Self, E>
    where
        F: FnOnce(&Self::IntegerRingBase) -> Result<El<Self::IntegerRing>, E>;
}

pub mod generic_impls {
    use std::alloc::Global;
    use std::marker::PhantomData;

    use crate::algorithms::convolution::STANDARD_CONVOLUTION;
    use crate::algorithms::int_bisect;
    use crate::divisibility::DivisibilityRingStore;
    use crate::field::*;
    use crate::integer::{IntegerRing, IntegerRingStore};
    use crate::ordered::*;
    use crate::primitive_int::{StaticRing, StaticRingBase};
    use crate::rings::extension::galois_field::{GaloisField, GaloisFieldOver};
    use crate::rings::zn::*;

    /// A generic `ZZ -> Z/nZ` homomorphism. Optimized for the case that values of `ZZ` can be very
    /// large, but allow for efficient estimation of their approximate size.

    pub struct BigIntToZnHom<I: ?Sized + IntegerRing, J: ?Sized + IntegerRing, R: ?Sized + ZnRing>
    where
        I: CanIsoFromTo<R::IntegerRingBase> + CanIsoFromTo<J>,
    {
        highbit_mod: usize,
        highbit_bound: usize,
        int_ring: PhantomData<I>,
        to_large_int_ring: PhantomData<J>,
        hom: <I as CanHomFrom<R::IntegerRingBase>>::Homomorphism,
        iso: <I as CanIsoFromTo<R::IntegerRingBase>>::Isomorphism,
        iso2: <I as CanIsoFromTo<J>>::Isomorphism,
    }

    /// See [`map_in_from_bigint()`].
    ///
    /// This will only ever return `None` if one of the integer ring `has_canonical_hom/iso` returns
    /// `None`.
    #[stability::unstable(feature = "enable")]
    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>>
    where
        I: CanIsoFromTo<R::IntegerRingBase> + CanIsoFromTo<J>,
    {
        if let Some(bound) = bounded_reduce_bound {
            Some(BigIntToZnHom {
                highbit_mod: to.integer_ring().abs_highest_set_bit(to.modulus()).unwrap(),
                highbit_bound: to_large_int_ring.abs_highest_set_bit(bound).unwrap(),
                int_ring: PhantomData,
                to_large_int_ring: PhantomData,
                hom: from.has_canonical_hom(to.integer_ring().get_ring())?,
                iso: from.has_canonical_iso(to.integer_ring().get_ring())?,
                iso2: from.has_canonical_iso(to_large_int_ring)?,
            })
        } else {
            Some(BigIntToZnHom {
                highbit_mod: to.integer_ring().abs_highest_set_bit(to.modulus()).unwrap(),
                highbit_bound: usize::MAX,
                int_ring: PhantomData,
                to_large_int_ring: PhantomData,
                hom: from.has_canonical_hom(to.integer_ring().get_ring())?,
                iso: from.has_canonical_iso(to.integer_ring().get_ring())?,
                iso2: from.has_canonical_iso(to_large_int_ring)?,
            })
        }
    }

    /// A parameterized, generic variant of the reduction `Z -> Z/nZ`.
    /// It considers the following situations:
    ///  - the source ring `Z` might not be large enough to represent `n`
    ///  - the integer ring associated to the destination ring `Z/nZ` might not be large enough to
    ///    represent the input
    ///  - the destination ring might use Barett reductions (or similar) for fast modular reduction
    ///    if the input is bounded by some fixed bound `B`
    ///  - general modular reduction modulo `n` is only performed in the source ring if necessary
    ///
    /// In particular, we use the following additional parameters:
    ///  - `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`)
    ///  - `from_positive_representative_exact`: a function that performs the restricted reduction
    ///    `{0, ..., n - 1} -> Z/nZ`
    ///  - `from_positive_representative_bounded`: a function that performs the restricted reduction
    ///    `{0, ..., B - 1} -> Z/nZ`
    ///
    /// 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 is likely to take longer than the actual
    /// modular reduction.
    ///
    /// 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 numbers than necessary is used.
    /// Furthermore, if the integer rings used can represent some but not all positive numbers of a
    /// certain bitlength, there might be rare edge cases with panics/overflows.
    ///
    /// 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 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 integer rings `StaticRing::<ixx>::RING` are used, or if `B >=
    /// 2n`.
    #[stability::unstable(feature = "enable")]
    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
    where
        I: CanIsoFromTo<R::IntegerRingBase> + CanIsoFromTo<J>,
        F: FnOnce(El<R::IntegerRing>) -> R::Element,
        G: FnOnce(J::Element) -> R::Element,
    {
        let (neg, n) = if from.is_neg(&el) {
            (true, from.negate(el))
        } else {
            (false, el)
        };
        let ZZ = to.integer_ring().get_ring();
        let highbit_el = from.abs_highest_set_bit(&n).unwrap_or(0);

        let reduced = if highbit_el < hom.highbit_mod {
            from_positive_representative_exact(from.map_out(ZZ, n, &hom.iso))
        } else if highbit_el < hom.highbit_bound {
            from_positive_representative_bounded(from.map_out(to_large_int_ring, n, &hom.iso2))
        } else {
            from_positive_representative_exact(from.map_out(
                ZZ,
                from.euclidean_rem(n, &from.map_in_ref(ZZ, to.modulus(), &hom.hom)),
                &hom.iso,
            ))
        };
        if neg { to.negate(reduced) } else { reduced }
    }

    /// Generates a uniformly random element of `Z/nZ` using the randomness of `rng`.
    /// Designed to be used when implementing
    /// [`crate::rings::finite::FiniteRing::random_element()`].
    #[stability::unstable(feature = "enable")]
    pub fn random_element<R: ZnRing, G: FnMut() -> u64>(ring: &R, rng: G) -> R::Element {
        ring.map_in(
            ring.integer_ring().get_ring(),
            ring.integer_ring().get_uniformly_random(ring.modulus(), rng),
            &ring.has_canonical_hom(ring.integer_ring().get_ring()).unwrap(),
        )
    }

    /// Computes the checked division in `Z/nZ`. Designed to be used when implementing
    /// [`crate::divisibility::DivisibilityRing::checked_left_div()`].
    #[stability::unstable(feature = "enable")]
    pub fn checked_left_div<R: ZnRingStore>(ring: R, lhs: &El<R>, rhs: &El<R>) -> Option<El<R>>
    where
        R::Type: ZnRing,
    {
        if ring.is_zero(lhs) {
            return Some(ring.zero());
        }
        let int_ring = ring.integer_ring();
        let lhs_lift = ring.smallest_positive_lift(ring.clone_el(lhs));
        let rhs_lift = ring.smallest_positive_lift(ring.clone_el(rhs));
        let (s, _, d) = int_ring.extended_ideal_gen(&rhs_lift, ring.modulus());
        if let Some(quotient) = int_ring.checked_div(&lhs_lift, &d) {
            Some(ring.mul(ring.coerce(int_ring, quotient), ring.coerce(int_ring, s)))
        } else {
            None
        }
    }

    #[stability::unstable(feature = "enable")]
    pub fn checked_div_min<R: ZnRingStore>(ring: R, lhs: &El<R>, rhs: &El<R>) -> Option<El<R>>
    where
        R::Type: ZnRing,
    {
        if ring.is_zero(lhs) && ring.is_zero(rhs) {
            return Some(ring.one());
        }
        assert!(ring.is_noetherian());
        let int_ring = ring.integer_ring();
        let rhs_ann = int_ring
            .checked_div(
                ring.modulus(),
                &int_ring.ideal_gen(ring.modulus(), &ring.smallest_positive_lift(ring.clone_el(rhs))),
            )
            .unwrap();
        let some_sol = ring.smallest_positive_lift(ring.checked_div(lhs, rhs)?);
        let minimal_solution = int_ring.euclidean_rem(some_sol, &rhs_ann);
        if int_ring.is_zero(&minimal_solution) {
            return Some(ring.coerce(&int_ring, rhs_ann));
        } else {
            return Some(ring.coerce(&int_ring, minimal_solution));
        }
    }

    #[stability::unstable(feature = "enable")]
    pub fn interpolation_ring<R: ZnRingStore>(ring: R, count: usize) -> GaloisFieldOver<R>
    where
        R: Clone,
        R::Type: ZnRing + Field + SelfIso + CanHomFrom<StaticRingBase<i64>>,
    {
        let ZZbig = BigIntRing::RING;
        let modulus = int_cast(ring.integer_ring().clone_el(ring.modulus()), ZZbig, ring.integer_ring());
        let count = int_cast(count.try_into().unwrap(), ZZbig, StaticRing::<i64>::RING);
        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) {
                1
            } else {
                -1
            }
        }) + 1;
        assert!(degree >= 1);
        return GaloisField::new_with_convolution(ring, degree as usize, Global, STANDARD_CONVOLUTION);
    }
}

/// The [`crate::ring::RingStore`] corresponding to [`ZnRing`].
pub trait ZnRingStore: FiniteRingStore
where
    Self::Type: ZnRing,
{
    delegate! { ZnRing, fn integer_ring(&self) -> &<Self::Type as ZnRing>::IntegerRing }
    delegate! { ZnRing, fn modulus(&self) -> &El<<Self::Type as ZnRing>::IntegerRing> }
    delegate! { ZnRing, fn smallest_positive_lift(&self, el: El<Self>) -> El<<Self::Type as ZnRing>::IntegerRing> }
    delegate! { ZnRing, fn smallest_lift(&self, el: El<Self>) -> El<<Self::Type as ZnRing>::IntegerRing> }
    delegate! { ZnRing, fn any_lift(&self, el: El<Self>) -> El<<Self::Type as ZnRing>::IntegerRing> }
    delegate! { ZnRing, fn is_field(&self) -> bool }

    fn as_field(self) -> Result<RingValue<AsFieldBase<Self>>, Self>
    where
        Self: Sized,
    {
        if self.is_field() {
            Ok(RingValue::from(AsFieldBase::promise_is_perfect_field(self)))
        } else {
            Err(self)
        }
    }
}

impl<R: RingStore> ZnRingStore for R where R::Type: ZnRing {}

/// Trait for algorithms that require some implementation of
/// `Z/nZ`, but do not care which.
///
/// See [`choose_zn_impl()`] for details.
pub trait ZnOperation {
    type Output<'a>
    where
        Self: 'a;

    fn call<'a, R>(self, ring: R) -> Self::Output<'a>
    where
        Self: 'a,
        R: 'a + RingStore + Send + Sync,
        R::Type: ZnRing,
        El<R>: Send;
}

/// Calls the given function with some implementation of the ring
/// `Z/nZ`, chosen depending on `n` to provide best performance.
///
/// It is currently necessary to write all the boilerplate code that
/// comes with manually implementing [`ZnOperation`]. I experimented with
/// macros, but currently something simple seems like the best solution.
///
/// # Example
/// ```rust
/// # use feanor_math::ring::*;
/// # use feanor_math::homomorphism::*;
/// # use feanor_math::rings::zn::*;
/// # use feanor_math::primitive_int::*;
/// # use feanor_math::integer::*;
/// # use feanor_math::assert_el_eq;
///
/// let int_value = 4;
/// // work in Z/17Z without explicitly choosing an implementation
/// struct DoStuff {
///     int_value: i64,
/// }
/// impl ZnOperation for DoStuff {
///     type Output<'a>
///         = ()
///     where
///         Self: 'a;
///
///     fn call<'a, R>(self, Zn: R) -> ()
///     where
///         Self: 'a,
///         R: 'a + RingStore,
///         R::Type: ZnRing,
///     {
///         let value = Zn.coerce(
///             Zn.integer_ring(),
///             int_cast(self.int_value, Zn.integer_ring(), &StaticRing::<i64>::RING),
///         );
///         assert_el_eq!(Zn, Zn.int_hom().map(-1), Zn.mul_ref(&value, &value));
///     }
/// }
/// choose_zn_impl(StaticRing::<i64>::RING, 17, DoStuff { int_value });
/// ```
pub fn choose_zn_impl<'a, I, F>(ZZ: I, n: El<I>, f: F) -> F::Output<'a>
where
    I: 'a + RingStore,
    I::Type: IntegerRing,
    F: ZnOperation,
{
    if ZZ.abs_highest_set_bit(&n).unwrap_or(0) < 57 {
        f.call(zn_64::Zn::new(StaticRing::<i64>::RING.coerce(&ZZ, n) as u64))
    } else {
        f.call(zn_big::Zn::new(BigIntRing::RING, int_cast(n, &BigIntRing::RING, &ZZ)))
    }
}

#[test]
fn test_choose_zn_impl() {
    let int_value = 4;
    // work in Z/17Z without explicitly choosing an implementation
    struct DoStuff {
        int_value: i64,
    }
    impl ZnOperation for DoStuff {
        type Output<'a>
            = ()
        where
            Self: 'a;

        fn call<'a, R>(self, Zn: R)
        where
            R: 'a + RingStore,
            R::Type: ZnRing,
        {
            let value = Zn.coerce(
                Zn.integer_ring(),
                int_cast(self.int_value, Zn.integer_ring(), &StaticRing::<i64>::RING),
            );
            assert_el_eq!(Zn, Zn.int_hom().map(-1), Zn.mul_ref(&value, &value));
        }
    }
    choose_zn_impl(StaticRing::<i64>::RING, 17, DoStuff { int_value });
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum ReductionMapRequirements {
    SmallestLift,
    ExplicitReduce,
}

/// The homomorphism `Z/nZ -> Z/mZ` that exists whenever `m | n`. In
/// addition to the map, this also provides a function [`ZnReductionMap::smallest_lift()`]
/// that computes the "smallest" preimage under the map, and a function
/// [`ZnReductionMap::mul_quotient_fraction()`], that computes the multiplication
/// with `n/m` while also changing from `Z/mZ` to `Z/nZ`. This is very
/// useful in many number theoretic applications, where one often has to switch
/// between `Z/nZ` and `Z/mZ`.
///
/// Furthermore, many implementations of `ZnRing` currently do not support
/// [`CanHomFrom`]-homomorphisms when the moduli are different (but divide each
/// other).
pub struct ZnReductionMap<R, S>
where
    R: RingStore,
    R::Type: ZnRing,
    S: RingStore,
    S::Type: ZnRing,
{
    from: R,
    to: S,
    fraction_of_quotients: El<R>,
    to_modulus: El<<R::Type as ZnRing>::IntegerRing>,
    to_from_int: <S::Type as CanHomFrom<<S::Type as ZnRing>::IntegerRingBase>>::Homomorphism,
    from_from_int: <R::Type as CanHomFrom<<R::Type as ZnRing>::IntegerRingBase>>::Homomorphism,
    map_forward_requirement: ReductionMapRequirements,
}

impl<R, S> ZnReductionMap<R, S>
where
    R: RingStore,
    R::Type: ZnRing,
    S: RingStore,
    S::Type: ZnRing,
{
    pub fn new(from: R, to: S) -> Option<Self> {
        let from_char = from.characteristic(&BigIntRing::RING).unwrap();
        let to_char = to.characteristic(&BigIntRing::RING).unwrap();
        if let Some(frac) = BigIntRing::RING.checked_div(&from_char, &to_char) {
            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()),
                    )
                {
                    ReductionMapRequirements::SmallestLift
                } else {
                    ReductionMapRequirements::ExplicitReduce
                };
            Some(Self {
                map_forward_requirement,
                to_modulus: int_cast(
                    to.integer_ring().clone_el(to.modulus()),
                    from.integer_ring(),
                    to.integer_ring(),
                ),
                to_from_int: to.get_ring().has_canonical_hom(to.integer_ring().get_ring()).unwrap(),
                from_from_int: from
                    .get_ring()
                    .has_canonical_hom(from.integer_ring().get_ring())
                    .unwrap(),
                fraction_of_quotients: from.can_hom(from.integer_ring()).unwrap().map(int_cast(
                    frac,
                    from.integer_ring(),
                    BigIntRing::RING,
                )),
                from,
                to,
            })
        } else {
            None
        }
    }

    /// Computes the additive group homomorphism `Z/mZ -> Z/nZ, x -> (n/m)x`.
    ///
    /// # Example
    /// ```rust
    /// # use feanor_math::assert_el_eq;
    /// # use feanor_math::ring::*;
    /// # use feanor_math::homomorphism::*;
    /// # use feanor_math::rings::zn::*;
    /// # use feanor_math::rings::zn::zn_64::*;
    /// let Z5 = Zn::new(5);
    /// let Z25 = Zn::new(25);
    /// let f = ZnReductionMap::new(&Z25, &Z5).unwrap();
    /// assert_el_eq!(
    ///     Z25,
    ///     Z25.int_hom().map(15),
    ///     f.mul_quotient_fraction(Z5.int_hom().map(3))
    /// );
    /// ```
    pub fn mul_quotient_fraction(&self, x: El<S>) -> El<R> {
        self.from.mul_ref_snd(self.any_preimage(x), &self.fraction_of_quotients)
    }

    /// Computes the smallest preimage under the reduction map `Z/nZ -> Z/mZ`, where
    /// "smallest" refers to the element that has the smallest lift to `Z`.
    ///
    /// # Example
    /// ```rust
    /// # use feanor_math::assert_el_eq;
    /// # use feanor_math::ring::*;
    /// # use feanor_math::homomorphism::*;
    /// # use feanor_math::rings::zn::*;
    /// # use feanor_math::rings::zn::zn_64::*;
    /// let Z5 = Zn::new(5);
    /// let Z25 = Zn::new(25);
    /// let f = ZnReductionMap::new(&Z25, &Z5).unwrap();
    /// assert_el_eq!(
    ///     Z25,
    ///     Z25.int_hom().map(-2),
    ///     f.smallest_lift(Z5.int_hom().map(3))
    /// );
    /// ```
    pub fn smallest_lift(&self, x: El<S>) -> El<R> {
        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,
        )
    }

    pub fn any_preimage(&self, x: El<S>) -> El<R> {
        // the problem is that we don't know if `to.any_lift(x)` will fit into
        // `from.integer_ring()`; furthermore, profiling indicates that it won't help a lot
        // anyway, since taking the smallest lift now will usually make reduction cheaper
        // later
        self.smallest_lift(x)
    }

    pub fn smallest_lift_ref(&self, x: &El<S>) -> El<R> { self.smallest_lift(self.codomain().clone_el(x)) }
}

impl<R, S> Homomorphism<R::Type, S::Type> for ZnReductionMap<R, S>
where
    R: RingStore,
    R::Type: ZnRing,
    S: RingStore,
    S::Type: ZnRing,
{
    type CodomainStore = S;
    type DomainStore = R;

    fn map(&self, x: El<R>) -> El<S> {
        let value = match self.map_forward_requirement {
            ReductionMapRequirements::SmallestLift => self.from.smallest_lift(x),
            ReductionMapRequirements::ExplicitReduce => self
                .from
                .integer_ring()
                .euclidean_rem(self.from.any_lift(x), &self.to_modulus),
        };
        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,
        )
    }

    fn codomain(&self) -> &Self::CodomainStore { &self.to }

    fn domain(&self) -> &Self::DomainStore { &self.from }
}

#[cfg(any(test, feature = "generic_tests"))]
pub mod generic_tests {

    use super::*;
    use crate::primitive_int::{StaticRing, StaticRingBase};

    pub fn test_zn_axioms<R: RingStore>(R: R)
    where
        R::Type: ZnRing,
        <R::Type as ZnRing>::IntegerRingBase: CanIsoFromTo<StaticRingBase<i128>> + CanIsoFromTo<StaticRingBase<i32>>,
    {
        let ZZ = R.integer_ring();
        let n = R.modulus();

        assert!(R.is_zero(&R.coerce(ZZ, ZZ.clone_el(n))));
        assert!(R.is_field() == algorithms::miller_rabin::is_prime(ZZ, n, 10));

        let mut k = ZZ.one();
        while ZZ.is_lt(&k, &n) {
            assert!(!R.is_zero(&R.coerce(ZZ, ZZ.clone_el(&k))));
            ZZ.add_assign(&mut k, ZZ.one());
        }

        let all_elements = R.elements().collect::<Vec<_>>();
        assert_eq!(
            int_cast(ZZ.clone_el(n), &StaticRing::<i128>::RING, &ZZ) as usize,
            all_elements.len()
        );
        for (i, x) in all_elements.iter().enumerate() {
            for (j, y) in all_elements.iter().enumerate() {
                assert!(i == j || !R.eq_el(x, y));
            }
        }
    }

    pub fn test_map_in_large_int<R: RingStore>(R: R)
    where
        <R as RingStore>::Type: ZnRing + CanHomFrom<BigIntRingBase>,
    {
        let ZZ_big = BigIntRing::RING;
        let n = ZZ_big.power_of_two(1000);
        let x = R.coerce(&ZZ_big, n);
        assert!(R.eq_el(&R.pow(R.int_hom().map(2), 1000), &x));
    }
}

#[test]
fn test_reduction_map_large_value() {
    let ring1 = zn_64::Zn::new(1 << 42);
    let ring2 = zn_big::Zn::new(BigIntRing::RING, BigIntRing::RING.power_of_two(666));
    let reduce = ZnReductionMap::new(&ring2, ring1).unwrap();
    assert_el_eq!(ring1, ring1.zero(), reduce.map(ring2.pow(ring2.int_hom().map(2), 665)));
}

#[test]
fn test_reduction_map() {
    let ring1 = zn_64::Zn::new(257);
    let ring2 = zn_big::Zn::new(StaticRing::<i128>::RING, 257 * 7);

    crate::homomorphism::generic_tests::test_homomorphism_axioms(
        ZnReductionMap::new(&ring2, &ring1).unwrap(),
        ring2.elements().step_by(8),
    );

    let ring1 = zn_big::Zn::new(StaticRing::<i16>::RING, 3);
    let ring2 = zn_big::Zn::new(BigIntRing::RING, BigIntRing::RING.int_hom().map(65537 * 3));

    crate::homomorphism::generic_tests::test_homomorphism_axioms(
        ZnReductionMap::new(&ring2, &ring1).unwrap(),
        ring2.elements().step_by(1024),
    );
}

#[test]
fn test_generic_impl_checked_div_min() {
    let ring = zn_64::Zn::new(5 * 7 * 11 * 13);
    let actual = ring.annihilator(&ring.int_hom().map(1001));
    let expected = ring.int_hom().map(5);
    assert!(ring.checked_div(&expected, &actual).is_some());
    assert!(ring.checked_div(&actual, &expected).is_some());

    let actual = ring.annihilator(&ring.zero());
    let expected = ring.one();
    assert!(ring.checked_div(&expected, &actual).is_some());
    assert!(ring.checked_div(&actual, &expected).is_some());
}