arcium-primitives 0.4.0

///////////////////////////////////////////////////////////////////////////////////////////////////
// Wide ops
///////////////////////////////////////////////////////////////////////////////////////////////////

use crate::algebra::{
    field::mersenne::{
        m107_ops::{M107AccRepr, M107MulAccRepr},
        Mersenne107,
    },
    ops::{AccReduce, DefaultDotProduct, IntoWide, MulAccReduce, ReduceWide},
};

impl IntoWide<M107MulAccRepr> for Mersenne107 {
    #[inline]
    fn to_wide(&self) -> M107MulAccRepr {
        M107MulAccRepr::new(self.0)
    }

    #[inline]
    fn zero_wide() -> M107MulAccRepr {
        M107MulAccRepr::zero()
    }
}

impl ReduceWide<M107MulAccRepr> for Mersenne107 {
    #[inline]
    fn reduce_mod_order(a: M107MulAccRepr) -> Self {
        Self(a.reduce())
    }
}

impl MulAccReduce for Mersenne107 {
    type WideType = M107MulAccRepr;

    #[inline]
    fn mul_acc(acc: &mut Self::WideType, a: Self, b: Self) {
        let tmp = M107MulAccRepr::mul(a.0, b.0);
        M107MulAccRepr::add_assign(acc, &tmp);
    }
}

impl MulAccReduce<Self, &Self> for Mersenne107 {
    type WideType = M107MulAccRepr;

    #[inline]
    fn mul_acc(acc: &mut Self::WideType, a: Self, b: &Self) {
        Self::mul_acc(acc, a, *b);
    }
}

impl MulAccReduce<&Self, Self> for Mersenne107 {
    type WideType = M107MulAccRepr;

    #[inline]
    fn mul_acc(acc: &mut Self::WideType, a: &Self, b: Self) {
        Self::mul_acc(acc, *a, b);
    }
}

impl MulAccReduce<&Self, &Self> for Mersenne107 {
    type WideType = M107MulAccRepr;

    #[inline]
    fn mul_acc(acc: &mut Self::WideType, a: &Self, b: &Self) {
        Self::mul_acc(acc, *a, *b);
    }
}

impl IntoWide<M107AccRepr> for Mersenne107 {
    #[inline]
    fn to_wide(&self) -> M107AccRepr {
        M107AccRepr::new(self.0)
    }

    #[inline]
    fn zero_wide() -> M107AccRepr {
        M107AccRepr::zero()
    }
}

impl ReduceWide<M107AccRepr> for Mersenne107 {
    #[inline]
    fn reduce_mod_order(a: M107AccRepr) -> Self {
        Self(a.reduce())
    }
}

impl AccReduce for Mersenne107 {
    type WideType = M107AccRepr;

    #[inline]
    fn acc(acc: &mut Self::WideType, a: Self) {
        M107AccRepr::add_assign(acc, &M107AccRepr::new(a.0));
    }
}

impl AccReduce<&Self> for Mersenne107 {
    type WideType = M107AccRepr;

    #[inline]
    fn acc(acc: &mut Self::WideType, a: &Self) {
        Self::acc(acc, *a);
    }
}

// -------------- Dot Product -------------- //

impl DefaultDotProduct for Mersenne107 {}
impl DefaultDotProduct<Self, &Self> for Mersenne107 {}
impl DefaultDotProduct<&Self, &Self> for Mersenne107 {}
impl DefaultDotProduct<&Self, Self> for Mersenne107 {}

#[cfg(test)]
mod test {
    use std::iter::Sum;

    use ff::Field;
    use num_bigint::BigInt;
    use num_traits::Zero;
    use rand::Rng;
    use typenum::Unsigned;

    use crate::{
        algebra::{
            field::{
                mersenne::{
                    m107::Mersenne107,
                    m107_ops::{M107AccRepr, M107MulAccRepr},
                    test::bigint_to_m107,
                },
                FieldExtension,
            },
            ops::{AccReduce, DotProduct, MulAccReduce, ReduceWide},
        },
        izip_eq,
        random::test_rng,
        types::{HeapArray, Positive},
    };

    type M = typenum::U1000;

    #[test]
    fn test_mul_acc_repr_to() {
        fn test_internal(a: u128) {
            let a_red_true = bigint_to_m107(BigInt::from(a));
            let tmp = M107MulAccRepr::new(a);
            let a_red_actual = bigint_to_m107(tmp.to_bigint());
            assert_eq!(a_red_true, a_red_actual, "a = {a:?}");
        }

        // Random values test
        let mut rng = test_rng();
        for _ in 0..M::to_usize() {
            let a = rng.gen::<u128>();
            test_internal(a);
        }

        // Corner cases
        test_internal(0);
        test_internal(Mersenne107::MAX);
        test_internal(Mersenne107::MODULUS);
        test_internal(0xffffffffffffffffffffffffffffffff);
    }

