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 Pow<&$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 Pow<$T> for &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 Pow<&$T> for &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: BigUint = 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: Sign, mag: BigUint) = 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, data:mag)
94}
95