blob: a4dd8063d3d16bcdc91dff297a0ab71546c0da70 [file] [log] [blame]
 use super::BigInt; use super::Sign::{self, Minus, Plus}; use crate::BigUint; use num_integer::Integer; use num_traits::{Pow, Signed, Zero}; /// Help function for pow /// /// Computes the effect of the exponent on the sign. #[inline] fn powsign(sign: Sign, other: &T) -> Sign { if other.is_zero() { Plus } else if sign != Minus || other.is_odd() { sign } else { -sign } } macro_rules! pow_impl { (\$T:ty) => { impl Pow<\$T> for BigInt { type Output = BigInt; #[inline] fn pow(self, rhs: \$T) -> BigInt { BigInt::from_biguint(powsign(self.sign, &rhs), self.data.pow(rhs)) } } impl<'b> Pow<&'b \$T> for BigInt { type Output = BigInt; #[inline] fn pow(self, rhs: &\$T) -> BigInt { BigInt::from_biguint(powsign(self.sign, rhs), self.data.pow(rhs)) } } impl<'a> Pow<\$T> for &'a BigInt { type Output = BigInt; #[inline] fn pow(self, rhs: \$T) -> BigInt { BigInt::from_biguint(powsign(self.sign, &rhs), Pow::pow(&self.data, rhs)) } } impl<'a, 'b> Pow<&'b \$T> for &'a BigInt { type Output = BigInt; #[inline] fn pow(self, rhs: &\$T) -> BigInt { BigInt::from_biguint(powsign(self.sign, rhs), Pow::pow(&self.data, rhs)) } } }; } pow_impl!(u8); pow_impl!(u16); pow_impl!(u32); pow_impl!(u64); pow_impl!(usize); pow_impl!(u128); pow_impl!(BigUint); pub(super) fn modpow(x: &BigInt, exponent: &BigInt, modulus: &BigInt) -> BigInt { assert!( !exponent.is_negative(), "negative exponentiation is not supported!" ); assert!( !modulus.is_zero(), "attempt to calculate with zero modulus!" ); let result = x.data.modpow(&exponent.data, &modulus.data); if result.is_zero() { return BigInt::zero(); } // The sign of the result follows the modulus, like `mod_floor`. let (sign, mag) = match (x.is_negative() && exponent.is_odd(), modulus.is_negative()) { (false, false) => (Plus, result), (true, false) => (Plus, &modulus.data - result), (false, true) => (Minus, &modulus.data - result), (true, true) => (Minus, result), }; BigInt::from_biguint(sign, mag) }