num_bigint/bigint/
power.rs

Help
1use super::BigInt;
2use super::Sign::{self, Minus, Plus};
3
4use crate::BigUint;
5
6use num_integer::Integer;
7use num_traits::{Pow, Signed, Zero};
8
9/// Help function for pow
10///
11/// Computes the effect of the exponent on the sign.
12#[inline]
13fn powsign<T: Integer>(sign: Sign, other: &T) -> Sign {
14    if other.is_zero() {
15        Plus
16    } else if sign != Minus || other.is_odd() {
17        sign
18    } else {
19        -sign
20    }
21}
22
23macro_rules! pow_impl {
24    ($T:ty) => {
25        impl Pow<$T> for BigInt {
26            type Output = BigInt;
27
28            #[inline]
29            fn pow(self, rhs: $T) -> BigInt {
30                BigInt::from_biguint(powsign(self.sign, &rhs), self.data.pow(rhs))
31            }
32        }
33
34        impl<'b> Pow<&'b $T> for BigInt {
35            type Output = BigInt;
36
37            #[inline]
38            fn pow(self, rhs: &$T) -> BigInt {
39                BigInt::from_biguint(powsign(self.sign, rhs), self.data.pow(rhs))
40            }
41        }
42
43        impl<'a> Pow<$T> for &'a BigInt {
44            type Output = BigInt;
45
46            #[inline]
47            fn pow(self, rhs: $T) -> BigInt {
48                BigInt::from_biguint(powsign(self.sign, &rhs), Pow::pow(&self.data, rhs))
49            }
50        }
51
52        impl<'a, 'b> Pow<&'b $T> for &'a BigInt {
53            type Output = BigInt;
54
55            #[inline]
56            fn pow(self, rhs: &$T) -> BigInt {
57                BigInt::from_biguint(powsign(self.sign, rhs), Pow::pow(&self.data, rhs))
58            }
59        }
60    };
61}
62
63pow_impl!(u8);
64pow_impl!(u16);
65pow_impl!(u32);
66pow_impl!(u64);
67pow_impl!(usize);
68pow_impl!(u128);
69pow_impl!(BigUint);
70
71pub(super) fn modpow(x: &BigInt, exponent: &BigInt, modulus: &BigInt) -> BigInt {
72    assert!(
73        !exponent.is_negative(),
74        "negative exponentiation is not supported!"
75    );
76    assert!(
77        !modulus.is_zero(),
78        "attempt to calculate with zero modulus!"
79    );
80
81    let result = x.data.modpow(&exponent.data, &modulus.data);
82    if result.is_zero() {
83        return BigInt::zero();
84    }
85
86    // The sign of the result follows the modulus, like `mod_floor`.
87    let (sign, mag) = match (x.is_negative() && exponent.is_odd(), modulus.is_negative()) {
88        (false, false) => (Plus, result),
89        (true, false) => (Plus, &modulus.data - result),
90        (false, true) => (Minus, &modulus.data - result),
91        (true, true) => (Minus, result),
92    };
93    BigInt::from_biguint(sign, mag)
94}
num_bigint/bigint/power.rs

num_bigint/bigint/
power.rs
