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    ///
11    /// For a modulus with leading zeros, this method is more efficient than a naive sum of products.
12    ///
13    /// All terms must be associated with equivalent `MontyParams`.
14    ///
15    /// # Panics
16    /// - if `products` is empty.
17    #[must_use]
18    pub fn lincomb_vartime(products: &[(&Self, &Self)]) -> Self {
19        assert!(!products.is_empty(), "empty products");
20        let params = &products[0].0.params;
21        Self {
22            montgomery_form: lincomb_boxed_monty_form(
23                products,
24                params.modulus(),
25                params.mod_neg_inv(),
26                params.mod_leading_zeros(),
27            ),
28            params: products[0].0.params.clone(),
29        }
30    }
31}
32
33#[cfg(test)]
34mod tests {
35
36    #[cfg(feature = "rand_core")]
37    #[test]
38    fn lincomb_expected() {
39        use crate::modular::{BoxedMontyForm, BoxedMontyParams};
40        use crate::{BoxedUint, Odd, RandomMod};
41        use rand_core::SeedableRng;
42
43        const SIZE: u32 = 511;
44
45        let mut rng = chacha20::ChaCha8Rng::seed_from_u64(1);
46        for n in 0..100 {
47            let modulus = Odd::<BoxedUint>::random(&mut rng, SIZE);
48            let params = BoxedMontyParams::new(modulus.clone());
49            let a = BoxedUint::random_mod_vartime(&mut rng, modulus.as_nz_ref());
50            let b = BoxedUint::random_mod_vartime(&mut rng, modulus.as_nz_ref());
51            let c = BoxedUint::random_mod_vartime(&mut rng, modulus.as_nz_ref());
52            let d = BoxedUint::random_mod_vartime(&mut rng, modulus.as_nz_ref());
53            let e = BoxedUint::random_mod_vartime(&mut rng, modulus.as_nz_ref());
54            let f = BoxedUint::random_mod_vartime(&mut rng, modulus.as_nz_ref());
55
56            let std = a
57                .mul_mod(&b, modulus.as_nz_ref())
58                .add_mod(&c.mul_mod(&d, modulus.as_nz_ref()), modulus.as_nz_ref())
59                .add_mod(&e.mul_mod(&f, modulus.as_nz_ref()), modulus.as_nz_ref());
60
61            let lincomb = BoxedMontyForm::lincomb_vartime(&[
62                (
63                    &BoxedMontyForm::new(a, &params),
64                    &BoxedMontyForm::new(b, &params),
65                ),
66                (
67                    &BoxedMontyForm::new(c, &params),
68                    &BoxedMontyForm::new(d, &params),
69                ),
70                (
71                    &BoxedMontyForm::new(e, &params),
72                    &BoxedMontyForm::new(f, &params),
73                ),
74            ]);
75
76            assert_eq!(std, lincomb.retrieve(), "n={n}");
77        }
78    }
79}
crypto_bigint/modular/boxed_monty_form/lincomb.rs

crypto_bigint/modular/boxed_monty_form/
lincomb.rs
