aのk乗をmで割った余り = p(a, k, m)

gistfile1.md

(xy % z) = ((x % z) * (y % z)) % z

k = 2tの場合 a^k = a^t * a^t

p(a, k, m) = (p(a, k/2, m) * p(a, k/2, m)) % m

k = 2t + 1の場合

a^k = a^t * a^t * a

p(a, k, m) = (p(a, k - 1, m) * p(a, 1, m)) % m


function p(a, k, m) {
  if (k == 0) {
    return 1;
  }
  q = p(a, k/2, m);
  
  ret = (q * q) % m;
  
  if (k % 2 == 1) {
    ret = (ret * (a % m)) % m;
  }
  
  return ret;
}