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;
}