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++!

b^e (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 b^e 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 = b² (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!