繰返し二乗法
冪乗を高速に求めるアルゴリズム。すべての自然数は $2$ の冪乗和の組み合わせで表すことができるという性質を利用している。 $N$ は $2$ の冪乗和で表すことができて $N = 2^{K_1} + 2^{K_2} + 2^{K_3} + \dots$ となる。よって $x^N = x^{2^{K_1}} \times x^{2^{K_2}} \times x^{2^{K^3}} \times \dots$。$2$ 進数で操作すればよいので, $1$ のビットが立つ部分 $i$ について, 解に $x^i$ を掛けていく。
計算量
$O(\log N)$
実装例