crypto_bigint/modular/fixed_monty_form/
lincomb.rs

1//! Linear combinations of integers in Montgomery form with a modulus set at runtime.
2
3use super::FixedMontyForm;
4use crate::modular::lincomb::lincomb_monty_form;
5
6impl<const LIMBS: usize> FixedMontyForm<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    ///
15    /// # Panics
16    /// - if `products` is empty.
17    #[must_use]
18    #[track_caller]
19    pub const fn lincomb_vartime(products: &[(&Self, &Self)]) -> Self {
20        assert!(!products.is_empty(), "empty products");
21        let params = &products[0].0.params;
22        Self {
23            montgomery_form: lincomb_monty_form(
24                products,
25                &params.modulus,
26                params.mod_neg_inv(),
27                params.mod_leading_zeros,
28            ),
29            params: products[0].0.params,
30        }
31    }
32}
33
34#[cfg(test)]
35mod tests {
36    #[cfg(feature = "rand_core")]
37    #[test]
38    fn lincomb_expected() {
39        use crate::U256;
40        use crate::{
41            Odd, Random, RandomMod,
42            modular::{FixedMontyForm, FixedMontyParams},
43        };
44        use rand_core::SeedableRng;
45
46        let mut rng = chacha20::ChaCha8Rng::seed_from_u64(1);
47        for n in 0..1500 {
48            let modulus = Odd::<U256>::random_from_rng(&mut rng);
49            let params = FixedMontyParams::new_vartime(modulus);
50            let m = modulus.as_nz_ref();
51            let a = U256::random_mod_vartime(&mut rng, m);
52            let b = U256::random_mod_vartime(&mut rng, m);
53            let c = U256::random_mod_vartime(&mut rng, m);
54            let d = U256::random_mod_vartime(&mut rng, m);
55
56            assert_eq!(
57                a.mul_mod(&b, m).add_mod(&c.mul_mod(&d, m), m),
58                FixedMontyForm::lincomb_vartime(&[
59                    (
60                        &FixedMontyForm::new(&a, &params),
61                        &FixedMontyForm::new(&b, &params)
62                    ),
63                    (
64                        &FixedMontyForm::new(&c, &params),
65                        &FixedMontyForm::new(&d, &params)
66                    ),
67                ])
68                .retrieve(),
69                "n={n}, a={a}, b={b}, c={c}, d={d}"
70            );
71        }
72    }
73}
crypto_bigint/modular/fixed_monty_form/lincomb.rs

crypto_bigint/modular/fixed_monty_form/
lincomb.rs
