How to calculate (a ^ b) % c

general
21

The language for above problem is Vietnamese, do you want to get the link?

22

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

23

I don’t know the question requiring, just understand that: "calculate a^b % c " :smiley:

24

if a p = 0, then a^n p will always be zero.

1 Like
25

Oh :D, thank you :smiley:

26

Don’t you think your if-else ladder for even exponent is very inefficient ?

27

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