Modular exponentiation

We shall now learn how to compute a^b (mod m) where a, b and m are given numbers. The main problem is as for modular multiplication: we cannot compute a^b directly as it might be too large.

We have already learned from modular multiplication that we should break the problem into steps, and perform modul reduction after each step. This prevents the numbers from growing too much. The question is: How to break up the computation of a^b into steps.

A simple way to compute a^b step by step is to compute a, a², a³ and so on, performing modular reduction at each step. This works, but if b is too large (say, 100 digits) this will take l...o...n...g!!!

We shall now learn another way to break the problem into steps. For this we start by expressing the number b in binary. Let the bits of b be

b_k-1, b_k-2, ..., b₁, b₀.

Example: If b=53 we shall write (using k=8 bits, say)
b = (00110101)₂.
Thus here
b₀ = 1 b₁ = 0 b₂ = 1 b₃ = 0 b₄ = 1 b₅ = 1 b₆ = 0 b₇ = 0

Then

b = b₀ 2⁰ + ..., + b_k-1 2^k-1,

and so

a^b = (c₀)^b₀ (c₁)^b₀ ... (c_k-1)^b_k-1.

where

c_i = a^2ⁱ.

Observe that

c₀ = a

and

c_i = c_i-1 ²

We shall perform all the computation modulo m.

Example: Taking a=3 we comoute c_i's as follows (with k=8 and m=6254):
c₀ = 3 c₁ = 9 c₂ = 81 c₃ = 307 c₄ = 439 c₅ = 5101 c₆ = 3561 c₇ = 3863 c₈ = 725

Now observe that the product in (**) is basically the product of those c_i's for which b_i's are 1.

Example: In our example, b₀ = b₂ = b₄ = b₅ = 1. So we need to form the product
c₀ c₂ c₄ c₅ (mod m).

c₀ c₂ = 3 * 81 = 243 (c₀ c₂) c₄ = 243 * 439 = 359 (c₀ c₂ c₄) c₅ = 359 * 5101 = 5091
Thus we finally see that
3⁵³ = 5091 (mod 6254).

Let us package this as a C function that we can use later:


unsigned int modExpo(unsigned int a, unsigned int b, unsigned int m) {
  unsigned int ans, ci;

  ci = a % m;
  ans = 1;
  for(i=0;i<k;i++) {
    ci = modMult(ci, ci, m);
    if((b & (1<<i)) != 0) {
      ans = modMult(ans, ci, m);
    }
  }  

  return ans;
}

Testing

Here is a complete C program ready to be compiled and run:


#include <stdio.h>
int k = 32;
unsigned int modMult(unsigned int a, unsigned int b, unsigned int m) {
  unsigned int ans, ci;

  di = a % m;
  ans = 0;
  for(i=0;i<k;i++) {
    di = (ci << 1) % m;
    if((b & (1<<i)) != 0) {
      ans = ans + di;
    }
  }  

  return ans;
}
unsigned int modExpo(unsigned int a, unsigned int b, unsigned int m) {
  unsigned int ans, ci;

  ci = a % m;
  ans = 1;
  for(i=0;i<k;i++) {
    ci = modMult(ci, ci, m);
    if((b & (1<<i)) != 0) {
      ans = modMult(ans, ci, m);
    }
  }  

  return ans;
}

main() {
  unsigned int y;

  y = modExpo(3,53,6254);
  printf("3 to the power 53 = %u mod 6254.\n",y);
}

Where do we stand?

In this and the last page we have learned how to perform modular multiplication and modular exponentiation. These are important building blocks in many cryptosystems, including RSA.

We shall not extend these algorithms any further. In the next page we shall learn how to compute gcd of two numbers using the Extended Euclidean Algorithm. This algorithm has nothing to do with modular multiplication or exponentiation.