takehikom https://blog.hatena.ne.jp/takehikom/ わさっきhb https://takehikom.hateblo.jp/ 情報教育 離散対数問題の時間計算量は「pに比例」じゃダメなの? ダメです．一言でその理由を説明すると，「計算量は，入力のサイズをもとに求めないといけないから」です． 順を追って説明しましょう．ここでは，離散対数問題*1を次のように定義しておきます．すなわち，素数 とその生成元 ，そして [tex:1\le y *1:正確には「有限体上の離散対数問題」です．暗号の分野では，これと別に「楕円曲線上の離散対数問題」もよく研究されています． 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftakehikom.hateblo.jp%2Fentry%2F20070728%2F1185623522" title=" P=NP問題を理解するためのステップ〜指数時間アルゴリズムの例 - わさっきhb" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2007-07-28 20:52:02 rich https://takehikom.hateblo.jp/entry/20070728/1185623522 1.0 100%