overflow problem

[macronin]

Hi there,
I have included code for a function called powermod which performs the following equation a^b mod(N), in which a, b and N are all defined as longs. However when I use large values for b, the function overflows and returns a wrong value. Does anyone know if there is a way around this?

// powermod function
// -----------------
// this function raises a number (value) to a power, under a given
// modulus.

long powermod(long value, long power, long modulus)
{
int temp;
long ret(1);
long t_value;

for(unsigned int i = 0;i < (sizeof(power)*8);++i)
{
if (i == 0)
{
t_value = value;
}

else
{
t_value *= t_value;
t_value %= modulus;
}

temp =((power >> i) & 1);
if ( temp == 1)
{
// the ith bit is 1, so we are going to
// need to include this t value in our
// answer.

ret *= t_value;
ret %= modulus;
}
}

return ret;
}

 

[Jeffray]

you can try the modulus before the multiplication:

t_value %= modulus;
t_value *= t_value;

It will be better.

 

[chipperMDW]

I don't know about it being &quot;better,&quot; but it would certainly be incorrect. (a^b) mod n is not the same thing as (a mod n)^b.

Try to find a HugeInt class. It's possible one came with your compiler. If not, one should be easy to find on the web.

 

[Jeffray]

Actually I would like to do the calculation of (a mod n) ^ b mod n, which should be the same as (a^b) mod n. Maybe I should do the modulus again before the function returns.

 

[chipperMDW]

(a mod n)^(b mod n) still doesn't work. If you play around with it, there might be an expression that works, but that's not it.