Modular exponentiation

modular.rs

fn modadd(a: u64, b: u64, module: u64) -> u64{
    if a >= module{
        return a%module;
    }else if b >= module{
        return b%module;
    }
    if a > module - b{
        return a - (module - b);
    }else if b > module - a {
        return b - (module - a);
    }else{
        return a + b;
    }
}

fn modmult(mut a: u64, mut b: u64, module: u64) -> u64{
    if a == 0 || b < a/module{
        return (a*b)%module;
    }
    let mut sum: u64 = 0;
    while b > 0{
        if b&1 == 1{
            sum = modadd(sum, a, module);
        }
        a = modadd(a, a, module);
        b >>= 1;
    }
    return sum;
}
      
fn modpow(module: u64, base: u64, mut exp: u64) -> u64 {
    if module == 1{
        return 0;
    }
    let mut result = 1;
    let mut base = base%module;
    let module = module;
    while exp > 0{
        if exp&1 == 1 {
            result = modmult(result, base, module);
        }
        exp >>= 1;
        base = modmult(base, base, module);
    }
    return result;
}