How to calculate a^b mod p i.e.(a^b%p) where p is a big prime number of the order 10^9....

general
, , ,
1

i have some knowldege of fermats little theorem but for that i think ‘b’ must be of the form : b=k*(p-1) + m…and the answer would be a^m…but in my case ‘b’ is smaller than p for example b is 10^7(so i cant express ‘b’ in terms of ‘p’) …??
By simply writing the expression it is overflowing the long long int range …plz help

2

you can use repeated squaring
it basically depends on the fact

alt text

you can use code:-

int mod = 1000000007
int powmod(int base,int pow)
{
   int res=1;
   while(pow)
   {     
         if (pow%2!=0)  res=(res*base)%mod;
         base=(base*base)%mod;
         pow/=2;
   }
   return res;
}

you can get more information from wiki-Exponentiation by squaring

2 Likes
3 

MOD 1000000007

int expo(int base,int power)
{
      int result=1;
      while(power)
      {
            if(power&1)
                   result=(result*base)%MOD;
            base=(base*base)%MOD;
            power>>=1;
      }
      return result;

}
4 

 MOD 1000000007
int square(int a)
{
     return (a*a)%MOD;
}
int expo(int base,int power) 
{ 
     if(power==1)
         return base;
     else if(power&1)
         return (base*expo(base,power-1)) % MOD;
     else
         return square(expo(base,power/2))%MOD;

}
5

for large prime, replace int with long long

6

for large prime, replace int with long long