離散対数問題

デジタル大辞泉

りさんたいすう‐もんだい【離散対数問題】

読み方：りさんたいすうもんだい

素数pと定数aが与えられ、整数yを素数pでa^xを除したときの剰余とするとき、yについて整数解xを求める問題。

[補説] xからyを計算することは容易だが、pが大きな数である場合、yからxを計算することは非常に困難であり、総当たりで計算しても膨大な時間がかかってしまう。解を得ることが困難な数学的性質から、エルガマル暗号や楕円曲線暗号などの基本原理として、公開鍵暗号に安全性を保証している。