繰り返し二乗法

この記事は，以下から該当箇所を抜き出したものです：Pythonで蟻本2-6 - 数学的な問題を解くコツ - 競プロはじめました
（蟻本p. 114-）

【注】Pythonでは繰り返し二乗法を実装しなくても，pow(base, exp[, mod])により，pow(base, exp) % modが効率よく計算できます．

問題

$x^{n}\pmod m$を効率よく計算することを考える．

方法1

考え方

\begin{aligned}
x^{n}
&=
\begin{cases}
\, \bigl(x^{2}\bigr)^{n/\!/2} & (n:\text{even}) \\
\, x \cdot \bigl(x^{2}\bigr)^{n/\!/2} & (n:\text{odd})
\end{cases}
\end{aligned}

とすれば，再帰的に$O(\log n)$で計算できる．

実装

def mod_pow(x, n, mod):
  if n == 0:
    return 1
  res = mod_pow(x**2 % mod, n//2, mod)
  if n & 1:
    # nが奇数ならxを掛ける
    res = res * x % mod
  return res

方法2

考え方

$n$が2進数で

\begin{aligned}
n
& = \sum_{i} a_{i} 2^{i} \\
& = \bigl(\cdots a_{2} a_{1} a_{0}\bigr)_{2}
\end{aligned}

と表せるとき，

\begin{aligned}
x^{n}
&= \prod_{i} x^{a_{i} 2^{i}}
\end{aligned}

である．

よって，$x^{2^{i}}$を順次計算して$a_{i}=1$なら結果に乗じることにすれば，$O(\log n)$で計算できる．

実装

$x^{2^{i}}$を$i$が小さい方から計算すると，次のようになる．

def mod_pow(x, n, mod):
  res = 1
  while n > 0:
    # n=0 なら1を返す
    if n & 1:
      # i(=0,1,...)番目のビットが1なら res * x^(2^i)
      res = res * x % mod
    x = x**2 % mod  # x = x^(2^(i+1))
    n >>= 1
  return res