離散対数問題
Disecrete Logarithm Problem, DLP
大きな素数
$ p
と、原始元
$ g
、任意の
$ a
を選んだときに
離散対数
を求めることは、実用的な時間内では解くことができない
離散対数
$ g
が
$ Z^\ast_p
の
原始元
のとき、任意の
$ a\in Z^\ast_p
に対し
$ a\equiv g^x \bmod p
となる
$ x\in\{0,1,\cdots,p-2\}
が必ず存在する
このような
$ x
を
$ a
の離散対数という
この
$ a
の離散対数を求める問題を離散対数問題という