わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

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

離散対数問題の時間計算量は「pに比例」じゃダメなの?

ダメです.一言でその理由を説明すると,「計算量は,入力のサイズをもとに求めないといけないから」です.
順を追って説明しましょう.ここでは,離散対数問題*1を次のように定義しておきます.すなわち,素数 p とその生成元 g,そして [tex:1\le y

  • x=0 のときに g^x\bmod p=y が成り立てば終了.成り立たなかったら次へ.
  • x=1 のときに g^x\bmod p=y が成り立てば終了.成り立たなかったら次へ.
  • x=2 のときに g^x\bmod p=y が成り立てば終了.成り立たなかったら次へ.

としていくと,ある値で終了するというものです.実際,素数と生成元の関係から,このような x は,[tex:0\le x*2.
もしかしたら x=1 のときに終了するかもしれないし,x=p-2 のときに終了かもしれません.p, g, yの具体的な値を見ただけでは,そこからどこで終了するかは想像できないので,終了までの g^x\bmod p=y の計算回数の平均は,間をとっておおよそ p/2 回としておきましょう.
これをオーダで表記すると O(p) になる.だから,「pに比例」と言いたいところですが,この式では,計算の手間,あるいは時間計算量を求めたことになりません.
冒頭に書いたとおり,計算量は,入力のサイズをもとに求めないといけないのです.
この場合,p, g, yのそれぞれの2進表現を,入力とします*3.この入力の長さを n として,pn の関係を求め,O(p)n の式で表現すればいいのですが….
明日に続くTo be continued tomorrow

*1:正確には「有限体上の離散対数問題」です.暗号の分野では,これと別に「楕円曲線上の離散対数問題」もよく研究されています.

*2:ちなみにフェルマーの小定理から,g^{p-1}\bmod p=1 となるので,x\ge p-1 の範囲を考える必要はありません.

*3:3進数でも4進数でもかまいませんが,その場合でも時間計算量は指数関数になります.1進数,すなわち「1」を p 個並べてこれを p とするのは不可です.