Rust extra::bigint mod_exp

mod_exp.rs

// Modular exponentiation by squaring
fn mod_exp(base: &BigUint, exponent: &BigUint, modulus: &BigUint) -> BigUint {
  let (zero, one): (BigUint, BigUint) = (Zero::zero(), One::one());
  let mut result = one.clone();
  let mut baseAcc = base.clone();
  let mut exponentAcc = exponent.clone();

  while exponentAcc > zero {
    // Accumulate current base if current exponent bit is 1
    if (exponent & one) == one {
      result = (result.mul(&baseAcc)).rem(modulus);
    }
    // Get next base by squaring
    baseAcc = (baseAcc.mul(&baseAcc)).rem(modulus);
    // Get next bit of exponent
    exponentAcc = exponentAcc.shr(&1);
  }
  result
}

#[test]
fn test_mod_exp() {
  let two = 2u.to_biguint().unwrap();
  let three = 3u.to_biguint().unwrap();
  let seven = 7u.to_biguint().unwrap();
  let one: BigUint = One::one();
  assert_eq!(mod_exp(&two, &three, &seven), one);
}