Modular Exponentiation as also known as repeated sequence algorithm which performs exponentiation over modulus. Which essential in computer cryptosystems.

A typical problem related to cryptography involves exponentials with a very large number

e.g. 36078²⁶⁷  mod 17.

To perform these very large number calculation we need an efficient approach. The approach should be a time-efficient and memory-efficient approach. As directly calculating (36078 * 267 mod 17) might result in overflow issues also time consuming in some cases.

So, the modular exponentiation algorithm computes 36078²⁶⁷  mod 17 without computing 36078 * 267 operation. Modular Exponentiation provides an efficient way to compute modules operation on a large number which is time effective and memory competent.

To understated modular exponentiation will take a small example

Let’s calculate 3⁹⁷ mod 10

So will start with 3¹, 3², 3⁴, 3⁸,3¹⁶, 3³², 3⁶⁴; As 3¹²⁸ is greater than 3⁹⁷ so will stop at 3^64.

Now let’s calculate mod for each power of 3’s

• 3¹ mod 10 = 3
• 3² mod 10 => 3¹  X  3¹ mod 10    => 3 X 3 mod 10    = 9 (will consider smaller number so will divide 9 – 10 =-1 as need remainder but we can use 9 also both will give same result)
• 3⁴ mod 10 => 3²  X 3² mod 10    => -1 X -1 mod 10  = 1
• 3⁸  mod 10 => 3⁴  X 3⁴   mod 10 => 1 X 1 mod 10     = 1
• 3¹⁶ mod 10 =>3⁸ X 3⁸  mod 10   => 1 X 1 mod 10     = 1
• 3³² mod 10 =>3¹⁶ X 3¹⁶  mod 10 => 1 X 1 mod 10     = 1
• 3⁶⁴ mod 10 =>3³² X3³²  mod 10 => 1 X 1 mod 10     = 1

As we have all calculation ready will use 2-base system to calculate 3⁹⁷

3⁹⁷ = ⁽3⁶⁴  X 3³² X 3¹⁾

3⁹⁷ = ⁽1X 1X 3⁾

3⁹⁷ = 3

3 mod 10 = 3

So final answer for problem 3⁹⁷ mod 10 is 3

Because modular exponentiation is an essential operation in computer science, many programming languages have dedicated function to perform modular exponentiations

.Net Framwork – BigInteger Class has a ModPow() method to perform modular exponentiations.

Java – java.math.BigInteger Class has a ModPow() method to perform modular exponentiations.

C# implementation of ModPow() Method

using System;
using System.Numerics;
 
public class ModularExponentiation
{
   public static void Main()
   {
      BigInteger number = 3;
      int exponent = 97;
      BigInteger modulus = 10;
      Console.WriteLine("({0}^{1}) Mod {2} = {3}",
                        number, exponent, modulus,
                      
                  BigInteger.ModPow(number, exponent, modulus));
      Console.ReadLine();
   }
}