以 3 ^6 为例, 6=110=10+100 因此，3^6=3^(2+4)=3^2*3^4.

两个注意点
1)求余两次和求余一次的效果是一样的。 例如 8%6%6=8%6=2； 3%6%6=3%6=3
2）循环操作要满足第一次循环没问题和每一次循环没问题

3^6 % p
=(3^23^4)%p
=[(3^2%p)(3^4%p)]%p
=[(1%p)(3^2%p)(3^4%p)]%p

res1=1%p
由于6=110，第二位是1，因此3^2是第一次循环，res2=res1(3^2%p). 第三位是1， 因此第二次循环是res3=res2(3^4%p)= (1%p)(3^2%p)(3^4%p), 但是这样并不等价于3^6 % p ， 因此基于注意点1），可以改为 res2=res1(3^2%p)%p, res3=res2(3^4%p)%p,
那么就对应了以下拆解开的代码
res1=1%p
if(b&1) res2=res1a%p
a=aa%p
b>>1