Modular Exponentiation

By Nikolay Blagoev

As you might have seen in our other articles, modern (asymmetric) cryptography relies on computing REALLY LARGE numbers to the power of another EVEN LARGER number modulo even another LARGE NUMBER. Obviously if you just tried to compute something like 2914136638394424429219 mod 52413328923451 even a computer might break a sweat. But there is a very simple algorithm, which makes these computations a lot faster to compute, and once you learn it even you will be able to perform such calculations without the need of a calculator

Some Preliminaries

Every number on your computer, every piece of information, is stored as bits - a sequence of 0s and 1s. For numbers, this means that they are stored in base 2 (as opposed to the normal base 10 we use in our day to day lives). Let us do a quick comparison. If you use base 10 to write the number 317, the number you are actually expressing is:

317 = 3*102 + 1*101 + 7*100

So in human terms you have 3 hundreds (102 = 100 = a hundred), 1 10 (101 = 10 = a ten), and 7 ones (100 = 1 = a one). In general, every number is some base (b) is actually = (number in last position)*b0 + (number in second to last position)*b1 + (number in third to last position)*b2 + (number in fourth to last position)*b3 +....

As you can see you start back to front (technically least significant to most significant is the proper term) and you increase the exponent of the base by 1 for which new position, starting from 0. A number in binary representation (base 2) is nothing different than a number in base 10. We are just used to base 10 more in our day to day lives. We could have just as easily ended up with base 12, as old civilizations often relied on such a system for their computations [1]

So the number 317 in binary is 100111101. And we can verify that as:

317 = 1*28 + 0*27 + 0*26 + 1*25 + 1*24 + 1*23 + 1*22 + 0*21 + 1*20
317 = 256 + 32 + 16 + 8 + 4 + 1
317 = 288 + 24 + 5

The Algorithm

So the algorithm goes as follows:

  1. Want to compute ae mod p
  2. Present exponent (e) in binary form
  3. Initialise result variable to 1
  4. Initialise a as the number you are trying to exponentiate, modulo p (a = a mod p)
  5. Starting left-to right on e in binary form for each bit:
  6.  if bit in that position is 1 result = (result * a) mod p
  7.  a = a2 mod p

Let's go through a simple example:

  1. Want to compute 711 mod 13
  2. Present exponent (e) in binary form = 1011
  3. Initialise result variable to 1
  4. Initialise a as the number you are trying to exponentiate, modulo p (a = 7 mod 13 = 7)
  5. Starting left-to right on e in binary form for each bit:
  6.  bit in position 0 is 1, so result = (result * a) mod p = (1 * 7) mod 13 = 7
  7.  a = a2 mod p = 72 mod 13 = 49 mod 13 = 10
  8.  bit in position 1 is 1, so result = (result * a) mod p = (7 * 10) mod 13 = 5
  9.  a = a2 mod p = 102 mod 13 = 100 mod 13 = 9
  10.  bit in position 2 is 0, so result doesn't change
  11.  a = a2 mod p = 92 mod 13 = 81 mod 13 = 3
  12.  bit in position 3 is 1, so result = (result * a) mod p = (5 * 3) mod 13 = 2
  13.  a = a2 mod p = 32 mod 13 = 9 mod 13 = 9
  14. Result is 2

Below you can find an interactive example:

A:

Exponent:

Modulo: