How can we compute modular arithmetic with large divisor and exponent?

Question

Example:

(30000000^30000000) mod 40000000 = ?

I have been using Euler theory and properties of exponents but still cannot get the answer Anyone know how to calculate this by just theories and simple calculator?

My trial is to reduce the exponent of the 30000000 by the Fermat's Little Theorem but the exponent is still too large for the calculator to compute.

Answer 1

You use the halving-and-squaring approach to power computation and reduce in every step the intermediate result modulo the given divisor.

You can also use negative remainders to get somewhat smaller intermediate results.

Note also that n=40000000=4*10^7=2^9*5^7 is a composite number, so the Euler totient function gives phi(n)=2^8*4*5^6=16*10^5=160000. Now reduce the exponent mod phi(n)-1 first.

This last method only works if you know the factorization of the divisor.

Answer 2

# b^e (mod m)
function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
        b := (b * b) % m
        e := floor(e / 2)
    return x