zinc_utils/field/
monty.rs

1use crypto_primitives::{
2    FromWithConfig, IntoWithConfig, PrimeField, crypto_bigint_monty::MontyField,
3    crypto_bigint_uint::Uint,
4};
5use std::ops::MulAssign;
6
7use crate::{
8    from_ref::FromRef, inner_transparent_field::InnerTransparentField, mul_by_scalar::MulByScalar,
9    projectable_to_field::ProjectableToField,
10};
11
12impl<const LIMBS: usize> MulByScalar<&Self> for MontyField<LIMBS> {
13    #[allow(clippy::arithmetic_side_effects)] // False alert
14    fn mul_by_scalar<const CHECK: bool>(&self, rhs: &Self) -> Option<Self> {
15        // Field operations cannot overflow
16        Some(self * rhs)
17    }
18}
19
20impl<const LIMBS: usize> FromRef<Self> for MontyField<LIMBS> {
21    fn from_ref(value: &Self) -> Self {
22        value.clone()
23    }
24}
25
26impl<T, const LIMBS: usize> ProjectableToField<MontyField<LIMBS>> for T
27where
28    MontyField<LIMBS>: for<'a> FromWithConfig<&'a T>,
29{
30    fn prepare_projection(
31        sampled_value: &MontyField<LIMBS>,
32    ) -> impl Fn(&Self) -> MontyField<LIMBS> + Send + Sync + 'static {
33        let config = sampled_value.cfg().clone();
34        move |value: &T| value.into_with_cfg(&config)
35    }
36}
37
38impl<const LIMBS: usize> InnerTransparentField for MontyField<LIMBS> {
39    fn add_inner(lhs: &Self::Inner, rhs: &Self::Inner, config: &Self::Config) -> Self::Inner {
40        Uint::new(
41            lhs.inner()
42                .add_mod(rhs.inner(), config.modulus().as_nz_ref()),
43        )
44    }
45
46    fn sub_inner(lhs: &Self::Inner, rhs: &Self::Inner, config: &Self::Config) -> Self::Inner {
47        Uint::new(
48            lhs.inner()
49                .sub_mod(rhs.inner(), config.modulus().as_nz_ref()),
50        )
51    }
52
53    fn mul_assign_by_inner(&mut self, rhs: &Self::Inner) {
54        let rhs: Self = Self::new_unchecked(*rhs, self.cfg());
55
56        self.mul_assign(rhs);
57    }
58}
59
60#[cfg(test)]
61#[allow(
62    clippy::arithmetic_side_effects,
63    clippy::cast_possible_truncation,
64    clippy::cast_possible_wrap
65)]
66mod prop_tests {
67    use crypto_bigint::U256;
68    use crypto_primitives::{
69        FromWithConfig, IntoWithConfig, PrimeField,
70        crypto_bigint_monty::{F256, MontyField},
71        crypto_bigint_uint::Uint,
72    };
73    use proptest::prelude::*;
74
75    use crate::inner_transparent_field::InnerTransparentField;
76
77    const LIMBS: usize = 4;
78    const MODULUS: &str = "00dca94d8a1ecce3b6e8755d8999787d0524d8ca1ea755e7af84fb646fa31f27";
79    type F = F256;
80
81    fn get_dyn_config(hex_modulus: &str) -> <MontyField<LIMBS> as PrimeField>::Config {
82        let modulus = Uint::new(
83            crypto_bigint::Uint::<LIMBS>::from_str_radix_vartime(hex_modulus, 16).unwrap(),
84        );
85        MontyField::make_cfg(&modulus).expect("Failed to create field config")
86    }
87
88    fn any_u128() -> impl Strategy<Value = u128> {
89        any::<u128>()
90    }
91    fn any_i128() -> impl Strategy<Value = i128> {
92        any::<i128>()
93    }
94    fn any_bool() -> impl Strategy<Value = bool> {
95        any::<bool>()
96    }
97
98    proptest! {
99        #[test]
100        #[cfg_attr(miri, ignore)] // long running
101        fn prop_from_unsigned_matches_sum_of_bits(x in any_u128()) {
102            let cfg = get_dyn_config(MODULUS);
103            let f: F = x.into_with_cfg(&cfg);
104            let mut acc: F = F::zero_with_cfg(&cfg);
105            for i in 0..128 {
106                if (x >> i) & 1 == 1 { acc += F::from_with_cfg(1u64, &cfg) * F::from_with_cfg(1u64 << i.min(63), &cfg); }
107            }
108            let u = Uint::<{ U256::LIMBS }>::from(x);
109            let g2: F = u.into_with_cfg(&cfg);
110            prop_assert_eq!(f, g2);
111        }
112
113        #[test]
114        #[cfg_attr(miri, ignore)] // long running
115        fn prop_from_signed_is_neg_of_abs_when_negative(x in any_i128()) {
116            let cfg = get_dyn_config(MODULUS);
117            let f: F = x.into_with_cfg(&cfg);
118            let abs = x.unsigned_abs();
119            let g_abs = abs.into_with_cfg(&cfg);
120            if x < 0 {
121                prop_assert_eq!(f + g_abs, F::zero_with_cfg(&cfg));
122            } else {
123                prop_assert_eq!(f, g_abs);
124            }
125        }
126
127        #[test]
128        #[cfg_attr(miri, ignore)] // long running
129        fn prop_from_bool_is_identity(b in any_bool()) {
130            let cfg = get_dyn_config(MODULUS);
131            let f: F = b.into_with_cfg(&cfg);
132            prop_assert_eq!(f, if b { F::one_with_cfg(&cfg) } else { F::zero_with_cfg(&cfg) });
133        }
134
135        #[test]
136        #[cfg_attr(miri, ignore)] // long running
137        fn prop_from_uint_roundtrip_through_uint(x in any_u128()) {
138            let cfg = get_dyn_config(MODULUS);
139            let u: Uint<LIMBS> = Uint::from(x);
140            let g_from_uint: F = u.into_with_cfg(&cfg);
141            let g_direct: F = x.into_with_cfg(&cfg);
142            prop_assert_eq!(g_from_uint, g_direct);
143        }
144
145        #[test]
146        #[cfg_attr(miri, ignore)] // long running
147        fn prop_inner_ops_match_normal_ops((x, y) in any::<(u128, u128)>()) {
148            let cfg = get_dyn_config(MODULUS);
149            let a: F = x.into_with_cfg(&cfg);
150            let b: F = y.into_with_cfg(&cfg);
151            prop_assert_eq!(F::add_inner(a.inner(), b.inner(), &cfg), (a.clone() + b.clone()).into_inner());
152            prop_assert_eq!(F::sub_inner(a.inner(), b.inner(), &cfg), (a.clone() - b.clone()).into_inner());
153
154            let mut res = a.clone();
155            res.mul_assign_by_inner(b.inner());
156            prop_assert_eq!(res, a * b);
157        }
158    }
159}
zinc_utils/field/monty.rs

zinc_utils/field/
monty.rs
