# 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. *36078 ^{267 } 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 ^{267 } 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 ^{97} mod 10*

So will start with *3 ^{1}, 3^{2}, 3^{4}, 3^{8},3^{16}, 3^{32}, 3^{64}*; As

*3*is greater than

^{128}*3*

^{97}^{ }so will stop at

*3*

^{64}^{.}

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

*3*^{1 }mod 10 = 3*3*(will consider smaller number so will divide 9 – 10 =-1 as need remainder but we can use 9 also both will give same result)^{2 }mod 10 => 3^{1 }X 3^{1}mod 10 => 3 X 3 mod 10 = 9*3*^{4 }mod 10 => 3^{2 }X 3^{2}mod 10 => -1 X -1 mod 10 = 1*3*^{8 }mod 10 => 3^{4 }X 3^{4}mod 10 => 1 X 1 mod 10 = 1*3*^{16}mod 10 =>3^{8}X 3^{8 }mod 10 => 1 X 1 mod 10 = 1*3*^{32}mod 10 =>3^{16}X 3^{16 }mod 10 => 1 X 1 mod 10 = 1*3*^{64}mod 10 =>3^{32}X3^{32 }mod 10 => 1 X 1 mod 10 = 1

As we have all calculation ready will use 2-base system to calculate *3 ^{97}*

*3 ^{97 }=^{ (}3^{64 }X 3^{32 }X 3^{1)}*

*3 ^{97 }=^{ (}1X 1X 3^{)}*

*3 ^{97 }= 3*

*3 mod 10 = 3*

So final answer for problem *3 ^{97} 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();
}
}
```

a“Nice info!”

“Great share!”

“Useful post”

“Amazing write-up!”

Thanks