use tc_bigint::BigUint;
use super::BigMontyForm;
impl BigMontyForm<'_> {
pub fn pow_vartime(&self, exponent: &BigUint) -> Self {
let mut power = Self::one(self.params);
for index in (0..exponent.bits()).rev() {
power = power.square();
if exponent.bit(index) {
power *= self;
}
}
power
}
}
#[cfg(test)]
mod tests {
use super::super::testing::{MODULI, VALUES, form, int, mul_mod, params};
fn pow_mod(a: u64, e: u64, m: u64) -> u64 {
let (mut base, mut power, mut e) = (a % m, 1 % m, e);
while e != 0 {
if e & 1 == 1 {
power = mul_mod(power, base, m);
}
base = mul_mod(base, base, m);
e >>= 1;
}
power
}
#[test]
fn the_power_matches_squaring_and_multiplying_in_primitives() {
for m in MODULI {
let params = params(m);
for a in VALUES {
for e in VALUES {
let power = form(a, ¶ms).pow_vartime(&int(e)).retrieve();
assert_eq!(power, int(pow_mod(a, e, m)), "{a} {e} {m}");
}
}
}
}
}