problem with Modular exponentiation

Consider a code for Modular exponentiation
assume we are calculating (x^n)% MOD

    result = (result*x)%MOD;


suppose x = 4 and n is large say 100 and MOD is 10^9 +6

so my program has overflow and giving result in -ve number
so in this program x can be very large < MOD
and when we multiply it be result intermediate value is very large so how to do it

p.s i am newbie :slight_smile:

Let say, you need to calculate (x * y) % MOD as some intermediate step.

Use ((x % MOD) * (y%MOD)) % MOD.

By doing this, both the terms will be less than MOD.

Now the intermediate result can be as large as (MOD^2). So make sure you either store the intermediate result in the suitable datatype or typecast it accordingly.

An example of typecasting in such cases. For eg.

res = (int)((long long)x * x) % MOD;

This will make sure that your result never overflows. This works for those cases where MOD fits in a 32 bit integer. If the MOD is larger, then you can use your own multiplication by using repeated addition in a O(log(multiplier)) method.
If the MOD is still larger(does not fit 64 bits), you will have to implement your own BigInteger.


Hi Mukul. Thanks for the article but there is one correction you need to do.
res = (int)((long long)x * x)%MOD must be changed to res = (int)(((long long)base*base)%MOD);

for x = 1000000000 and n=2. The first version gives the wrong answer because of overflow while typecasting from long long to int. But instead, typecasting must be done after taking the modulo.