## Fast Exponentiation: Solution to Huge Modulo Exponentiation

This is actually the subject I’ve learned in the computer security class. The problem was that how can a computer solve a^{b} mod c? The simplest thing might be to use the Math class in C++, which you can derive to be Math.exp(a,b) % c. However, things will get out of hand for huge exponentiation. Take 2^{201} for an example, this will yield an incorrect result if you use either integer or float. Since number types in C++ is kind of a cycle, they will return to their lowest value if it exceeds the allowed value. Just for reference, I will list the amount limit of every number types:

**int** : -32 768 to 32 767. It uses 2 bytes of memory.

**unsigned int** : 0 to 65 535. It uses 2 bytes of memory.

**long** : -2 147 483 648 to 2 147 483 647. It uses 4 bytes of memory.

**unsigned long** : 0 to 4 294 967 295. It uses 4 bytes of memory.

**float** : 3.4 x 10^{-38} to 3.4 x 10^{38}. This also includes the negative numbers. It uses 4 bytes of memory and has a 7 digit precision..

**double** : 1.7 x 10^{-308} to 1.7 x 10^{308}. This also includes the negative numbers. It uses 8 bytes of memory and has a 15 digit precision.

**long double** : 3.4 x 10^{-4932} to 1.1 x 10^{4932}. This also includes the negative numbers. It uses 10 bytes of memory and has a 19 digit precision.

Well, you can solve your 2^{201} by using a double or long double type. However, they have a number limitation which only allows limited number variables. What if we want to calculate a bigger number which exceeds the limit of the long double?

Fast exponentiation is the answer. Here’s the theory behind the algorithm:

If a = a1 + a2 + a3 + … + an, where a is a square exponent, then z^{a} can be described as z^{a1} + z^{a2} + z^{a3} + … +z^{an}. For an example,

To illustrate with 5^21: 1) 21 = 16 + 4 + 1 2) 5^1 = 5 5^2 = 5*5 = 25 5^4 = 25 * 25 = 625 5^8 = 625 * 625 = 390625 5^16 = 390625 * 390625 = 152587890625 3) 5^21 = 5^16 * 5^4 * 5 = 476837158203125

But this doesn’t solve our problem right? So, we have to add another theorem called Fermat’s theorem. Take the same equation again, 5^{21} mod 19 as an example. Just like above, You can use the result of the previous computation to compute the next computation eventhough you have a modulo on you. Here’s what I meant:

1) 21 = 16 + 4 + 1 2) 5^1 mod 19 = 5 5^2 mod 19 = 5*5 mod 19= 6 5^4 mod 19 = 6 * 6 mod 19 = 17 5^8 mod 19 = 17 * 17 mod 19 = 4 5^16 mod 19 = 4 * 4 mod 19= 16 3) 5^21 mod 19= 5^16 mod 19 * 5^4 mod 19 * 5 mod 19 = (16 * 17 * 5) mod 19 = 11

In conclusion, you will supress the the modulo exponentiation not to be larger than the modulo itself. Therefore you can save some memory by only using integer or unsigned integer as your number type. If you are interested in the C++ code of this implementation, you can copy & paste the code below:

/***************************************************** * Implementation of Fast Exponentiation Algorithm * * An Assignment of Chapter 8 Programming Problem 8.22* * Author: Souza Nurafrianto W.P. * * ID: 1-2205-033 * ******************************************************/ #include <cstdlib> #include <conio.h> #include <iostream> #include <cstdio> #include <stdio.h> #include <string.h> #include <math.h> #include <time.h> int main(int argc, char *argv[]) { int base, exp, mod, y = 1; printf("base = "); scanf("%d",&base); printf("exponent = "); scanf("%d",&exp); printf("mod = "); scanf("%d",&mod); int a = base,b = exp; while(0 < b) { if(b % 2 == 1) { printf("%d * %d mod %d = %d\n",a,y,mod,(a * y) % mod); y = (a * y) % mod; } b = (int)round(b/2); a = (a*a) % mod; } printf("\n%d^%d mod %d = %d\n",base,exp,mod,y); system("PAUSE"); return EXIT_SUCCESS; }

## Comments