公開鍵暗号における応用
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/11 10:07 UTC 版)
上述のように、m を法とした b の e-冪剰余を求めるには、高々 O(log(e)) 回の加算、乗算、剰余算が必要である。加算、乗算、剰余算はそれぞれ被演算数の桁数の多項式時間で計算できる。特に、上述のように乗算を行うたびに剰余演算を行えば、被演算数を常に m 未満に保つことができる。よって、m を法とした b の e-冪剰余は、入力サイズ log(b) + log(e) + log(m) の多項式時間で計算できる。 一方、m, b, c から c = be mod m なる e を求める問題は離散対数問題といわれ、効率的な、つまり入力サイズの多項式時間のアルゴリズムは発見されていない。公開鍵暗号のうちある種のものは、この一方向性を利用して設計されている。
※この「公開鍵暗号における応用」の解説は、「冪剰余」の解説の一部です。
「公開鍵暗号における応用」を含む「冪剰余」の記事については、「冪剰余」の概要を参照ください。
ウィキペディア小見出し辞書の「公開鍵暗号における応用」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 公開鍵暗号における応用のページへのリンク
