How to calculate the mod of large exponents?

Question

For example I want to calculate (reasonably efficiently)

2^1000003 mod 12321

And finally I want to do (2^1000003 - 3) mod 12321. Is there any feasible way to do this?

Answer 1

Basic modulo properties tell us that

1) a + b (mod n) is (a (mod n)) + (b (mod n)) (mod n), so you can split the operation in two steps

2) a * b (mod n) is (a (mod n)) * (b (mod n)) (mod n), so you can use modulo exponentiation (pseudocode):

x = 1
for (10000003 times) {
    x = (x * 2) % 12321; # x will never grow beyond 12320
}

Of course, you shouldn't do 10000003 iterations, just remember that 2^1000003 = 2 * 2^1000002 , and 2^1000002 = (2⁵⁰⁰⁰⁰¹)² and so on...

Answer 2

Well in Java there's an easy way to do this:

Math.pow(2, 1000003) % 12321;

For languages without the Math.* functions built in it'd be a little harder. Can you clarify which language this is supposed to be in?

Answer 3

In some reasonably C- or java-like language:

def modPow(Long base, Long exponent, Long modulus) = {
  if (exponent < 0) {complain or throw or whatever}
  else if (exponent == 0) {
    return 1;
  } else if (exponent & 1 == 1) { // odd exponent
    return (base * modPow(base, exponent - 1, modulus)) % modulus;
  } else {
    Long halfexp = modPow(base, exponent / 2, modulus);
    return (halfexp * halfexp) % modulus;
  }
}

This requires that modulus is small enough that both (modulus - 1) * (modulus - 1) and base * (modulus - 1) won't overflow whatever integer type you're using. If modulus is too large for that, then there are some other techniques to compensate a bit, but it's probably just easier to attack it with some arbitrary-precision integer arithmetic library.

Then, what you want is:

(modPow(2, 1000003, 12321) + (12321 - 3)) % 12321