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...