アルゴリズム論特論(塩田)2021年度 第10回

 RSA暗号は素因数分解問題の困難さに安全性の根拠を置いていますが、 一定の条件を満たす合成数に対しては高速に実行できる素因数分解アルゴリズムがいくつか知られています。 鍵を生成する際にはそれらの攻撃法への対策を施す必要がある、というお話です。

  1. フェルマ法
  2. 多倍長整数の平方根
  3. 拡張フェルマ法
  4. $p-1$ 法
  5. RSA 暗号に使ってはいけない危険な鍵
  6. 今日のまとめ