src/tools.rs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

use num::BigUint;

pub fn powm(base: &BigUint, exp: &BigUint, modulus: &BigUint) -> BigUint {
    let zero = BigUint::new(vec![0]);
    let one = BigUint::new(vec![1]);
    let two = BigUint::new(vec![2]);
    let mut exp = exp.clone();
    let mut result = one.clone();
    let mut base = base % modulus;

    while exp > zero {
        if &exp % &two == one {
            result = (result * &base) % modulus;
        }
        exp = exp >> 1;
        base = (&base * &base) % modulus;
    }
    result
}