RSA encryption

[Oromis]

I'm trying to write a simple program to encrypt a text using RSA. P and Q should be under the hundred:

const int e = 4909;
const int N = 5893; //71*83
//...
string text;
//...
for (int i=0;i<text.length();i++)
{
    int value = (int)pow((int)text[i],e)%N;
    //...
}

But this results in a negative value. I guess because the number becomes to big, so I tried the following:

long double temp_e = e;
long double value  = (int)text[i];
while (temp_e > 4)
{
   temp_e/=2;
   value = (int)pow(value,2)%N;
}
value = (int)pow(value,temp_e)%N

But this doesn't work either. Can anyone help me out here?

[jsmith]

You're going to have to rethink your formula because you are correct -- you are
experiencing overflow when raising a number to the 4909 power.

Simple thought experiment. Let's say we want to do (3^4) % 5

3 * 3 == 9. 9 == 1 * 5 + 4, or in other words (3^2) % 5 = 4.

3 * 3 * 3 == 9 * 3 == ( 1 * 5 + 4 ) * 3 == 3 * 5 + 12 == 5 * 5 + 2, or in other words (3^3) % 5 == 2.

Notice that the remainder modulo 5 is a function entirely of the remainder modulo 5 of the
previous multiplication. This means that you can write your own pow_mod() function that
performs (a^b) % c in the following way:


answer = a;
repeat b - 1 times:
answer = ( answer * a ) % c;
return answer;


If you use unsigned integers for your multiplications, you can be guaranteed that you will
not experience overflow as long as a * a < 2^32, or a < 2^16 (65536).

[Oromis]

Thanks! I used your algorithm and it works perfectly.