アルゴリズム論特論（塩田）第12回 (3) 生成元 $g$ の作り方
前へ / 戻る / 次へ
$\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}}}$
生成元 $g$ の作り方（シンプルなヴァージョン）
$g$ が生成元であること
$\Leftrightarrow$
初めて $g^e=1$ となる自然数 $e$ （位数）が $p-1$
$\Leftrightarrow$
$g^1 \neq 1$, $g^2 \neq 1$, $\cdots$, $g^{p-2} \neq 1$
でした。
これを計算で確かめようとするとその計算量は $O(p\log^2 p)$ になり、
実用の鍵サイズでは実行不可能です。
$p$ を無条件で作ってしまうからいけないので、もっと「作為的」に $p$ を作ることにしましょう。
Th.5 $p-1=2\,\times$ ( 大きな素数 $q$ ) であれば
$g$ が生成元であること $\Leftrightarrow$ $g^2 \neq 1$ かつ $g^q \neq 1$.
証明 $\Rightarrow$) は上の注意より。
$\Leftarrow$) $g$ の位数を $e$ とし、これが $p-1$ に等しいことを示します。
前回の
Th.4 (1) より $e$ は $p-1=2q$ の約数ですから、$e=1$, $2$, $q$, $2q$ のいずれかです。
条件より $g^2 \neq 1$, $g^q \neq 1$ であり、これから $g \neq 1$ でもありますから、
$e \neq 1 ,2,q$. 従って $e=2q=p-1$ となり $g$ は生成元となります。(証明終)
$g^q$ の計算量は高速べき乗法を用いれば $O(\log^3 p)$ でした。
さらに、この設定下では約 50% の剰余類が生成元であることがわかっています。
従って、$p=2\times$ ( 大きな素数 $q$ ) $+1$ が素数であれば、
$\bmod\ p$ の生成元は高速に生成できます。
Algorithm 6（みんなの公開鍵）
- 入力：鍵長（ $p$ のビット数 ）$k$
- 出力：$k$-ビットの素数 $p$ と、$\bmod\ p$ の生成元 $g$
while True:
$q=(k-1)$-ビットのランダムな素数
$p=2q+1$
if $p$ が素数：
break
while True:
$g=$ 乱数 ( $1 \lt g \lt p-1$ )
if $g^2 \neq 1$ and $g^q \neq 1$:
$p$, $g$ を出力し終了
生成元 $g$ の作り方（一般化されたヴァージョン）
ただし、鍵長が大きくなると
$q$ も $2q+1$ も素数
となる $q$ が見つかりにくくなります。
そこで、もう少し探しやすい定理も書いておきましょう。
Th.7 $p-1=$ ( 小さな偶数 $m$ ) $\times$ ( 大きな素数 $q$ ) であれば
$g$ が生成元であること
$\Leftrightarrow$
$g^m \neq 1$ かつ 「 $m$ の全ての素因子 $\ell$ について $g^{(m/\ell)q} \neq 1$ 」
例えば $p-1=72q$ であれば
$g^{72} \neq 1$, $g^{36q} \neq 1$, $g^{24q} \neq 1$
を満たす $g$ は生成元になります。証明は
Th.5 と同様です。
これを使えば
Algorithm 8（みんなの公開鍵）
- 入力：鍵長（ $p$ のビット数 ）$k$
- 出力：$k$-ビットの素数 $p$ と、$\bmod\ p$ の生成元 $g$
while True:
$q=((k-10)$-ビットのランダムな素数$)$
$m=(10$-ビット程度のランダムな偶数$)$
$p=mq+1$
if $p$ が $k$-ビット：
if $p$ が素数：
break
while True:
$g=$ 乱数 ( $1 \lt g \lt p-1$ )
if $g^m \neq 1$ and 「 $m$ の全ての素因子 $\ell$ について $g^{mq/\ell} \neq 1$ 」:
$p$, $g$ を出力し終了
Rem.9 実は、もっと簡潔に
$g$ が生成元であること
$\Leftrightarrow$
$p-1$ の全ての素因子 $\ell$ について $g^{(p-1)/\ell} \neq 1$
と書けるのですが、
セキュリティ上の配慮から $p-1$ には大きな素因子を持たせたいので Th.7 のように書きました。