離散対数問題
DLP
(discrete logarithm problem)
$ p
を素数、
$ g
を
$ Z^*_p
の原始元としたとき、
$ Z^*_p
の任意の元
$ y
に対して
$ y=g^x \; mod\; p\; (0 \leq x \leq p-2)
を満たす
この
$ x
を底
$ g
についての
$ y
の
離散対数
といい、
$ log_gy
と表す
このとき、離散対数
$ x
を解く問題を
$ Z^*_p
における離散対数問題という
離散対数問題を効率的に解くアルゴリズムは存在しないという仮定
→
離散対数仮定
(
DL仮定
)
参考:
暗号技術のすべて(IPUSIRON)|翔泳社の本