use num_traits::One;
use tc_bigint::{FixedBigUint, Word};
use tc_constant_time::{Choice, ConditionallySelectable};
use super::mul::mul_residues;
use crate::wipe::replace_wiped;
use crate::{FixedMontyForm, FixedMontyParams, ModPow, NonZero, Odd};
use tc_zeroize::Zeroizing;
impl<const N: usize> ModPow for FixedBigUint<N> {
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 base = Zeroizing::new(FixedMontyForm::new(self, FixedMontyParams::new(odd)));
let power = Zeroizing::new(base.pow(exponent));
power.retrieve()
}
None => pow_residues(&Zeroizing::new(self % modulus), exponent, modulus),
}
}
}
fn pow_residues<const N: usize>(
base: &FixedBigUint<N>,
exponent: &FixedBigUint<N>,
modulus: &FixedBigUint<N>,
) -> FixedBigUint<N> {
let mut power = FixedBigUint::one() % modulus;
for index in (0..N as u32 * Word::BITS).rev() {
let squared = mul_residues(&power, &power, modulus);
replace_wiped(&mut power, squared);
let product = Zeroizing::new(mul_residues(&power, base, modulus));
power.conditional_assign(&product, Choice::from_lsb(u8::from(exponent.bit(index))));
}
power
}
#[cfg(test)]
mod tests {
use tc_bigint::{FixedBigUint, Word};
use crate::{ModPow, NonZero};
const SMALL: usize = (u64::BITS / Word::BITS) as usize;
const LARGE: usize = (u128::BITS / Word::BITS) as usize;
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(FixedBigUint::<SMALL>::from(*m)).unwrap();
for a in VALUES {
for e in VALUES {
let (x, y) = (
FixedBigUint::<SMALL>::from(a),
FixedBigUint::<SMALL>::from(e),
);
let expected = FixedBigUint::<SMALL>::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(FixedBigUint::<LARGE>::from(prime)).unwrap();
let power = FixedBigUint::<LARGE>::from(3u8)
.mod_pow(&FixedBigUint::<LARGE>::from(prime - 1), &modulus);
assert_eq!(power, FixedBigUint::<LARGE>::from(1u8));
}
}