crypto_bigint/modular/boxed_monty_form/
lincomb.rs

1//! Linear combinations of integers in Montgomery form with a modulus set at runtime.
2
3use super::BoxedMontyForm;
4use crate::modular::lincomb::lincomb_boxed_monty_form;
5
6impl BoxedMontyForm {
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 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_boxed_monty_form(
19                products,
20                &params.modulus,
21                params.mod_neg_inv,
22                params.mod_leading_zeros,
23            ),
24            params: products[0].0.params.clone(),
25        }
26    }
27}
28
29#[cfg(test)]
30mod tests {
31
32    #[cfg(feature = "rand")]
33    #[test]
34    fn lincomb_expected() {
35        use crate::modular::{BoxedMontyForm, BoxedMontyParams};
36        use crate::{BoxedUint, Odd, RandomMod};
37        use rand_core::SeedableRng;
38
39        const SIZE: u32 = 511;
40
41        let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(1);
42        for n in 0..100 {
43            let modulus = Odd::<BoxedUint>::random(&mut rng, SIZE);
44            let params = BoxedMontyParams::new(modulus.clone());
45            let a = BoxedUint::random_mod(&mut rng, modulus.as_nz_ref());
46            let b = BoxedUint::random_mod(&mut rng, modulus.as_nz_ref());
47            let c = BoxedUint::random_mod(&mut rng, modulus.as_nz_ref());
48            let d = BoxedUint::random_mod(&mut rng, modulus.as_nz_ref());
49            let e = BoxedUint::random_mod(&mut rng, modulus.as_nz_ref());
50            let f = BoxedUint::random_mod(&mut rng, modulus.as_nz_ref());
51
52            let std = a
53                .mul_mod(&b, &modulus)
54                .add_mod(&c.mul_mod(&d, &modulus), &modulus)
55                .add_mod(&e.mul_mod(&f, &modulus), &modulus);
56
57            let lincomb = BoxedMontyForm::lincomb_vartime(&[
58                (
59                    &BoxedMontyForm::new(a, params.clone()),
60                    &BoxedMontyForm::new(b, params.clone()),
61                ),
62                (
63                    &BoxedMontyForm::new(c, params.clone()),
64                    &BoxedMontyForm::new(d, params.clone()),
65                ),
66                (
67                    &BoxedMontyForm::new(e, params.clone()),
68                    &BoxedMontyForm::new(f, params.clone()),
69                ),
70            ]);
71
72            assert_eq!(std, lincomb.retrieve(), "n={n}");
73        }
74    }
75}
crypto_bigint/modular/boxed_monty_form/lincomb.rs

crypto_bigint/modular/boxed_monty_form/
lincomb.rs
