crypto_bigint/modular/monty_form/
lincomb.rs

1//! Linear combinations of integers in Montgomery form with a modulus set at runtime.
2
3use super::MontyForm;
4use crate::modular::lincomb::lincomb_monty_form;
5
6impl<const LIMBS: usize> MontyForm<LIMBS> {
7    /// Calculate the sum of products of pairs `(a, b)` in `products`.
8    ///
9    /// This method is variable time only with the value of the modulus.
10    /// For a modulus with leading zeros, this method is more efficient than a naive sum of products.
11    ///
12    /// This method will panic if `products` is empty. All terms must be associated
13    /// with equivalent `MontyParams`.
14    pub const fn lincomb_vartime(products: &[(&Self, &Self)]) -> Self {
15        assert!(!products.is_empty(), "empty products");
16        let params = &products[0].0.params;
17        Self {
18            montgomery_form: lincomb_monty_form(
19                products,
20                &params.modulus,
21                params.mod_neg_inv,
22                params.mod_leading_zeros,
23            ),
24            params: products[0].0.params,
25        }
26    }
27}
28
29#[cfg(test)]
30mod tests {
31    #[cfg(feature = "rand")]
32    #[test]
33    fn lincomb_expected() {
34        use crate::U256;
35        use crate::{
36            modular::{MontyForm, MontyParams},
37            Odd, Random, RandomMod,
38        };
39        use rand_core::SeedableRng;
40
41        let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(1);
42        for n in 0..1500 {
43            let modulus = Odd::<U256>::random(&mut rng);
44            let params = MontyParams::new_vartime(modulus);
45            let m = modulus.as_nz_ref();
46            let a = U256::random_mod(&mut rng, m);
47            let b = U256::random_mod(&mut rng, m);
48            let c = U256::random_mod(&mut rng, m);
49            let d = U256::random_mod(&mut rng, m);
50
51            assert_eq!(
52                a.mul_mod(&b, m).add_mod(&c.mul_mod(&d, m), m),
53                MontyForm::lincomb_vartime(&[
54                    (&MontyForm::new(&a, params), &MontyForm::new(&b, params)),
55                    (&MontyForm::new(&c, params), &MontyForm::new(&d, params)),
56                ])
57                .retrieve(),
58                "n={n}, a={a}, b={b}, c={c}, d={d}"
59            )
60        }
61    }
62}
crypto_bigint/modular/monty_form/lincomb.rs

crypto_bigint/modular/monty_form/
lincomb.rs
