■

雑誌「数理科学」を見ながら、誌面で紹介されてたPohlig-Hellman法で離散対数問題を解いてみよう。と思ったが、やってみると問題を解くより問題を設定する方がなかなか出来ない。適当に２つの数を選んでても、例えば 13 ∈ <3> on Z₂₀₀ かどうかが結局途中まで解かないと分からない。Log₃13 を求めるのと 13 ∈? <3> on Z₂₀₀ を判定するのと結局どっちが計算量的には困難なんだろうか。