/rust/registry/src/index.crates.io-1949cf8c6b5b557f/num-bigint-0.4.6/src/bigint/power.rs
Line | Count | Source |
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] |
13 | 0 | fn powsign<T: Integer>(sign: Sign, other: &T) -> Sign { |
14 | 0 | if other.is_zero() { |
15 | 0 | Plus |
16 | 0 | } else if sign != Minus || other.is_odd() { |
17 | 0 | sign |
18 | | } else { |
19 | 0 | -sign |
20 | | } |
21 | 0 | } |
22 | | |
23 | | macro_rules! pow_impl { |
24 | | ($T:ty) => { |
25 | | impl Pow<$T> for BigInt { |
26 | | type Output = BigInt; |
27 | | |
28 | | #[inline] |
29 | 0 | fn pow(self, rhs: $T) -> BigInt { |
30 | 0 | BigInt::from_biguint(powsign(self.sign, &rhs), self.data.pow(rhs)) |
31 | 0 | } Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<u8>>::pow Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<u16>>::pow Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<u32>>::pow Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<u64>>::pow Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<usize>>::pow Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<u128>>::pow Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<num_bigint::biguint::BigUint>>::pow |
32 | | } |
33 | | |
34 | | impl Pow<&$T> for BigInt { |
35 | | type Output = BigInt; |
36 | | |
37 | | #[inline] |
38 | 0 | fn pow(self, rhs: &$T) -> BigInt { |
39 | 0 | BigInt::from_biguint(powsign(self.sign, rhs), self.data.pow(rhs)) |
40 | 0 | } Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<&u16>>::pow Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<&u32>>::pow Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<&u8>>::pow Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<&u64>>::pow Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<&usize>>::pow Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<&u128>>::pow Unexecuted instantiation: <num_bigint::bigint::BigInt as num_traits::pow::Pow<&num_bigint::biguint::BigUint>>::pow |
41 | | } |
42 | | |
43 | | impl Pow<$T> for &BigInt { |
44 | | type Output = BigInt; |
45 | | |
46 | | #[inline] |
47 | 0 | fn pow(self, rhs: $T) -> BigInt { |
48 | 0 | BigInt::from_biguint(powsign(self.sign, &rhs), Pow::pow(&self.data, rhs)) |
49 | 0 | } Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<u32>>::pow Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<u8>>::pow Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<u16>>::pow Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<u64>>::pow Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<usize>>::pow Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<u128>>::pow Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<num_bigint::biguint::BigUint>>::pow |
50 | | } |
51 | | |
52 | | impl Pow<&$T> for &BigInt { |
53 | | type Output = BigInt; |
54 | | |
55 | | #[inline] |
56 | 0 | fn pow(self, rhs: &$T) -> BigInt { |
57 | 0 | BigInt::from_biguint(powsign(self.sign, rhs), Pow::pow(&self.data, rhs)) |
58 | 0 | } Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<&u8>>::pow Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<&u16>>::pow Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<&u32>>::pow Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<&u64>>::pow Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<&usize>>::pow Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<&u128>>::pow Unexecuted instantiation: <&num_bigint::bigint::BigInt as num_traits::pow::Pow<&num_bigint::biguint::BigUint>>::pow |
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 | | |
71 | 0 | pub(super) fn modpow(x: &BigInt, exponent: &BigInt, modulus: &BigInt) -> BigInt { |
72 | 0 | assert!( |
73 | 0 | !exponent.is_negative(), |
74 | 0 | "negative exponentiation is not supported!" |
75 | | ); |
76 | 0 | assert!( |
77 | 0 | !modulus.is_zero(), |
78 | 0 | "attempt to calculate with zero modulus!" |
79 | | ); |
80 | | |
81 | 0 | let result = x.data.modpow(&exponent.data, &modulus.data); |
82 | 0 | if result.is_zero() { |
83 | 0 | return BigInt::ZERO; |
84 | 0 | } |
85 | | |
86 | | // The sign of the result follows the modulus, like `mod_floor`. |
87 | 0 | let (sign, mag) = match (x.is_negative() && exponent.is_odd(), modulus.is_negative()) { |
88 | 0 | (false, false) => (Plus, result), |
89 | 0 | (true, false) => (Plus, &modulus.data - result), |
90 | 0 | (false, true) => (Minus, &modulus.data - result), |
91 | 0 | (true, true) => (Minus, result), |
92 | | }; |
93 | 0 | BigInt::from_biguint(sign, mag) |
94 | 0 | } |