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

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

you can use repeated squaring
it basically depends on the fact 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;
}
``````

2 Likes
``````
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;

}

``````
``````
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;

}

``````

for large prime, replace int with long long

for large prime, replace int with long long