アルゴリズム論特論（塩田）第9回 (2) 素数生成
素数生成
不完全ながら素数判定が高速にできるようになりましたので、
RSA 暗号に使う大きな素数を作りましょう。
Algorithm 6 (素数生成)
- 入力：ビット長 $k$
- 出力：$k$-ビットの素数 $n$
def kBitPrime(k):
while True:
$n$ = $k$-ビットの乱数
if FermatTest($n$) :
return $n$
Python で $k$-ビットの乱数を得るには、random module を import して次のように書きます。
random.randint(1 << (k-1), (1 << k) - 1)
1 << (k-1) は $2^{k-1}$ のことで、$k\,$-ビットで最小の自然数です。
宜しいですね。
ちなみに numpy.random.randint では仕様が違って右端を入れないので
numpy.random.randint(1 << (k-1), (1 << k))
になります。
素数定理
Alg.6 の計算量を見積もるためは、
素数が見つかるまでに幾つ位の乱数をテストしなければならないかを知る必要があります。
Th.7（素数定理） $x$ 以下の素数の個数を $\pi(x)$ と表すと、
$\pi(x) \sim \displaystyle{\frac{x}{\log x}}$
$\sim$ は「おおよそ」という意味です。
（ 正確に言うと、$x \rightarrow +\infty$ のとき比の極限が 1 になる、ということです。）
証明はとても難しいので、結果だけ使わしてもらいましょう。
Cor.8 $x$ 程度のランダムな整数が素数である確率はおおよそ $\displaystyle{\frac{1}{\log x}}$ である。
証明
(個数) $=\displaystyle{\int_0^x}$(確率) $dx$
ですから
(確率) $=$ (個数) $'$ $\displaystyle{\sim\frac{d}{dx}\left(\frac{x}{\log x}\right)}
=\displaystyle{\frac{1}{\log x}-\frac{1}{\log^2 x}}$
≒ $\displaystyle{\frac{1}{\log x}}$.
(証明終)
素数生成の計算量
Th.9 Alg.6 の計算量は $O(\log^4 n)$.
証明 フェルマ・テストの計算量は反復2乗法と同じ $O(\log^3 n)$ です。
Cor.8 より素数が見つかるまでに平均でおおよそ $\frac{1}{2}\log n$ 個の乱数をテストしなければならないので、
Alg.6 全体の計算量は
$O(\log^3 n) \times \frac{1}{2}\log n = O(\log^4 n)$
になります。(証明終)
Rem.10 RSA 暗号の正規ユーザが用いる計算の計算量をまとめておきましょう。RSA modulus を $n$ として
- 素数 $p$, $q$ の生成（フェルマ・テスト）：$O(\log^4 n)$
- $n= p \times q$ の計算：$O(\log^2 n)$
- $m = (p-1) \times (q-1)$ の計算：$O(\log^2 n)$
- 暗号化指数・復号指数 $e$, $d$ の生成（拡張ユークリッド）：$O(\log^2 n)$
- 平文の暗号化・暗号文の復号（反復2乗法）：$O(\log^3 n)$
いずれも $\log$ で書ける高速な計算であることがわかります。