crypto_bigint/modular/monty_form/
pow.rs

1//! Exponentiation of integers in Montgomery form with a modulus set at runtime.
2
3use super::MontyForm;
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<const LIMBS: usize> MontyForm<LIMBS> {
13    /// Raises to the `exponent` power.
14    pub const fn pow<const RHS_LIMBS: usize>(
15        &self,
16        exponent: &Uint<RHS_LIMBS>,
17    ) -> MontyForm<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    ) -> Self {
31        Self {
32            montgomery_form: pow_montgomery_form(
33                &self.montgomery_form,
34                exponent,
35                exponent_bits,
36                &self.params.modulus,
37                &self.params.one,
38                self.params.mod_neg_inv,
39            ),
40            params: self.params,
41        }
42    }
43}
44
45impl<const LIMBS: usize, const RHS_LIMBS: usize> PowBoundedExp<Uint<RHS_LIMBS>>
46    for MontyForm<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, const LIMBS: usize, const RHS_LIMBS: usize>
54    MultiExponentiateBoundedExp<Uint<RHS_LIMBS>, [(Self, Uint<RHS_LIMBS>); N]>
55    for MontyForm<LIMBS>
56{
57    fn multi_exponentiate_bounded_exp(
58        bases_and_exponents: &[(Self, Uint<RHS_LIMBS>); N],
59        exponent_bits: u32,
60    ) -> Self {
61        assert!(N != 0, "bases_and_exponents must not be empty");
62        let params = bases_and_exponents[0].0.params;
63
64        let mut bases_and_exponents_montgomery_form =
65            [(Uint::<LIMBS>::ZERO, Uint::<RHS_LIMBS>::ZERO); N];
66
67        let mut i = 0;
68        while i < N {
69            let (base, exponent) = bases_and_exponents[i];
70            bases_and_exponents_montgomery_form[i] = (base.montgomery_form, exponent);
71            i += 1;
72        }
73
74        Self {
75            montgomery_form: multi_exponentiate_montgomery_form_array(
76                &bases_and_exponents_montgomery_form,
77                exponent_bits,
78                &params.modulus,
79                &params.one,
80                params.mod_neg_inv,
81            ),
82            params,
83        }
84    }
85}
86
87#[cfg(feature = "alloc")]
88impl<const LIMBS: usize, const RHS_LIMBS: usize>
89    MultiExponentiateBoundedExp<Uint<RHS_LIMBS>, [(Self, Uint<RHS_LIMBS>)]> for MontyForm<LIMBS>
90{
91    fn multi_exponentiate_bounded_exp(
92        bases_and_exponents: &[(Self, Uint<RHS_LIMBS>)],
93        exponent_bits: u32,
94    ) -> Self {
95        assert!(
96            !bases_and_exponents.is_empty(),
97            "bases_and_exponents must not be empty"
98        );
99        let params = bases_and_exponents[0].0.params;
100
101        let bases_and_exponents: Vec<(Uint<LIMBS>, Uint<RHS_LIMBS>)> = bases_and_exponents
102            .iter()
103            .map(|(base, exp)| (base.montgomery_form, *exp))
104            .collect();
105        Self {
106            montgomery_form: multi_exponentiate_montgomery_form_slice(
107                &bases_and_exponents,
108                exponent_bits,
109                &params.modulus,
110                &params.one,
111                params.mod_neg_inv,
112            ),
113            params,
114        }
115    }
116}
crypto_bigint/modular/monty_form/pow.rs

crypto_bigint/modular/monty_form/
pow.rs
