離散対数問題の時間計算量は「pに比例」じゃダメなの?
ダメです.一言でその理由を説明すると,「計算量は,入力のサイズをもとに求めないといけないから」です.
順を追って説明しましょう.ここでは,離散対数問題*1を次のように定義しておきます.すなわち,素数 とその生成元 ,そして [tex:1\le y
- のときに が成り立てば終了.成り立たなかったら次へ.
- のときに が成り立てば終了.成り立たなかったら次へ.
- のときに が成り立てば終了.成り立たなかったら次へ.
- …
としていくと,ある値で終了するというものです.実際,素数と生成元の関係から,このような は,[tex:0\le x
もしかしたら のときに終了するかもしれないし, のときに終了かもしれません., , の具体的な値を見ただけでは,そこからどこで終了するかは想像できないので,終了までの の計算回数の平均は,間をとっておおよそ 回としておきましょう.
これをオーダで表記すると になる.だから,「pに比例」と言いたいところですが,この式では,計算の手間,あるいは時間計算量を求めたことになりません.
冒頭に書いたとおり,計算量は,入力のサイズをもとに求めないといけないのです.
この場合,, , のそれぞれの2進表現を,入力とします*3.この入力の長さを として, と の関係を求め, を の式で表現すればいいのですが….
明日に続くTo be continued tomorrow.