Use modular arithmetic to compute power. [ (a mod p) (b mod p) ≡ (ab) mod p ] // Calculate (x^n)%p in O(logy) int power(int x, unsigned int y, int p) { // Initialize result int res = 1; // Update x if it is more than or equal to p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) { // y must be even now res = (res*x) % p; } // y = y/2 y = y>>1; x = (x*x) % p; } return res; }