Modular Exponentiation

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. 36078267  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 36078267  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 397 mod 10

So will start with 31, 32, 34, 38,316, 332, 364; As 3128 is greater than 397 so will stop at 364.

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

  • 3mod 10 = 3
  • 3mod 10 => 31  X  31 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)
  • 3mod 10 => 32  X 32 mod 10    => -1 X -1 mod 10  = 1
  • 38  mod 10 => 34  X 34   mod 10 => 1 X 1 mod 10     = 1
  • 316 mod 10 =>38 X 38  mod 10   => 1 X 1 mod 10     = 1
  • 332 mod 10 =>316 X 316  mod 10 => 1 X 1 mod 10     = 1
  • 364 mod 10 =>332 X332  mod 10 => 1 X 1 mod 10     = 1

As we have all calculation ready will use 2-base system to calculate 397

397 = (364  X 332 X 31)

397 = (1X 1X 3)

397 = 3

3 mod 10 = 3

So final answer for problem 397 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();
   }
}

2 Replies to “Modular Exponentiation”

Leave a Reply

Your email address will not be published. Required fields are marked *