use num_traits::One;
use tc_bigint::BigUint;
use crate::{BigMontyForm, BigMontyParams, ModPow, NonZero, Odd};
impl ModPow for BigUint {
type Output = Self;
fn mod_pow(&self, exponent: &Self, modulus: &NonZero<Self>) -> Self {
let modulus: &Self = modulus;
match Odd::new(modulus.clone()) {
Some(odd) => {
let params = BigMontyParams::new(odd);
BigMontyForm::new(self, ¶ms)
.pow_vartime(exponent)
.retrieve()
}
None => pow_residues(&(self % modulus), exponent, modulus),
}
}
}
fn pow_residues(base: &BigUint, exponent: &BigUint, modulus: &BigUint) -> BigUint {
let mut power = BigUint::one() % modulus;
for index in (0..exponent.bits()).rev() {
power = (&power * &power) % modulus;
if exponent.bit(index) {
power = (power * base) % modulus;
}
}
power
}
#[cfg(test)]
mod tests {
use tc_bigint::BigUint;
use crate::{ModPow, NonZero};
const VALUES: [u64; 6] = [0, 1, 2, u32::MAX as u64 + 1, i64::MAX as u64, u64::MAX];
fn expected(a: u64, e: u64, m: u64) -> u64 {
let m = u128::from(m);
let (mut base, mut power, mut e) = (u128::from(a) % m, 1 % m, e);
while e != 0 {
if e & 1 == 1 {
power = power * base % m;
}
base = base * base % m;
e >>= 1;
}
power as u64
}
#[test]
fn the_power_matches_squaring_and_multiplying_in_primitives() {
for m in &VALUES[1..] {
let modulus = NonZero::new(BigUint::from(*m)).unwrap();
for a in VALUES {
for e in VALUES {
let (x, y) = (BigUint::from(a), BigUint::from(e));
let expected = BigUint::from(expected(a, e, *m));
assert_eq!(x.mod_pow(&y, &modulus), expected, "{a} {e} {m}");
}
}
}
}
#[test]
fn a_power_of_a_prime_minus_one_is_one_as_fermat_has_it() {
let prime = i128::MAX as u128;
let modulus = NonZero::new(BigUint::from(prime)).unwrap();
let power = BigUint::from(3u8).mod_pow(&BigUint::from(prime - 1), &modulus);
assert_eq!(power, BigUint::from(1u8));
}
}