    #[test]
    fn test_mul_acc_repr_to_and_from() {
        fn test_internal(val: Mersenne107) {
            let val_wide = <Mersenne107 as MulAccReduce>::to_wide(&val);
            let act = Mersenne107::reduce_mod_order(val_wide);
            assert_eq!(val, act, "val = {val:?}");
        }

        let mut rng = test_rng();
        for _ in 0..M::to_usize() {
            let a = Mersenne107::random(&mut rng);
            test_internal(a);
        }

        // Corner cases
        test_internal(Mersenne107::ZERO);
        test_internal(Mersenne107::ONE);
        test_internal(Mersenne107(Mersenne107::MAX));
    }

    #[test]
    fn test_mul_acc_repr_dot_product() {
        fn bigint_dot(
            a: impl ExactSizeIterator<Item = Mersenne107>,
            b: impl ExactSizeIterator<Item = Mersenne107>,
        ) -> Mersenne107 {
            let tmp = izip_eq!(a, b).fold(BigInt::zero(), |mut acc, (a, b)| {
                acc += BigInt::from(a.0) * BigInt::from(b.0);
                acc % BigInt::from(Mersenne107::MODULUS)
            });
            bigint_to_m107(tmp)
        }

        fn test_internal<N: Positive>(a: HeapArray<Mersenne107, N>, b: HeapArray<Mersenne107, N>) {
            let exp = bigint_dot(a.iter().copied(), b.iter().copied());
            let act = Mersenne107::dot(a, b);
            assert_eq!(exp, act);
        }

        let mut rng = test_rng();
        for _ in 0..M::to_usize() {
            let a = Mersenne107::random_elements::<typenum::U13>(&mut rng);
            let b = Mersenne107::random_elements(&mut rng);
            test_internal(a, b);
        }

        // Corner cases
        // Dot-product of empty iterators should return zero
        assert_eq!(
            Mersenne107::ZERO,
            Mersenne107::dot(
                std::iter::empty::<Mersenne107>(),
                std::iter::empty::<Mersenne107>()
            )
        );
        let a = Mersenne107::random(&mut rng);
        let b = Mersenne107::random(&mut rng);

        assert_eq!(
            a * b,
            Mersenne107::dot(std::iter::once(a), std::iter::once(b))
        );
        assert_eq!(
            a,
            Mersenne107::dot(std::iter::once(a), std::iter::once(Mersenne107::ONE))
        );
        assert_eq!(
            Mersenne107::ZERO,
            Mersenne107::dot(std::iter::once(a), std::iter::once(Mersenne107::ZERO))
        );
    }

    #[test]
    fn test_acc_repr_to() {
        fn test_internal(a: u128) {
            let a_red_true = bigint_to_m107(BigInt::from(a));
            let tmp = M107AccRepr::new(a);
            let a_red_actual = bigint_to_m107(tmp.to_bigint());
            assert_eq!(a_red_true, a_red_actual, "a = {a:?}");
        }

        // Random values test
        let mut rng = test_rng();
        for _ in 0..M::to_usize() {
            let a = rng.gen::<u128>();
            test_internal(a);
        }

        // Corner cases
        test_internal(0);
        test_internal(Mersenne107::MAX);
        test_internal(Mersenne107::MODULUS);
        test_internal(0xffffffffffffffffffffffffffffffff);
    }

    #[test]
    fn test_acc_repr_to_and_from() {
        fn test_internal(val: Mersenne107) {
            let val_wide = <Mersenne107 as AccReduce>::to_wide(&val);
            let act = Mersenne107::reduce_mod_order(val_wide);
            assert_eq!(val, act, "val = {val:?}");
        }

        let mut rng = test_rng();
        for _ in 0..M::to_usize() {
            let a = Mersenne107::random(&mut rng);
            test_internal(a);
        }

        // Corner cases
        test_internal(Mersenne107::ZERO);
        test_internal(Mersenne107::ONE);
        test_internal(Mersenne107(Mersenne107::MAX));
    }

    #[test]
    fn test_acc_repr_sum() {
        fn bigint_sum(a: impl ExactSizeIterator<Item = Mersenne107>) -> Mersenne107 {
            let tmp = a.into_iter().fold(BigInt::zero(), |mut acc, a| {
                acc += BigInt::from(a.0);
                acc % BigInt::from(Mersenne107::MODULUS)
            });
            bigint_to_m107(tmp)
        }

        fn test_internal<N: Positive>(a: HeapArray<Mersenne107, N>) {
            let exp = bigint_sum(a.iter().copied());
            let act = Mersenne107::sum(a.into_iter());
            assert_eq!(exp, act);
        }

        let mut rng = test_rng();
        for _ in 0..M::to_usize() {
            let a = Mersenne107::random_elements::<typenum::U131>(&mut rng);
            test_internal(a);
        }

        // Corner cases
        // Dot-product of empty iterators should return zero
        assert_eq!(
            Mersenne107::ZERO,
            Mersenne107::sum(std::iter::empty::<Mersenne107>())
        );
        let a = Mersenne107::random(&mut rng);
        let b = Mersenne107::random(&mut rng);

        assert_eq!(a, Mersenne107::sum(std::iter::once(a)));
        assert_eq!(
            a + b,
            Mersenne107::sum(std::iter::once(a).chain(std::iter::once(b)))
        );
    }
}