crypto_bigint/uint/boxed/
pow.rs

1//! [`BoxedUint`] exponentiation operations.
2
3use super::{BoxedUint, mul::BoxedMultiplier};
4use crate::{Checked, Choice, CtOption, Limb, PowBoundedExp, UintRef, Wrapping};
5
6impl BoxedUint {
7    /// Computes `self^exp`, returning a `CtOption` which is none in the case of overflow.
8    #[must_use]
9    pub fn checked_pow(&self, exp: impl AsRef<UintRef>) -> CtOption<Self> {
10        let exp = exp.as_ref();
11        self.checked_pow_bounded_exp(exp, exp.bits_precision())
12    }
13
14    /// Computes `self^exp`, returning a `CtOption` which is none in the case of overflow.
15    ///
16    /// NOTE: `exp_bits` may be leaked in the time pattern.
17    ///
18    /// # Panics
19    /// - if `exp_bits` exceeds the capacity of `rhs`
20    #[must_use]
21    pub fn checked_pow_bounded_exp(
22        &self,
23        exp: impl AsRef<UintRef>,
24        exp_bits: u32,
25    ) -> CtOption<Self> {
26        let (lo, overflow) = self.overflowing_pow_bounded_exp(exp, exp_bits);
27        CtOption::new(lo, overflow.not())
28    }
29
30    /// Computes `self^exp`, returning a `CtOption` which is none in the case of overflow.
31    ///
32    /// This method is variable time in the exponent `exp` only.
33    #[must_use]
34    pub fn checked_pow_vartime(&self, exp: impl AsRef<UintRef>) -> CtOption<Self> {
35        let (lo, overflow) = self.overflowing_pow_vartime(exp);
36        CtOption::new(lo, overflow.not())
37    }
38
39    /// Computes `self^exp`, returning a `Self::MAX` in the case of overflow.
40    #[must_use]
41    pub fn saturating_pow(&self, exp: impl AsRef<UintRef>) -> Self {
42        let exp = exp.as_ref();
43        self.saturating_pow_bounded_exp(exp, exp.bits_precision())
44    }
45
46    /// Computes `self^exp`, returning a `Self::MAX` in the case of overflow.
47    ///
48    /// NOTE: `exp_bits` may be leaked in the time pattern.
49    ///
50    /// # Panics
51    /// - if `exp_bits` exceeds the capacity of `rhs`
52    #[must_use]
53    pub fn saturating_pow_bounded_exp(&self, exp: impl AsRef<UintRef>, exp_bits: u32) -> Self {
54        let (mut lo, overflow) = self.overflowing_pow_bounded_exp(exp, exp_bits);
55        lo.as_mut_uint_ref().conditional_set_max(overflow);
56        lo
57    }
58
59    /// Computes `self^exp`, returning a `Self::MAX` in the case of overflow.
60    ///
61    /// This method is variable time in the exponent `exp`.
62    #[must_use]
63    pub fn saturating_pow_vartime(&self, exp: impl AsRef<UintRef>) -> Self {
64        let (mut lo, overflow) = self.overflowing_pow_vartime(exp);
65        lo.as_mut_uint_ref().conditional_set_max(overflow);
66        lo
67    }
68
69    /// Computes `self^exp`, discarding overflow.
70    #[must_use]
71    pub fn wrapping_pow(&self, exp: impl AsRef<UintRef>) -> Self {
72        let exp = exp.as_ref();
73        self.wrapping_pow_bounded_exp(exp, exp.bits_precision())
74    }
75
76    /// Computes `self^exp`, discarding overflow.
77    ///
78    /// NOTE: `exp_bits` may be leaked in the time pattern.
79    ///
80    /// # Panics
81    /// - if `exp_bits` exceeds the capacity of `rhs`
82    #[must_use]
83    pub fn wrapping_pow_bounded_exp(&self, exp: impl AsRef<UintRef>, exp_bits: u32) -> Self {
84        let exp = exp.as_ref();
85        assert!(exp_bits <= exp.bits_precision());
86        let mut ret = Self::one_with_precision(self.bits_precision());
87        let mut helper = BoxedMultiplier::new();
88        let mut limbs = exp_bits.div_ceil(Limb::BITS);
89        let mut i = exp_bits - limbs.saturating_sub(1) * Limb::BITS;
90        while limbs > 0 {
91            limbs -= 1;
92            let limb = exp.as_limbs()[limbs as usize];
93            while i > 0 {
94                i -= 1;
95                helper.wrapping_square_assign(&mut ret);
96                let apply = limb.shr(i).lsb_to_choice();
97                let buf = helper.wrapping_mul(&ret, self);
98                ret.as_mut_uint_ref().conditional_copy_from(buf, apply);
99            }
100            i = Limb::BITS;
101        }
102        ret
103    }
104
105    /// Computes `self^exp`, discarding overflow.
106    ///
107    /// This method is variable time in the exponent `exp` only.
108    #[inline]
109    #[must_use]
110    pub fn wrapping_pow_vartime(&self, exp: impl AsRef<UintRef>) -> Self {
111        let exp = exp.as_ref();
112        let mut exp_bits = exp.bits_vartime();
113        if exp_bits == 0 {
114            return Self::one_with_precision(self.bits_precision());
115        }
116        exp_bits -= 1;
117        let mut ret = self.clone();
118        let mut helper = BoxedMultiplier::new();
119        let mut limbs = exp_bits.div_ceil(Limb::BITS);
120        let mut i = exp_bits - limbs.saturating_sub(1) * Limb::BITS;
121        while limbs > 0 {
122            limbs -= 1;
123            let word = exp.as_limbs()[limbs as usize].0;
124            while i > 0 {
125                i -= 1;
126                helper.wrapping_square_assign(&mut ret);
127                if (word >> i) & 1 == 1 {
128                    helper.wrapping_mul_assign(&mut ret, self);
129                }
130            }
131            i = Limb::BITS;
132        }
133        ret
134    }
135
136    /// Computes `self^exp`, returning a wrapped result and a `Choice`
137    /// indicating whether overflow occurred.
138    ///
139    /// NOTE: `exp_bits` may be leaked in the time pattern.
140    #[inline(always)]
141    #[must_use]
142    pub(crate) fn overflowing_pow_bounded_exp(
143        &self,
144        exp: impl AsRef<UintRef>,
145        exp_bits: u32,
146    ) -> (Self, Choice) {
147        let exp = exp.as_ref();
148        assert!(exp_bits <= exp.bits_precision());
149        let mut ret = Self::one_with_precision(self.bits_precision());
150        let mut helper = BoxedMultiplier::new();
151        let mut overflow = Choice::FALSE;
152        let mut check;
153        let mut limbs = exp_bits.div_ceil(Limb::BITS);
154        let mut i = exp_bits - limbs.saturating_sub(1) * Limb::BITS;
155        while limbs > 0 {
156            limbs -= 1;
157            let limb = exp.as_limbs()[limbs as usize];
158            while i > 0 {
159                i -= 1;
160                check = helper.overflowing_square_assign(&mut ret);
161                overflow = overflow.or(check);
162                let (mul, check) = helper.overflowing_mul(&ret, self);
163                let apply = limb.shr(i).lsb_to_choice();
164                ret.as_mut_uint_ref().conditional_copy_from(mul, apply);
165                overflow = overflow.or(check.and(apply));
166            }
167            i = Limb::BITS;
168        }
169        (ret, overflow)
170    }
171
172    /// Computes `self^exp`, returning a wrapped result and a `Choice`
173    /// indicating whether overflow occurred.
174    ///
175    /// This method is variable time in the exponent `exp` only.
176    #[inline(always)]
177    #[must_use]
178    pub(crate) fn overflowing_pow_vartime(&self, exp: impl AsRef<UintRef>) -> (Self, Choice) {
179        let exp = exp.as_ref();
180        let mut exp_bits = exp.bits_vartime();
181        if exp_bits == 0 {
182            return (
183                Self::one_with_precision(self.bits_precision()),
184                Choice::FALSE,
185            );
186        }
187        exp_bits -= 1;
188        let mut ret = self.clone();
189        let mut helper = BoxedMultiplier::new();
190        let mut overflow = Choice::FALSE;
191        let mut check;
192        let mut limbs = exp_bits.div_ceil(Limb::BITS);
193        let mut i = exp_bits - limbs.saturating_sub(1) * Limb::BITS;
194        while limbs > 0 {
195            limbs -= 1;
196            let word = exp.limbs[limbs as usize].0;
197            while i > 0 {
198                i -= 1;
199                check = helper.overflowing_square_assign(&mut ret);
200                overflow = overflow.or(check);
201                if (word >> i) & 1 == 1 {
202                    check = helper.overflowing_mul_assign(&mut ret, self);
203                    overflow = overflow.or(check);
204                }
205            }
206            i = Limb::BITS;
207        }
208        (ret, overflow)
209    }
210}
211
212impl<Rhs: AsRef<UintRef>> PowBoundedExp<Rhs> for Checked<BoxedUint> {
213    fn pow_bounded_exp(&self, exponent: &Rhs, exponent_bits: u32) -> Self {
214        let is_some = self.0.is_some();
215        let pow = self
216            .0
217            .as_inner_unchecked()
218            .checked_pow_bounded_exp(exponent, exponent_bits);
219        Checked(pow.filter_by(is_some))
220    }
221}
222
223impl<Rhs: AsRef<UintRef>> PowBoundedExp<Rhs> for Wrapping<BoxedUint> {
224    fn pow_bounded_exp(&self, exponent: &Rhs, exponent_bits: u32) -> Self {
225        Wrapping(self.0.wrapping_pow_bounded_exp(exponent, exponent_bits))
226    }
227}
228
229#[cfg(test)]
230mod tests {
231    use crate::{BoxedUint, Checked, CtOption, Limb, Pow, Resize, U128, UintRef, Wrapping};
232
233    #[test]
234    fn checked_pow_expected() {
235        let checks = [
236            (U128::ZERO, U128::ZERO, Some(U128::ONE)),
237            (U128::ZERO, U128::MAX, Some(U128::ZERO)),
238            (U128::ONE, U128::ZERO, Some(U128::ONE)),
239            (U128::ONE, U128::MAX, Some(U128::ONE)),
240            (U128::MAX, U128::ZERO, Some(U128::ONE)),
241            (U128::MAX, U128::ONE, Some(U128::MAX)),
242            (U128::MAX, U128::from_u8(2), None),
243            (U128::MAX, U128::MAX, None),
244        ];
245        for (base, pow, expect) in checks {
246            let (base, pow, expect) = (
247                BoxedUint::from(base),
248                BoxedUint::from(pow),
249                expect.map(BoxedUint::from),
250            );
251            assert_eq!(base.checked_pow(&pow).into_option(), expect);
252            assert_eq!(base.checked_pow_vartime(&pow).into_option(), expect);
253            assert_eq!(
254                Checked(CtOption::some(base)).pow(&pow).0.into_option(),
255                expect
256            );
257        }
258
259        assert!(
260            Checked(CtOption::<U128>::none())
261                .pow(&U128::ONE)
262                .0
263                .is_none()
264                .to_bool_vartime()
265        );
266    }
267
268    #[test]
269    fn saturating_pow_expected() {
270        let checks = [
271            (U128::ZERO, U128::ZERO, U128::ONE),
272            (U128::ZERO, U128::MAX, U128::ZERO),
273            (U128::ONE, U128::ZERO, U128::ONE),
274            (U128::ONE, U128::MAX, U128::ONE),
275            (U128::MAX, U128::ZERO, U128::ONE),
276            (U128::MAX, U128::ONE, U128::MAX),
277            (U128::MAX, U128::from_u8(2), U128::MAX),
278            (U128::MAX, U128::MAX, U128::MAX),
279        ];
280        for (base, pow, expect) in checks {
281            let (base, pow, expect) = (
282                BoxedUint::from(base),
283                BoxedUint::from(pow),
284                BoxedUint::from(expect),
285            );
286            assert_eq!(base.saturating_pow(&pow), expect);
287            assert_eq!(base.saturating_pow_vartime(&pow), expect);
288        }
289    }
290
291    #[test]
292    fn wrapping_pow_expected() {
293        let checks = [
294            (U128::ZERO, U128::ZERO, U128::ONE),
295            (U128::ZERO, U128::MAX, U128::ZERO),
296            (U128::ONE, U128::ZERO, U128::ONE),
297            (U128::ONE, U128::MAX, U128::ONE),
298            (U128::MAX, U128::ZERO, U128::ONE),
299            (U128::MAX, U128::ONE, U128::MAX),
300            (U128::MAX, U128::from_u8(2), U128::ONE),
301            (U128::MAX, U128::from_u8(3), U128::MAX),
302            (U128::MAX, U128::MAX, U128::MAX),
303        ];
304        for (base, pow, expect) in checks {
305            let (base, pow, expect) = (
306                BoxedUint::from(base),
307                BoxedUint::from(pow),
308                BoxedUint::from(expect),
309            );
310            assert_eq!(base.wrapping_pow(&pow), expect);
311            assert_eq!(base.wrapping_pow_vartime(&pow), expect);
312            assert_eq!(Wrapping(base).pow(&pow), Wrapping(expect));
313        }
314
315        let two = BoxedUint::from(U128::from_u8(2));
316        assert_eq!(two.wrapping_pow_vartime(U128::ZERO), U128::ONE);
317        for i in 0..10 {
318            let pow = 1u32 << i;
319            assert_eq!(
320                two.wrapping_pow_vartime(U128::from_u32(pow)),
321                U128::from_u128(2u128.wrapping_pow(pow)),
322                "i={i}"
323            );
324        }
325
326        assert_eq!(
327            BoxedUint::from(U128::from_u8(3))
328                .wrapping_pow_vartime(U128::from_u128((1 << 64) + (1 << 63))),
329            BoxedUint::from_be_hex("002b3854b3dc5d6e0000000000000001", 128).unwrap()
330        );
331    }
332
333    #[test]
334    fn pow_uintref() {
335        let a = BoxedUint::from(1234567890u64).resize_unchecked(128);
336        let b = UintRef::new(&[Limb(4), Limb(0)]);
337        assert_eq!(
338            a.wrapping_pow(b),
339            BoxedUint::from(2323057227982592441500937982514410000u128)
340        );
341    }
342}
crypto_bigint/uint/boxed/pow.rs

crypto_bigint/uint/boxed/
pow.rs
