Find the last   40   decimal digits of   




a

b




{\displaystyle a^{b}}

,   where

   



a
=
2988348162058574136915891421498819466320163312926952423791023078876139


{\displaystyle a=2988348162058574136915891421498819466320163312926952423791023078876139}


   



b
=
2351399303373464486466122544523690094744975233415544072992656881240319


{\displaystyle b=2351399303373464486466122544523690094744975233415544072992656881240319}




A computer is too slow to find the entire value of   




a

b




{\displaystyle a^{b}}

.

Instead, the program must use a fast algorithm for modular exponentiation:   




a

b



mod


m


{\displaystyle a^{b}\mod m}

.

The algorithm must work for any integers   



a
,
b
,
m


{\displaystyle a,b,m}

,     where   



b
≥
0


{\displaystyle b\geq 0}

   and   



m
>
0


{\displaystyle m>0}

.




/* Add this line to the [dependencies] section of your Cargo.toml file:
num = "0.2.0"
*/
 
 
use num::bigint::BigInt;
use num::bigint::ToBigInt;
 
 
// The modular_exponentiation() function takes three identical types
// (which get cast to BigInt), and returns a BigInt:
fn modular_exponentiation<T: ToBigInt>(n: &T, e: &T, m: &T) -> BigInt {
    // Convert n, e, and m to BigInt:
    let n = n.to_bigint().unwrap();
    let e = e.to_bigint().unwrap();
    let m = m.to_bigint().unwrap();
 
    // Sanity check:  Verify that the exponent is not negative:
    assert!(e >= Zero::zero());
 
    use num::traits::{Zero, One};
 
    // As most modular exponentiations do, return 1 if the exponent is 0:
    if e == Zero::zero() {
        return One::one()
    }
 
    // Now do the modular exponentiation algorithm:
    let mut result: BigInt = One::one();
    let mut base = n % &m;
    let mut exp = e;
 
    // Loop until we can return out result:
    loop {
        if &exp % 2 == One::one() {
            result *= &base;
            result %= &m;
        }
 
        if exp == One::one() {
            return result
        }
 
        exp /= 2;
        base *= base.clone();
        base %= &m;
    }
}