crypto_bigint/modular/const_monty_form/
pow.rs

1//! Exponentiation of integers in Montgomery form with a constant modulus.
2
3use super::{ConstMontyForm, ConstMontyParams};
4use crate::{
5    MultiExponentiateBoundedExp, PowBoundedExp, Uint,
6    modular::pow::{
7        multi_exponentiate_montgomery_form_array, pow_montgomery_form, pow_montgomery_form_amm,
8    },
9};
10
11#[cfg(feature = "alloc")]
12use {crate::modular::pow::multi_exponentiate_montgomery_form_slice, alloc::vec::Vec};
13
14impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> ConstMontyForm<MOD, LIMBS> {
15    /// Raises to the `exponent` power.
16    #[must_use]
17    pub const fn pow<const RHS_LIMBS: usize>(&self, exponent: &Uint<RHS_LIMBS>) -> Self {
18        self.pow_bounded_exp(exponent, Uint::<RHS_LIMBS>::BITS)
19    }
20
21    /// Raises to the `exponent` power,
22    /// with `exponent_bits` representing the number of (least significant) bits
23    /// to take into account for the exponent.
24    ///
25    /// NOTE: `exponent_bits` may be leaked in the time pattern.
26    #[must_use]
27    pub const fn pow_bounded_exp<const RHS_LIMBS: usize>(
28        &self,
29        exponent: &Uint<RHS_LIMBS>,
30        exponent_bits: u32,
31    ) -> Self {
32        Self {
33            montgomery_form: pow_montgomery_form::<LIMBS, RHS_LIMBS, false>(
34                &self.montgomery_form,
35                exponent,
36                exponent_bits,
37                &MOD::PARAMS,
38            ),
39            phantom: core::marker::PhantomData,
40        }
41    }
42
43    /// Raises to the `exponent` power.
44    ///
45    /// This method is variable time in `exponent`.
46    #[must_use]
47    pub const fn pow_vartime<const RHS_LIMBS: usize>(&self, exponent: &Uint<RHS_LIMBS>) -> Self {
48        let exponent_bits = exponent.bits_vartime();
49        Self {
50            montgomery_form: pow_montgomery_form::<LIMBS, RHS_LIMBS, true>(
51                &self.montgomery_form,
52                exponent,
53                exponent_bits,
54                &MOD::PARAMS,
55            ),
56            phantom: core::marker::PhantomData,
57        }
58    }
59
60    /// Raises to the `exponent` power using Almost Montgomery Multiplication (AMM).
61    #[must_use]
62    pub fn pow_amm(&self, exponent: &Uint<LIMBS>) -> Self {
63        self.pow_amm_bounded_exp(exponent, Uint::<LIMBS>::BITS)
64    }
65
66    /// Raises to the `exponent` power using Almost Montgomery Multiplication (AMM)
67    /// with `exponent_bits` representing the number of (least significant) bits
68    /// to take into account for the exponent.
69    ///
70    /// NOTE: `exponent_bits` may be leaked in the time pattern.
71    #[must_use]
72    pub fn pow_amm_bounded_exp(&self, exponent: &Uint<LIMBS>, exponent_bits: u32) -> Self {
73        Self {
74            montgomery_form: pow_montgomery_form_amm(
75                &self.montgomery_form,
76                exponent,
77                exponent_bits,
78                &MOD::PARAMS,
79            ),
80            phantom: core::marker::PhantomData,
81        }
82    }
83}
84
85impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize, const RHS_LIMBS: usize>
86    PowBoundedExp<Uint<RHS_LIMBS>> for ConstMontyForm<MOD, LIMBS>
87{
88    fn pow_bounded_exp(&self, exponent: &Uint<RHS_LIMBS>, exponent_bits: u32) -> Self {
89        self.pow_bounded_exp(exponent, exponent_bits)
90    }
91}
92
93impl<const N: usize, MOD: ConstMontyParams<LIMBS>, const LIMBS: usize, const RHS_LIMBS: usize>
94    MultiExponentiateBoundedExp<Uint<RHS_LIMBS>, [(Self, Uint<RHS_LIMBS>); N]>
95    for ConstMontyForm<MOD, LIMBS>
96{
97    fn multi_exponentiate_bounded_exp(
98        bases_and_exponents: &[(Self, Uint<RHS_LIMBS>); N],
99        exponent_bits: u32,
100    ) -> Self {
101        let mut bases_and_exponents_montgomery_form =
102            [(Uint::<LIMBS>::ZERO, Uint::<RHS_LIMBS>::ZERO); N];
103
104        let mut i = 0;
105        while i < N {
106            let (base, exponent) = bases_and_exponents[i];
107            bases_and_exponents_montgomery_form[i] = (base.montgomery_form, exponent);
108            i += 1;
109        }
110
111        Self {
112            montgomery_form: multi_exponentiate_montgomery_form_array::<LIMBS, RHS_LIMBS, N, false>(
113                &bases_and_exponents_montgomery_form,
114                exponent_bits,
115                &MOD::PARAMS,
116            ),
117            phantom: core::marker::PhantomData,
118        }
119    }
120}
121
122#[cfg(feature = "alloc")]
123impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize, const RHS_LIMBS: usize>
124    MultiExponentiateBoundedExp<Uint<RHS_LIMBS>, [(Self, Uint<RHS_LIMBS>)]>
125    for ConstMontyForm<MOD, LIMBS>
126{
127    fn multi_exponentiate_bounded_exp(
128        bases_and_exponents: &[(Self, Uint<RHS_LIMBS>)],
129        exponent_bits: u32,
130    ) -> Self {
131        let bases_and_exponents: Vec<(Uint<LIMBS>, Uint<RHS_LIMBS>)> = bases_and_exponents
132            .iter()
133            .map(|(base, exp)| (base.montgomery_form, *exp))
134            .collect();
135        Self {
136            montgomery_form: multi_exponentiate_montgomery_form_slice::<LIMBS, RHS_LIMBS, false>(
137                &bases_and_exponents,
138                exponent_bits,
139                &MOD::PARAMS,
140            ),
141            phantom: core::marker::PhantomData,
142        }
143    }
144}
145
146#[cfg(test)]
147mod tests {
148    use crate::traits::MultiExponentiate;
149    use crate::{
150        U256, const_monty_form, const_monty_params, modular::const_monty_form::ConstMontyParams,
151    };
152
153    const_monty_params!(
154        Modulus,
155        U256,
156        "9CC24C5DF431A864188AB905AC751B727C9447A8E99E6366E1AD78A21E8D882B"
157    );
158
159    const_monty_form!(Fe, Modulus);
160
161    #[test]
162    fn test_powmod_zero() {
163        let base = U256::from(105u64);
164        let base_mod = Fe::new(&base);
165
166        let res = base_mod.pow(&U256::ZERO);
167        let res_vartime = base_mod.pow_vartime(&U256::ZERO);
168
169        assert_eq!(res.retrieve(), U256::ONE);
170        assert_eq!(res_vartime.retrieve(), U256::ONE);
171    }
172
173    #[test]
174    fn test_powmod_small_base() {
175        let base = U256::from(105u64);
176        let base_mod = Fe::new(&base);
177
178        let exponent =
179            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
180
181        let res = base_mod.pow(&exponent);
182        let res_vartime = base_mod.pow_vartime(&exponent);
183
184        let expected =
185            U256::from_be_hex("7B2CD7BDDD96C271E6F232F2F415BB03FE2A90BD6CCCEA5E94F1BFD064993766");
186        assert_eq!(res.retrieve(), expected);
187        assert_eq!(res_vartime.retrieve(), expected);
188    }
189
190    #[test]
191    fn test_powmod_small_exponent() {
192        let base =
193            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
194        let base_mod = Fe::new(&base);
195
196        let exponent = U256::from(105u64);
197
198        let res = base_mod.pow(&exponent);
199        let res_vartime = base_mod.pow_vartime(&exponent);
200
201        let expected =
202            U256::from_be_hex("89E2A4E99F649A5AE2C18068148C355CA927B34A3245C938178ED00D6EF218AA");
203        assert_eq!(res.retrieve(), expected);
204        assert_eq!(res_vartime.retrieve(), expected);
205    }
206
207    #[test]
208    fn test_powmod() {
209        let base =
210            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
211        let base_mod = Fe::new(&base);
212
213        let exponent =
214            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
215
216        let res = base_mod.pow(&exponent);
217        let res_vartime = base_mod.pow_vartime(&exponent);
218
219        let expected =
220            U256::from_be_hex("3681BC0FEA2E5D394EB178155A127B0FD2EF405486D354251C385BDD51B9D421");
221        assert_eq!(res.retrieve(), expected);
222        assert_eq!(res_vartime.retrieve(), expected);
223    }
224
225    #[test]
226    fn test_multi_exp_array() {
227        let base = U256::from(2u8);
228        let base_mod = Fe::new(&base);
229
230        let exponent = U256::from(33u8);
231        let bases_and_exponents = [(base_mod, exponent)];
232        let res = crate::modular::const_monty_form::ConstMontyForm::<Modulus, { U256::LIMBS }>::multi_exponentiate(
233            &bases_and_exponents,
234        );
235
236        let expected =
237            U256::from_be_hex("0000000000000000000000000000000000000000000000000000000200000000");
238
239        assert_eq!(res.retrieve(), expected);
240
241        let base2 =
242            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
243        let base2_mod = Fe::new(&base2);
244
245        let exponent2 =
246            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
247
248        let expected = base_mod.pow(&exponent) * base2_mod.pow(&exponent2);
249        let bases_and_exponents = [(base_mod, exponent), (base2_mod, exponent2)];
250        let res = crate::modular::const_monty_form::ConstMontyForm::<Modulus, { U256::LIMBS }>::multi_exponentiate(
251            &bases_and_exponents,
252        );
253
254        assert_eq!(res, expected);
255    }
256
257    #[cfg(feature = "alloc")]
258    #[test]
259    fn test_multi_exp_slice() {
260        let base = U256::from(2u8);
261        let base_mod = Fe::new(&base);
262
263        let exponent = U256::from(33u8);
264        let bases_and_exponents = vec![(base_mod, exponent)];
265        let res = crate::modular::const_monty_form::ConstMontyForm::<Modulus, { U256::LIMBS }>::multi_exponentiate(
266            bases_and_exponents.as_slice(),
267        );
268
269        let expected =
270            U256::from_be_hex("0000000000000000000000000000000000000000000000000000000200000000");
271
272        assert_eq!(res.retrieve(), expected);
273
274        let base2 =
275            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
276        let base2_mod = Fe::new(&base2);
277
278        let exponent2 =
279            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
280
281        let expected = base_mod.pow(&exponent) * base2_mod.pow(&exponent2);
282        let bases_and_exponents = vec![(base_mod, exponent), (base2_mod, exponent2)];
283        let res = crate::modular::const_monty_form::ConstMontyForm::<Modulus, { U256::LIMBS }>::multi_exponentiate(
284            bases_and_exponents.as_slice(),
285        );
286
287        assert_eq!(res, expected);
288    }
289}
crypto_bigint/modular/const_monty_form/pow.rs

crypto_bigint/modular/const_monty_form/
pow.rs
