Raising a number to a huge exponent

Question

I am given the number 3 and a variable 'n', that can be as high as 1 000 000 000 (a billion). I have to print the answer of 3^n modulo 100003. I tried the following:

1. I tried using the function std::pow(3,n), but it doesn't work for large exponents(can't apply the modulo during the process).
2. I tried implementing my own function that would raise the number 3 to the power n so I could apply the modulo when needed, but when tested with very large numbers, this method proved to be too slow.

3. Lastly I tried prime factorization of the number 'n' and then using the factors of 'n' (and how many times they appear) to build back the answer and this seems like the best method that I could come up with (if it is correct). The problem is what would I do for a huge number that is already prime?

   So these were the ideas that I had, if anyone thinks there's a better way (or if one of my methods is optimal), I would appreciate any guidance.

Answer 1

Take advantage of property of modular arithmetic

(a × b) modulo M == ((a module M) × (b modulo M)) modulo M

By using above multiplication rule

(a^n) modulo M 
= (a × a × a × a ... × a) modulo M 
= ((a module M) × (a modulo M) × (a modulo M) ... × (a modulo M)) modulo M

Calculate the result by divide and conquer approach. The recurrence relation will be:

f(x, n) = 0                     if n == 0

f(x, n) = (f(x, n / 2))^2       if n is even
f(x, n) = (f(x, n / 2))^2 * x   if n is odd

Here is the C++ implementation:

int powerUtil(int base, int exp, int mod) {
    if(exp == 0) return 1;
    int ret = powerUtil(base, exp / 2, mod) % mod;
    ret = 1LL * ret * ret % mod;
    if(exp & 1) {
        ret = 1LL * ret * base % mod;
    }
    return ret;
}

double power(int base, int exp, int mod) {
    if(exp < 0) {
        if(base == 0) return DBL_MAX; // undefined
        return 1 / (double) powerUtil(base, -exp, mod);
    }
    return powerUtil(base, exp, mod);
}

Answer 2

This is to augment Kaidul's answer.

100003 is a prime number, which immediately casts in the Fermat's Little Theorem: any number raised to a prime power is congruent to itself modulo that prime. It means that you don't need to raise to n'th power. A n % 100002 power suffices.

Edit: example.

Say, n is 200008, which is 100002 * 2 + 6. Now,

3 ^ 200007 =
3 ^ (100002 + 100002 + 6) = 
3 ^ 100002 * 3 ^ 100002 * 3 ^ 6

FLT claims that (3 ^ 100002) % 100003 == 1, and the last line above, modulo 100003, reduces to 3 ^ 6. In general, for a prime p,

(k ^ n) % p == k ^ (n % p)

Of course, it only speeds the computation if the exponent n is greater than p. As per your request (exponent 100, modulo 100003) there is nothing to reduce. Go straight to the Kaidul's approach.