P=NP問題を理解するためのステップ〜指数時間アルゴリズムの例(続き)

整数のオーダを，入力サイズのオーダに変換する

昨日の続きです．

素数 $p$ とその生成元 $g$ ，そして [tex:1\le y

という離散対数問題において， $x$ の候補を0から順に試して解を見つけるという「総当たり法」を実施すると，計算終了までの時間計算量は $O(p)$ になる*1のですが，これを入力サイズ $n$ の式で表現するのが目的です．これも昨日の復習ですが， $n$ とは， $p$ , $g$ , $y$ のそれぞれの2進表現により得られる長さとします．
$p$ と $n$ の関係について，細かいことを言うといくらでも考えられるのですが，ここでは，「 $p$ の2進表現が， $g$ , $y$ のそれらと比べて非常に大きい場合」と，「 $p$ , $g$ , $y$ がそれぞれ近い値である場合」の2点に絞ってみます*2．
まず，「 $p$ の2進表現が， $g$ , $y$ のそれらと比べて非常に大きい場合」ですが，このときは「 $n$ の値は， $p$ の2進表現の長さで決まる」と考えます．以後，よく「2進表現の長さ」が出てくるので，記号を導入しましょう．整数値 $b$ の2進表現の長さを， $|b|$ と書きます． $|b|$ ≒ $log_2 b$ です．
ここで $n$ ≒ $|p|$ ≒ $log_2 p$ を $p$ について解くと， $p$ ≒ $2^n$ となります． $O(p)$ に代入すると， $O(2^n)$ となって，したがって時間計算量は入力サイズの指数関数になります．
もう一つのケースは，「 $p$ , $g$ , $y$ がそれぞれ近い値である場合」ですね．このときは， $n$ ≒ $|p|+|g|+|y|$ と $|p|$ ≒ $|g|$ ≒ $|y|$ が成り立ちます．ここから $p$ と $n$ の関係を求めると， $p$ ≒ $n/3$ となります．
これを $O(p)$ に代入すると， $O(2^{n/3})$ です．指数法則を使って「なんとかのn乗」にすると，[tex:O*3，そして $O((2^{1/3})^n)$ という時間計算量も指数オーダと言うことができます．

で，離散対数問題は指数時間ですか?

この表現は誤解を招きますね．問題そのものには，時間などの計算量は付随しません．アルゴリズムを決めれば，その計算量を求めることは当たり前のように行われます．同じ問題でも，計算量が大きいアルゴリズムは「まずい解法」，小さいアルゴリズムは「良い解法」と言えます．
今のところ知られているアルゴリズムの中で，計算量の最も小さい値(たいていはオーダ表記)によって，その問題の難しさを表現することはよくあります．しかしそう捉えるとしても，研究の進歩によってその式が小さくなる可能性がある点には，注意しましょう．
さてこの意味での，離散対数問題の難しさ(計算量)についてですが，離散対数問題の困難性に関する計算量についての調査・研究報告書というのを見かけました．数式たくさんですが，有力なアルゴリズムであっても，上記の素数 $p$ のサイズに関する準指数時間というのがベストなようです．
準指数時間というのは， $O(n^k)$ に代表される「多項式時間」と， $O(c^n)$ に代表される「指数時間」の間に位置します．これも多項式時間を越えているので，効率がよいとはみなされません．

*1:「 $g^x\bmod p=y$ 」の計算回数で評価しています．実は，この計算に要する手間は $p$ に依存するので，より精密に評価するなら，この点にも配慮する必要があります．

*2:なお， $p>g$ , $p>y$ として差し支えありません．というのも， $p\le y$ のときは，離散対数の式に照らし合わせると左辺が $p$ 未満，右辺が $p$ 以上なので，解なしです．また $p\le g$ のときは，フェルマーの小定理から， $g\bmod (p-1)$ を新たな $g$ にすればいいのです．

*3:2^{1/3})^n)] となります．オーダ記法でこのような表現を見ることはなかなかないのですが，定数 $c$ が $c>1$ であり，かつ十分大きな $n$ を考えるならば， $c^n$ は $n$ に関するどんな多項式よりも大きくなるので， $(2^{1/3})^n$ だって確かに指数関数((ここで $2^{1/3}$ とは，2の立方根のことです．はてなのtex記法では，立方根がうまく表せなかったので，この書き方にしています．