離散対数問題

デジタル大辞泉

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

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

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

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

ウィキペディア

離散対数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 06:40 UTC 版)

代数学における離散対数（りさんたいすう、英: discrete logarithm）とは、通常の対数の群論的な類似物である。 離散対数を計算する問題は整数の因数分解と以下の点が共通している：