Modular Exponentiation in C++

Modular Exponentiation is way of calculating the remainder when dividing an integer b (Base) by another integer m (Modulus) raised to the power e(Exponent). Fast modular exponentiation of large numbers is used all the time in RSA to encrypt/decrypt private information over the internet. Whenever you go to a secure site you are using RSA which deals with modular exponentiation.So lets understand modular exponentiation with c++!

be (mod m)

b = 32

e = 2

m = 5

32^2 = 1024 / 5 has a remainder of 4

But what if we are dealing with very large numbers? Calculating the be then (mod m) can be very expensive operations. That’s why modular exponentiation is so wonderful. Take the following problem

b = 1819

e = 13

m = 2537

1819^13 (mod 2537). First step we will convert the exponent 13 into binary: 2^0 + 2^2 + 2^3 = 1101    Starting with the least significant bit we will do the following: If the bit is 1  then x = x * b (mod m). At each step b (base) changes regardless if the exponent bit is 0 or 1.  b = b2 (mod m).  Continue this while there are still bits left. Then x is your answer.

Exp———–x———————- Base Computation

1          x = 1819          1819^2 (mod 2537) = 513

0          x = 1819          513^2    (mod 2537) = 1858

1          x = 418            1858^2 (mod 2537) = 1844

1          x = 2081

As you can see using this method uses extremely less computation. If you can understand this than you are one step closer to understanding RSA! With the algorithm above it shouldn’t be difficult to write a program that will compute modular exponentiation with very large integers. I have included my program and like always am up for your suggestions!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*****************************************************************************
* Finds m^e mod n using modular exponenation
*******************************************************************************/

int modExp(int b, int e, int m)
{
int remainder;
int x = 1;

while (e != 0)
{
remainder = e % 2;
e= e/2;

if (remainder == 1)
x = (x * b) % m;
b= (b * b) % m; // New base equal b^2 % m
}
return x;
}

4 comments on “Modular Exponentiation in C++

  1. It seems too complicated and very broad for me. I’m looking forward for your next post, I’ll try to get the hang of it!

  2. Nice post. I was checking continuously this blog and I’m impressed! Very useful info specially the last part 🙂 Thank you and good luck.

  3. Thanks for the blog loaded with so many information. Stopping by your blog helped me to get what I was looking for. I found your site in yahoo. And I will be back next time, thank you.

  4. I was looking through some of your blog posts on this website and I conceive this internet site is very instructive! Keep on putting up.

Leave a Reply

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