1 use super::BigInt;
2 use super::Sign::{self, Minus, Plus};
3
4 use crate::BigUint;
5
6 use num_integer::Integer;
7 use num_traits::{Pow, Signed, Zero};
8
9 /// Help function for pow
10 ///
11 /// Computes the effect of the exponent on the sign.
12 #[inline]
powsign<T: Integer>(sign: Sign, other: &T) -> Sign13 fn 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
23 macro_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
63 pow_impl!(u8);
64 pow_impl!(u16);
65 pow_impl!(u32);
66 pow_impl!(u64);
67 pow_impl!(usize);
68 pow_impl!(u128);
69 pow_impl!(BigUint);
70
modpow(x: &BigInt, exponent: &BigInt, modulus: &BigInt) -> BigInt71 pub(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 }
95