crypto_bigint/uint/modular/constant_mod/
const_pow.rs

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

crypto_bigint/uint/modular/constant_mod/
const_pow.rs
