Advertisements
Home > Information Technology, programming, Science, Security > Fast Exponentiation: Solution to Huge Modulo Exponentiation

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 ab 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 2201 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 1038.  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 10308.  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 104932. This also includes the negative numbers.  It uses 10 bytes of memory and has a 19 digit precision.

Well, you can solve your 2201 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 za can be described as za1 + za2 + za3 + … +zan. 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, 521 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;
}
Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: