how does the repeated squaring method of modular exponentiation works?

can anyone explain repeated squaring method of computing a^b%m, I have referred various links, but everywhere only the algorithm is written no one explains how it works.

Anyone please explain repeated squaring method in detail with its working.

You know that (a^n)^2 = a^(2n). So if you have say b=8
a^8=(a^4)^2=((a^2)^2)^2.
This is the logic. however if b is not a power of 2 say 10 then

a^10 = (a^5)^2
a^5 = ((a^4)*a = ((a^2)^2)*a.

This is how you do it . Repeatedly calculate a^(n/2) till n is 1.

@sdssudhu

ll fast_exp(int base, int exp) {
ll res=1;
while(exp>0) {
if(exp%2==1) res=(resbase)%MOD;
base=(base
base)%MOD;
exp/=2;
}
return res%MOD;
}

why we are doing different thing for odd exp.

We do it different for odd exp. as a odd number cannot be expressed as some 2*z , z->integer. So that difference comes.

@sdssudhu

Thanks.

//