# 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));
}
}``````

## 2 Replies to “Modular Exponentiation”

1. Rajat kushwaha says:

a“Nice info!”
“Great share!”
“Useful post”
“Amazing write-up!”

1. Mahesh Deshmane says:

Thanks