crypto_bigint/modular/const_monty_form/
lincomb.rs

1//! Linear combinations of integers n Montgomery form with a constant modulus.
2
3use core::marker::PhantomData;
4
5use super::{ConstMontyForm, ConstMontyParams};
6use crate::modular::lincomb::lincomb_const_monty_form;
7
8impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> ConstMontyForm<MOD, LIMBS> {
9    /// Calculate the sum of products of pairs `(a, b)` in `products`.
10    ///
11    /// This method is variable time only with the value of the modulus.
12    /// For a modulus with leading zeros, this method is more efficient than a naive sum of products.
13    pub const fn lincomb_vartime(products: &[(Self, Self)]) -> Self {
14        Self {
15            montgomery_form: lincomb_const_monty_form(products, &MOD::MODULUS, MOD::MOD_NEG_INV),
16            phantom: PhantomData,
17        }
18    }
19}
20
21#[cfg(test)]
22mod tests {
23
24    #[cfg(feature = "rand")]
25    #[test]
26    fn lincomb_expected() {
27        use super::{ConstMontyForm, ConstMontyParams};
28        use crate::{impl_modulus, RandomMod, U256};
29        use rand_core::SeedableRng;
30        impl_modulus!(
31            P,
32            U256,
33            "7fffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551"
34        );
35        let modulus = P::MODULUS.as_nz_ref();
36
37        let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(1);
38        for n in 0..1000 {
39            let a = U256::random_mod(&mut rng, modulus);
40            let b = U256::random_mod(&mut rng, modulus);
41            let c = U256::random_mod(&mut rng, modulus);
42            let d = U256::random_mod(&mut rng, modulus);
43            let e = U256::random_mod(&mut rng, modulus);
44            let f = U256::random_mod(&mut rng, modulus);
45
46            assert_eq!(
47                a.mul_mod(&b, modulus)
48                    .add_mod(&c.mul_mod(&d, modulus), modulus)
49                    .add_mod(&e.mul_mod(&f, modulus), modulus),
50                ConstMontyForm::<P, { P::LIMBS }>::lincomb_vartime(&[
51                    (ConstMontyForm::new(&a), ConstMontyForm::new(&b)),
52                    (ConstMontyForm::new(&c), ConstMontyForm::new(&d)),
53                    (ConstMontyForm::new(&e), ConstMontyForm::new(&f)),
54                ])
55                .retrieve(),
56                "n={n}"
57            )
58        }
59    }
60}
crypto_bigint/modular/const_monty_form/lincomb.rs

crypto_bigint/modular/const_monty_form/
lincomb.rs
