Modular Exponentiation (Power in Modular Arithmetic)

Given three numbers x, y and p, compute (xy) % p.

Examples

Input:  x = 2, y = 3, p = 5
Output: 3
Explanation: 2^3 % 5 = 8 % 5 = 3.

Input:  x = 2, y = 5, p = 13
Output: 6
Explanation: 2^5 % 13 = 32 % 13 = 6.
 

We have discussed recursive and iterative solutions for power.

Below is discussed iterative solution.

/* Iterative Function to calculate (x^y) in O(log y) */ int power(int x, unsigned int y) {     int res = 1;     // Initialize result        while (y > 0)     {         // If y is odd, multiply x with result         if (y & 1)             res = res*x;            // n must be even now         y = y>>1; // y = y/2         x = x*x;  // Change x to x^2     }     return res; }

The problem with above solutions is, overflow may occur for large value of n or x. Therefore, power is generally evaluated under modulo of a large number.

Below is the fundamental modular property that is used for efficiently computing power under modular arithmetic.

(a mod p) (b mod p) ≡  (ab) mod p

or equivalently 

( (a mod p) (b mod p) ) mod p  =  (ab) mod p

For example a = 50,  b = 100, p = 13
50  mod 13  = 11
100 mod 13  = 9

11*9 ≡ 1500 mod 13
or 
11*9 mod 13 = 1500 mod 13

Below is C implementation based on above property.

// Iterative C program to compute modular power #include <stdio.h>   /* Iterative Function to calculate (x^y)%p in O(log y) */ int power(int x, unsigned int y, int p) {     int res = 1;      // Initialize result       x = x % p;  // Update x if it is more than or                 // equal to p       while (y > 0)     {         // If y is odd, multiply x with result         if (y & 1)             res = (res*x) % p;           // y must be even now         y = y>>1; // y = y/2         x = (x*x) % p;      }     return res; }   // Driver program to test above functions int main() {    int x = 2;    int y = 5;    int p = 13;    printf("Power is %u", power(x, y, p));    return 0; }

Output:

 Power is 6

Time Complexity of above solution is O(Log y).