# Modular Exponentiation

By | August 19, 2015

# Modular Exponentiation

(Raising to a Power with a modulus)

E.g. To find 1113 mod 53

13 = 8 + 4 + 1   so  1113 = 118+4+1 = 118 * 114 * 111

We can compute successive squares of 11 to obtain 11, 112, 114, 118  and then multiply together 111 * 114 * 118 to get the answer 1113 .Because we are working mod 53, we will “take mods” at every stage of the calculation.

Thus we have:

11 mod 53 = 11

112  =  121,  121 mod 53 = 121 – 2*53 = 15

114 = (112)2 = 152 mod 53 = 225 mod 53 = 225 – 4*53 = 13

118 = (114)2 = 132 mod 53 = 169 mod 53 = 169 – 3*53 = 10

Therefore 1113 mod 53 = 11 * 13 * 10 = 1430  mod 53 = 1430 – 26*53 = 52

The answer is 1113 mod 53 = 52

This method of computing modular exponentiations can be formalised into an algorithm as follows:

Psuedocode to compute xn mod p
Here the u value is the successive squaring of x, and the y value is the multiplication together of the required squared values of x.

```Initialise  y=1; u=x mod p;
Repeat
If n is odd then y:=(y*u) mod p;
n:=n div 2;
u:=(u*u) mod p;
Until n==0;
Output y;```

To compute 1113 mod 53 using this algorithm:

 y u n 1 11 13 11  (1*11 mod 53) 15     (112 mod 53) 6      (13 div 2) 11 ( n even, y doesn’t alter) 13     (152 mod 53) 3       (6 div 2) 37  (11*13 mod 53) 10     (132 mod 53) 1       (1 div 2) 52  (37 * 10 mod 53) 0       (1 div 2)

Here is the working code:

```#include <iostream>
using namespace std;

void ModularExponention(int x,int n,int p)
{
int y=1,u=x%p;
while(n)
{
if(n&1) // to check if last bit is 1 or not
{
y=(y*u)%p;
}
n>>=1;
u=(u*u)%p;
}
cout<<"The Answer using Modular exponentiation is "<<y;
}

int main() {
int x=11,n=13,p=53;
ModularExponention(x,n,p);
return 0;
}```

Time Complexity: O(log N) // N is the exponent
This comes considering the fact that we only run the loop, till we have bits left in the exponent.

Output:

`The Answer using Modular exponentiation is 52`

Here is the same code with different variable names:

```LL ModularExponentiaion(LL x,LL n,LL p)
{
LL ans=1,temp=x%p;
while(n)
{
if(n&1) // to check if last bit is 1 or not
{
ans=(ans*temp)%p;
}
n>>=1;
temp=(temp*temp)%p;
}
return  ans;
}```