pow_mod.rs

/// Exponenciación modular ((b^e) % m)
fn pow_mod(b: usize, mut e: usize, m: usize) -> usize {
    // if e == 0 { return 1; }

    // if e % 2 == 0 {
    //     pow_mod(b, e / 2, m).pow(2) % m
    // } else {
    //     (b * pow_mod(b, e - 1, m)) % m
    // }

    // p < 0 && throw(DomainError())
    // b = oftype(m,mod(b,m))  # this also checks for divide by zero
    // p == 0 && return mod(one(b),m)
    // (m == 1 || m == -1) && return zero(m)

    // t = prevpow2(p)
    // local r::T
    // r = 1
    // while true
    //     if p >= t
    //         r = mod(widemul(r,b),m)
    //         p -= t
    //     end
    //     t >>>= 1
    //     t <= 0 && break
    //     r = mod(widemul(r,r),m)
    // end
    // return r

    //prevpow2(x::Unsigned) = (one(x)>>(x==0)) << ((sizeof(x)<<3)-leading_zeros(x)-1)

    fn prev_power_of_two(n: usize) -> usize {
        let bits = n.count_ones() + n.count_zeros();
        n.wrapping_shr(bits - n.leading_zeros() - 1).wrapping_shl(bits - n.leading_zeros() - 2)
    }

    if e == 0 { return 1 % m; }
    if m == 1 { return 0; }

    let mut t = prev_power_of_two(e);
    let mut r = 1;

    loop {
        if e >= t {
            r = (r * b) % m;
            e -= t;
        }

        t = t.shr(1);
        if t <= 0 { break; }
        r = (r * r) % m;
    }

    r
}