離散対数問題

Discrete Logarithm Problem(DLP)

ある計算の結果から簡単に逆算ができないような数学上の問題の1つ

ある素数qについて、q未満の自然数gおよびsを選択し、gのs乗をqで割った余りmを算出する

このとき、q、g、sからmは容易に算出できる一方、g、q、mが分かっても、このような関係を満たすsを求める効率的な方法は見つかっていない

超わかりやすく言うと「mod q がついた対数問題」

通常の対数問題は「g を何乗したら y になるか？」というもの

g^s = y

この場合、logを使うことで計算できる

離散対数問題は「g を何乗したら y になるか？(素数 q を法とする)」

g, y ∈ mod q に対して g^s = y

参考資料