c - Function's return value is unexpected

Question

long long encrypt(int message,int n,int e)
{
long long s=pow(message,e);
return s%n;
}

When I try this:

        printf("%lli",encrypt(65,3233,17));

It prints out this: -2631

Does anyone have any idea how to fix this...To be honest those are small values for now..I think I'll use larger values in the future

Answer 1

A long long is probably 64 bits on your system. The biggest (decimal) number you can put in it is 9,223,372,036,854,775,807. You're trying to put 65¹⁷ in one - that's 6,599,743,590,836,592,050,933,837,890,625. Overflow!

You need to use some kind of big number library to do these kinds of operations with perfect precision. There are many available - GMP, for example.

Answer 2

Perhaps this will do:

int encrypt(int message,int n,int e)
{
    int s = 1;
    while (e--) {
        s = ( s * message ) % n;
    }
    return s;
}

Answer 3

We have Theorem as follows in Mathmatics: *(a*b)%p =(a%p*b%p)%p* So we can get this:

*(a^e)%n=(a(e-1)%p*a%p)%p*

so we can get code like this:

int encrypt(int message,int n,int e)
{
    int result = 0;

    if(1 == e)
    {
       return message%n;
    }
    else
    {
       result = encrypt(message,n,e-1);
    }

    return (result%p * message%p)%p;

}