crypto_bigint/modular/fixed_monty_form/
mul.rs

1//! Multiplications between integers in Montgomery form with a modulus set at runtime.
2
3use super::FixedMontyForm;
4use crate::modular::mul::almost_montgomery_mul;
5use crate::prelude::AmmMultiplier;
6use crate::{
7    MontyMultiplier, Square, SquareAssign, Uint,
8    modular::{
9        FixedMontyParams,
10        mul::{mul_montgomery_form, square_montgomery_form, square_repeat_montgomery_form},
11    },
12};
13use core::ops::{Mul, MulAssign};
14
15impl<const LIMBS: usize> FixedMontyForm<LIMBS> {
16    /// Multiplies by `rhs`.
17    #[must_use]
18    pub const fn mul(&self, rhs: &Self) -> Self {
19        Self {
20            montgomery_form: mul_montgomery_form(
21                &self.montgomery_form,
22                &rhs.montgomery_form,
23                &self.params.modulus,
24                self.params.mod_neg_inv(),
25            ),
26            params: self.params,
27        }
28    }
29
30    /// Computes the (reduced) square.
31    #[must_use]
32    pub const fn square(&self) -> Self {
33        Self {
34            montgomery_form: square_montgomery_form(
35                &self.montgomery_form,
36                &self.params.modulus,
37                self.params.mod_neg_inv(),
38            ),
39            params: self.params,
40        }
41    }
42
43    /// Computes the reduced product `self^2n`.
44    ///
45    /// This method is variable time in `n` only.
46    #[must_use]
47    pub const fn square_repeat_vartime(&self, n: u32) -> Self {
48        Self {
49            montgomery_form: square_repeat_montgomery_form::<LIMBS>(
50                &self.montgomery_form,
51                n,
52                &self.params.modulus,
53                self.params.mod_neg_inv(),
54            ),
55            params: self.params,
56        }
57    }
58}
59
60impl<const LIMBS: usize> Mul<&FixedMontyForm<LIMBS>> for &FixedMontyForm<LIMBS> {
61    type Output = FixedMontyForm<LIMBS>;
62    fn mul(self, rhs: &FixedMontyForm<LIMBS>) -> FixedMontyForm<LIMBS> {
63        debug_assert_eq!(self.params, rhs.params);
64        self.mul(rhs)
65    }
66}
67
68impl<const LIMBS: usize> Mul<FixedMontyForm<LIMBS>> for &FixedMontyForm<LIMBS> {
69    type Output = FixedMontyForm<LIMBS>;
70    #[allow(clippy::op_ref)]
71    fn mul(self, rhs: FixedMontyForm<LIMBS>) -> FixedMontyForm<LIMBS> {
72        self * &rhs
73    }
74}
75
76impl<const LIMBS: usize> Mul<&FixedMontyForm<LIMBS>> for FixedMontyForm<LIMBS> {
77    type Output = FixedMontyForm<LIMBS>;
78    #[allow(clippy::op_ref)]
79    fn mul(self, rhs: &FixedMontyForm<LIMBS>) -> FixedMontyForm<LIMBS> {
80        &self * rhs
81    }
82}
83
84impl<const LIMBS: usize> Mul<FixedMontyForm<LIMBS>> for FixedMontyForm<LIMBS> {
85    type Output = FixedMontyForm<LIMBS>;
86    fn mul(self, rhs: FixedMontyForm<LIMBS>) -> FixedMontyForm<LIMBS> {
87        &self * &rhs
88    }
89}
90
91impl<const LIMBS: usize> MulAssign<&FixedMontyForm<LIMBS>> for FixedMontyForm<LIMBS> {
92    fn mul_assign(&mut self, rhs: &FixedMontyForm<LIMBS>) {
93        *self = *self * rhs;
94    }
95}
96
97impl<const LIMBS: usize> MulAssign<FixedMontyForm<LIMBS>> for FixedMontyForm<LIMBS> {
98    fn mul_assign(&mut self, rhs: FixedMontyForm<LIMBS>) {
99        *self *= &rhs;
100    }
101}
102
103impl<const LIMBS: usize> Square for FixedMontyForm<LIMBS> {
104    fn square(&self) -> Self {
105        FixedMontyForm::square(self)
106    }
107}
108
109impl<const LIMBS: usize> SquareAssign for FixedMontyForm<LIMBS> {
110    fn square_assign(&mut self) {
111        *self = self.square();
112    }
113}
114
115#[derive(Debug, Clone, Copy)]
116pub struct FixedMontyMultiplier<'a, const LIMBS: usize>(&'a FixedMontyParams<LIMBS>);
117
118impl<'a, const LIMBS: usize> From<&'a FixedMontyParams<LIMBS>> for FixedMontyMultiplier<'a, LIMBS> {
119    fn from(source: &'a FixedMontyParams<LIMBS>) -> Self {
120        Self(source)
121    }
122}
123
124impl<'a, const LIMBS: usize> MontyMultiplier<'a> for FixedMontyMultiplier<'a, LIMBS> {
125    type Monty = FixedMontyForm<LIMBS>;
126
127    /// Performs a Montgomery multiplication, assigning a fully reduced result to `lhs`.
128    fn mul_assign(&mut self, lhs: &mut Self::Monty, rhs: &Self::Monty) {
129        let product = mul_montgomery_form(
130            &lhs.montgomery_form,
131            &rhs.montgomery_form,
132            &self.0.modulus,
133            self.0.mod_neg_inv(),
134        );
135        lhs.montgomery_form = product;
136    }
137
138    /// Performs a Montgomery squaring, assigning a fully reduced result to `lhs`.
139    fn square_assign(&mut self, lhs: &mut Self::Monty) {
140        let product =
141            square_montgomery_form(&lhs.montgomery_form, &self.0.modulus, self.0.mod_neg_inv());
142        lhs.montgomery_form = product;
143    }
144}
145
146impl<'a, const LIMBS: usize> AmmMultiplier<'a> for FixedMontyMultiplier<'a, LIMBS> {
147    /// Perform an "Almost Montgomery Multiplication", assigning the product to `a`.
148    ///
149    /// NOTE: the resulting output will be reduced to the *bit length* of the modulus, but not fully reduced and may
150    /// exceed the modulus. A final reduction is required to ensure AMM results are fully reduced, and should not be
151    /// exposed outside the internals of this crate.
152    fn mul_amm_assign(&mut self, a: &mut Uint<LIMBS>, b: &Uint<LIMBS>) {
153        let mut product = Uint::<LIMBS>::ZERO;
154        almost_montgomery_mul(
155            a.as_uint_ref(),
156            b.as_uint_ref(),
157            product.as_mut_uint_ref(),
158            self.0.modulus().as_uint_ref(),
159            self.0.mod_neg_inv(),
160        );
161        a.limbs.copy_from_slice(&product.limbs);
162    }
163
164    /// Perform a squaring using "Almost Montgomery Multiplication", assigning the result to `a`.
165    ///
166    /// NOTE: the resulting output will be reduced to the *bit length* of the modulus, but not fully reduced and may
167    /// exceed the modulus. A final reduction is required to ensure AMM results are fully reduced, and should not be
168    /// exposed outside the internals of this crate.
169    fn square_amm_assign(&mut self, a: &mut Uint<LIMBS>) {
170        let mut product = Uint::<LIMBS>::ZERO;
171        almost_montgomery_mul(
172            a.as_uint_ref(),
173            a.as_uint_ref(),
174            product.as_mut_uint_ref(),
175            self.0.modulus().as_uint_ref(),
176            self.0.mod_neg_inv(),
177        );
178        a.limbs.copy_from_slice(&product.limbs);
179    }
180}
181
182#[cfg(test)]
183mod tests {
184    use crate::{
185        Odd, U256,
186        modular::{FixedMontyForm, FixedMontyParams},
187    };
188
189    const PARAMS: FixedMontyParams<{ U256::LIMBS }> =
190        FixedMontyParams::new_vartime(Odd::<U256>::from_be_hex(
191            "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
192        ));
193    const N: U256 =
194        U256::from_be_hex("14117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
195    const N_MOD: FixedMontyForm<{ U256::LIMBS }> = FixedMontyForm::new(&N, &PARAMS);
196
197    #[test]
198    fn test_mul_zero() {
199        let res = N_MOD.mul(&FixedMontyForm::zero(&PARAMS));
200        let expected = U256::ZERO;
201        assert_eq!(res.retrieve(), expected);
202    }
203
204    #[test]
205    fn test_mul_one() {
206        let res = N_MOD.mul(&FixedMontyForm::one(&PARAMS));
207        assert_eq!(res.retrieve(), N);
208    }
209
210    #[test]
211    fn test_mul_eq_add() {
212        let res = N_MOD.mul(&FixedMontyForm::new(&U256::from(2u8), &PARAMS));
213        assert_eq!(res, N_MOD.add(&N_MOD));
214    }
215
216    #[test]
217    fn test_square_eq_mul() {
218        let res = N_MOD.square();
219        let expected = N_MOD.mul(&N_MOD);
220        assert_eq!(res, expected);
221    }
222
223    #[test]
224    fn test_square_repeat() {
225        let res = N_MOD.square_repeat_vartime(0);
226        assert_eq!(res, N_MOD);
227
228        let res = N_MOD.square_repeat_vartime(1);
229        assert_eq!(res, N_MOD.square());
230
231        let res = N_MOD.square_repeat_vartime(5);
232        let expected = N_MOD.square().square().square().square().square();
233        assert_eq!(res, expected);
234    }
235}
crypto_bigint/modular/fixed_monty_form/mul.rs

crypto_bigint/modular/fixed_monty_form/
mul.rs
