Given your formula and a the following variation:
(A + B) mod C = ((A mod C) + (B mod C)) mod C
You can use the divide and conquer approach to develope an algorithm that is both easy and fast:
#include <iostream>
long bigMod(long a, long b, long c) {
if (a == 0 || b == 0) {
return 0;
}
if (a == 1) {
return b;
}
if (b == 1) {
return a;
}
// Returns: (a * b/2) mod c
long a2 = bigMod(a, b / 2, c);
// Even factor
if ((b & 1) == 0) {
// [((a * b/2) mod c) + ((a * b/2) mod c)] mod c
return (a2 + a2) % c;
} else {
// Odd exponent
// [(a mod c) + ((a * b/2) mod c) + ((a * b/2) mod c)] mod c
return ((a % c) + (a2 + a2)) % c;
}
}
int main() {
// Use the min(a, b) as the second parameter
// This prints: 27
std::cout << bigMod(64545, 58971, 144) << std::endl;
return 0;
}
Which is O(log N)