# How to calculate (a ^ b) % c

Could anyone give me a hint how to calculate (a ^ b) % c (with 2 <= a < 10^1000000, 1 <= b < 10^1000000, 2 <= c <= 10^9)?
I try to use this formula (a ^ b) % c = ((a % c) ^ (b % phi©) % c (phi© is Euler’s totient). But I realize that a and c aren’t coprime. Is it necessary that a and c must be coprime? Or we must use other formula.
Thank you! ^-^

2 Likes

Yes a and c should be coprime to use this formula. You can break c into prime powers. Compute the answer modulo p^k where p is prime. Now after doing this, you can use CRT to combine the answers using CRT.

2 Likes

I usually use a function to calculate it, by divide b into two part, and continue to do that in same function with b’ = b/2 (called “backtrack”).
Pseudo code:

``````func pow( int a, int b, int c)
{
If b=1 then exit with a%c;
//Divide b by 2:
pow = (pow (a, b/2, c) * (pow(a, b/2, c)) mod c;
//Case b is odd:
pow = (pow*a) mod c;
}
``````

That code I wrote depend on C++. You can change it into other languages, using quotes.

p.s: You are Vietnamese, right? I’m in Vung Tau.

upd1: I am not sure that what time limit of your problem is, but with b = 10000000000000000000000000000000000000000, if consumes about O(logb) ~ O(132), and I think that it could work with b <= 10^1000000.
upd2: a/b means that a div b.

You can learn CRT mostly from [it’s wikipedia article][1].

Break General modulo into prime power modulo’s
A summary: Basically when we have to compute something modulo n where n is not prime, according to this theorem, we can break this kind of questions into cases where the number by which you are taking modulo’s is a prime power.

This can be done by write n in its prime representation n = p1q1. . . pkqk

Compute modulo p^k by usual methods
Many times we can use standard tricks to find answer modulo p^k.

After getting modulo p^k answers, we can merge them using CRT. For that see the example given in the wikipedia page.

Short Example
Compute a^b % n assume a = 4 and n = 6.
Write n = 6 = 2 * 3
Compute a^b % 2 = 0
Compute a^b % 3 = 1
Now merge them using CRT. See the formula given in the wikipedia to merge it.

Details of Merging
Assume we want to find a % n.
Let n = p1 * p2.
Find a % p1 and a % p2.
Call a % p1 = x1
Call a % p2 = x2;
For finding a % n. We can do following.
Write a % n = x1 * alpha1 + x2 * alpha2; (Proof is very simple).
where alpha1 is such that
alpha1 = 1 mod p1
and alpha1 = 0 mod p2

Similarly define alpha2
where alpha1 is such that
alpha2 = 0 mod p1
and alpha2 = 1 mod p2

So basically find alpha1, alpha2. For finding these, you need to solve two equations of two variables. That can be done by simplifying the equations written above.

Sample Implementation
See the following

``````
[2]

[1]: http://en.wikipedia.org/wiki/Chinese_remainder_theorem
[2]: http://stanford.edu/~liszt90/acm/notebook.html#file13``````
2 Likes

Why don’t you use simple modular exponentiation?

long long square(long long x)
{

``````return (x*x)%MOD;</br>
``````

}
long long power(long long base,long long expo)
{
if(base==0)
return 0;
if(expo==0)
return 1;
else
{
if(expo%2==0)
return square(power(base,expo/2))%MOD;
else
return (base*power(base,expo-1))%MOD;
}
}

Here base is a, expo is b and MOD is c.

Use logarithmic exponentiation
Here is the c++ implimentation
int power(int a,int b){
long long x=1;
while(b){
if(b&1){
x*=a;
x%=mod;
}
a*=a;
a%=mod;
b>>=1;
}
return x;
}

Hi, just check 《Introduction to Algorithms, 3rd Edition》Chapter 31.6. Especially “Raising to powers with repeated squaring” section

In order to calculate a^b(mod n):

``````MODULAR-EXPONENTIATION(a, b, n)
c = 0
d =1
let <bk,bk-1,...,b0> be the binary representation of b
for i = k downto 0
c = 2c
d = (d * d) mod n
if (bi == 1)
c = c + 1
d = (d * a) mod n
return d``````

Could you tell me more about that? ^^

Yes certainly, I have some meeting to do in around 3 hours. I will explain it in detail after that.

Yes, I’m in Hue ^^. But b is really huge, 1 <= b < 10^1000000, how can we apply this code with that b.
Time limit is 1s.

Thank you very much

I use C++ too

Hm… With b, you must use array or string to store it. Imagine that if a = 10^1000000, b=10^1000000, and c = 2, then how can you calculator (10^1000000 % 2) * (10^1000000 % phi(2))??

I store a in a string s = a1a2a3…an (n is length of a)
Then I use this formula a%c = (a1 * 10^(n-1) % c + a2 * 10^(n-2) % c + … + an * 1 % c) % c