アルゴリズム論特論（塩田）第8回 (3) 高速べき乗
前へ / 戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$
$\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
高速べき乗
第3回で注意したように、
宇宙の年齢がおよそ 138億年 ≒ $4.35×10^{17}$ 秒であることに比べて、
2048 ビットの整数は $10^{600}$ 以上というとてつもなく巨大な数です。
そのような数に対して RSA 暗号では $x^e\, \%\, n$ を計算しなければなりません。
- Python なら x ** e % n と書く式ですが、
x ** e はおよそ $2048 \times 2^{2048}$ ビットの数なので、そもそもメモリに入りません。
（ 1TiB はたった $2^{43}$ ビット ）
- 必要なのは $n$ で割った余りなので「 $x$ 倍して $\%\,n$ する」計算を $e$ 回繰り返せばメモリの問題は解決します。
しかし、反復回数 $e$ が巨大なので、これも現実的ではありません（ 計算量としては $O(n\log^2 n)$ ）。
ところが、うまい手を考える人はいるもので
アイデア（反復2乗法） $163^{91} \,\%\, 307$ で説明しましょう。
- べき指数 $91$ を 2 べきの和として表します。
$91=(1011011)_2$ $\Rightarrow$ $91=64+16+8+2+1$
- $x^2 % 307$ を繰り返して $163^{64}\,\%\,307$ まで計算します。
$\begin{array}{lll}
163^2\,\%\,307 &&= 167 \\
167^2\,\%\,307 &(\ = 163^4\,\%\,307\ ) &= 259 \\
259^2\,\%\,307 &(\ = 163^8\,\%\,307\ ) &= 155 \\
155^2\,\%\,307 &(\ = 163^{16}\,\%\,307\ ) &= 79 \\
79^2\,\%\,307 &(\ = 163^{32}\,\%\,307\ ) &= 101 \\
101^2\,\%\,307 &(\ = 163^{64}\,\%\,307\ ) &= 70 \\
\end{array}
$
- 1° , 2° を組み合わせて
\begin{align}
163^{91}\,\%\,307 &= 163^{64+16+8+2+1}\,\%\,307 \\
&= (163^{64} \times 163^{16} \times 163^{8} \times 163^{2} \times 163^{1})\,\%\,307 \\
&= (70 \times 79 \times 155 \times 167 \times 163)\,\%\,307 \\
&= 2 \\
\end{align}
Th.7 $x$, $e$ が $n$ と同じくらいのビット数であれば、
反復2乗法を用いた $x^e\,\%\, n$ の計算量は $O(\log^3 n)$.
証明 1° は $e$ の2進数表示を使うだけ。
2° , 3° はいずれも、乗算と除算を最大で ( $e$ のビット長 ) 回繰り返すので、
計算量は $O(\log e) \times O(\log^2 n)=O(\log^3 n)$.
(証明終)
Python 風に書けば、こんなにも簡単です：
Algorithm 8 (反復2乗法)
- 入力：$x$, $e$, $n$
- 出力：$x^e\,\%\,n$
def modpow(x, e, n):
y = 1
while e > 0:
if e % 2 == 1:
y = (y * x) % n
x = (x * x) % n
e //= 2
return y
Rem.9
- Python には高速べき乗法が組み込まれていて、
pow(x, e, n) と書けば高速に $x^e\,\%\,n$ を計算してくれます。
ただし math モジュール内の pow は double 型対象で引数を 2 個しか取りませんので
from math import *
と書くとエラーを起こします。
- $x^e\,\%\,n$ の計算は他にも、
素数判定・素数生成の確率的アルゴリズムや、
Th.5 (3) ⇒ (1) のアルゴリズム等、
色んな所で使われます。