Implement exponentation for BigInt about num HOT 7 CLOSED

#56 is similar to this.

from num.

Why not just use num::pow?

For modular exponentiation, here is a working implementation:

/// Calculate base^exp (mod modulus).
fn powm(base: &BigInt, exp: &BigInt, modulus: &BigInt) -> BigInt {
    let zero = Integer::zero();
    let one: BigInt = Integer::one();
    let two = &one + &one;
    let mut exp = exp.clone();
    let mut result = one.clone();
    let mut base = base % modulus;
    if exp < zero {
        exp = -exp;
        base = inverse(base, modulus).unwrap();
    }
    while exp > zero {
        if &exp % &two == one {
            result = (result * &base) % modulus;
        }
        exp = exp >> 1;
        base = (&base * &base) % modulus;
    }
    result
}

For negative powers more machinery is needed (namely the extended Euclidean algorithm for inverting the base). See here.

from num.

Why not just use num::pow?

My application needs negative and/or non-integer powers (but not modular arithmetic). If I use this powm implementation, but simply remove the modulus parameter and drop all … % modulus, will the result work correctly?

from num.

It sounds like you want big floats? That is not possible with num. You might want to have a look at rust-gmp.

from num.

@nejucomo I think that big fixed and floating point arithmetic is no goal for num crate. However it can happen that there will be additional library "blessed" by rust-num organization.

from num.

Why not just use num::pow

I think there probably was a good reason back in Jan. 2015, but I don't remember it now.

For modular exponentiation, here is a working implementation:

Can you make a PR with that?

from num.

There is BigUint::modpow now. If you need more, please open an issue on the new repo:
https://github.com/rust-num/num-bigint/issues

from num.