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    modular::pow::{multi_exponentiate_montgomery_form_array, pow_montgomery_form},
6    MultiExponentiateBoundedExp, PowBoundedExp, Uint,
7};
8
9#[cfg(feature = "alloc")]
10use {crate::modular::pow::multi_exponentiate_montgomery_form_slice, alloc::vec::Vec};
11
12impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize> ConstMontyForm<MOD, LIMBS> {
13    /// Raises to the `exponent` power.
14    pub const fn pow<const RHS_LIMBS: usize>(
15        &self,
16        exponent: &Uint<RHS_LIMBS>,
17    ) -> ConstMontyForm<MOD, LIMBS> {
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    pub const fn pow_bounded_exp<const RHS_LIMBS: usize>(
27        &self,
28        exponent: &Uint<RHS_LIMBS>,
29        exponent_bits: u32,
30    ) -> ConstMontyForm<MOD, LIMBS> {
31        Self {
32            montgomery_form: pow_montgomery_form(
33                &self.montgomery_form,
34                exponent,
35                exponent_bits,
36                &MOD::MODULUS,
37                &MOD::ONE,
38                MOD::MOD_NEG_INV,
39            ),
40            phantom: core::marker::PhantomData,
41        }
42    }
43}
44
45impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize, const RHS_LIMBS: usize>
46    PowBoundedExp<Uint<RHS_LIMBS>> for ConstMontyForm<MOD, LIMBS>
47{
48    fn pow_bounded_exp(&self, exponent: &Uint<RHS_LIMBS>, exponent_bits: u32) -> Self {
49        self.pow_bounded_exp(exponent, exponent_bits)
50    }
51}
52
53impl<const N: usize, MOD: ConstMontyParams<LIMBS>, const LIMBS: usize, const RHS_LIMBS: usize>
54    MultiExponentiateBoundedExp<Uint<RHS_LIMBS>, [(Self, Uint<RHS_LIMBS>); N]>
55    for ConstMontyForm<MOD, LIMBS>
56{
57    fn multi_exponentiate_bounded_exp(
58        bases_and_exponents: &[(Self, Uint<RHS_LIMBS>); N],
59        exponent_bits: u32,
60    ) -> Self {
61        let mut bases_and_exponents_montgomery_form =
62            [(Uint::<LIMBS>::ZERO, Uint::<RHS_LIMBS>::ZERO); N];
63
64        let mut i = 0;
65        while i < N {
66            let (base, exponent) = bases_and_exponents[i];
67            bases_and_exponents_montgomery_form[i] = (base.montgomery_form, exponent);
68            i += 1;
69        }
70
71        Self {
72            montgomery_form: multi_exponentiate_montgomery_form_array(
73                &bases_and_exponents_montgomery_form,
74                exponent_bits,
75                &MOD::MODULUS,
76                &MOD::ONE,
77                MOD::MOD_NEG_INV,
78            ),
79            phantom: core::marker::PhantomData,
80        }
81    }
82}
83
84#[cfg(feature = "alloc")]
85impl<MOD: ConstMontyParams<LIMBS>, const LIMBS: usize, const RHS_LIMBS: usize>
86    MultiExponentiateBoundedExp<Uint<RHS_LIMBS>, [(Self, Uint<RHS_LIMBS>)]>
87    for ConstMontyForm<MOD, LIMBS>
88{
89    fn multi_exponentiate_bounded_exp(
90        bases_and_exponents: &[(Self, Uint<RHS_LIMBS>)],
91        exponent_bits: u32,
92    ) -> Self {
93        let bases_and_exponents: Vec<(Uint<LIMBS>, Uint<RHS_LIMBS>)> = bases_and_exponents
94            .iter()
95            .map(|(base, exp)| (base.montgomery_form, *exp))
96            .collect();
97        Self {
98            montgomery_form: multi_exponentiate_montgomery_form_slice(
99                &bases_and_exponents,
100                exponent_bits,
101                &MOD::MODULUS,
102                &MOD::ONE,
103                MOD::MOD_NEG_INV,
104            ),
105            phantom: core::marker::PhantomData,
106        }
107    }
108}
109
110#[cfg(test)]
111mod tests {
112    use crate::traits::MultiExponentiate;
113    use crate::{
114        const_monty_form, impl_modulus, modular::const_monty_form::ConstMontyParams, U256,
115    };
116
117    impl_modulus!(
118        Modulus,
119        U256,
120        "9CC24C5DF431A864188AB905AC751B727C9447A8E99E6366E1AD78A21E8D882B"
121    );
122
123    #[test]
124    fn test_powmod_small_base() {
125        let base = U256::from(105u64);
126        let base_mod = const_monty_form!(base, Modulus);
127
128        let exponent =
129            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
130
131        let res = base_mod.pow(&exponent);
132
133        let expected =
134            U256::from_be_hex("7B2CD7BDDD96C271E6F232F2F415BB03FE2A90BD6CCCEA5E94F1BFD064993766");
135        assert_eq!(res.retrieve(), expected);
136    }
137
138    #[test]
139    fn test_powmod_small_exponent() {
140        let base =
141            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
142        let base_mod = const_monty_form!(base, Modulus);
143
144        let exponent = U256::from(105u64);
145
146        let res = base_mod.pow(&exponent);
147
148        let expected =
149            U256::from_be_hex("89E2A4E99F649A5AE2C18068148C355CA927B34A3245C938178ED00D6EF218AA");
150        assert_eq!(res.retrieve(), expected);
151    }
152
153    #[test]
154    fn test_powmod() {
155        let base =
156            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
157        let base_mod = const_monty_form!(base, Modulus);
158
159        let exponent =
160            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
161
162        let res = base_mod.pow(&exponent);
163
164        let expected =
165            U256::from_be_hex("3681BC0FEA2E5D394EB178155A127B0FD2EF405486D354251C385BDD51B9D421");
166        assert_eq!(res.retrieve(), expected);
167    }
168
169    #[test]
170    fn test_multi_exp_array() {
171        let base = U256::from(2u8);
172        let base_mod = const_monty_form!(base, Modulus);
173
174        let exponent = U256::from(33u8);
175        let bases_and_exponents = [(base_mod, exponent)];
176        let res = crate::modular::const_monty_form::ConstMontyForm::<Modulus, { U256::LIMBS }>::multi_exponentiate(
177            &bases_and_exponents,
178        );
179
180        let expected =
181            U256::from_be_hex("0000000000000000000000000000000000000000000000000000000200000000");
182
183        assert_eq!(res.retrieve(), expected);
184
185        let base2 =
186            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
187        let base2_mod = const_monty_form!(base2, Modulus);
188
189        let exponent2 =
190            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
191
192        let expected = base_mod.pow(&exponent) * base2_mod.pow(&exponent2);
193        let bases_and_exponents = [(base_mod, exponent), (base2_mod, exponent2)];
194        let res = crate::modular::const_monty_form::ConstMontyForm::<Modulus, { U256::LIMBS }>::multi_exponentiate(
195            &bases_and_exponents,
196        );
197
198        assert_eq!(res, expected);
199    }
200
201    #[cfg(feature = "alloc")]
202    #[test]
203    fn test_multi_exp_slice() {
204        let base = U256::from(2u8);
205        let base_mod = const_monty_form!(base, Modulus);
206
207        let exponent = U256::from(33u8);
208        let bases_and_exponents = vec![(base_mod, exponent)];
209        let res = crate::modular::const_monty_form::ConstMontyForm::<Modulus, { U256::LIMBS }>::multi_exponentiate(
210            bases_and_exponents.as_slice(),
211        );
212
213        let expected =
214            U256::from_be_hex("0000000000000000000000000000000000000000000000000000000200000000");
215
216        assert_eq!(res.retrieve(), expected);
217
218        let base2 =
219            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
220        let base2_mod = const_monty_form!(base2, Modulus);
221
222        let exponent2 =
223            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
224
225        let expected = base_mod.pow(&exponent) * base2_mod.pow(&exponent2);
226        let bases_and_exponents = vec![(base_mod, exponent), (base2_mod, exponent2)];
227        let res = crate::modular::const_monty_form::ConstMontyForm::<Modulus, { U256::LIMBS }>::multi_exponentiate(
228            bases_and_exponents.as_slice(),
229        );
230
231        assert_eq!(res, expected);
232    }
233}
crypto_bigint/modular/const_monty_form/pow.rs

crypto_bigint/modular/const_monty_form/
pow.rs
