前へ / 戻る $\newcommand{\ol}[1]{\overline{#1}}$ $\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$ $\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$ $\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$

本講義のまとめ

• 計算量が $\log$ で書けるアルゴリズムは高速に実行できる。
• 例えば加法・減法の計算量は $\log$ オーダー、乗法・除法の計算量は $\log^2$ オーダー。
• 公開鍵暗号の設計・運用では高速なアルゴリズムが使われる。
  • 拡張ユークリッドアルゴリズム
  • 法演算
  • 高速べき乗
  • 素数判定
  • 素数生成
  • 中国剰余アルゴリズム etc.
• 公開鍵暗号の攻撃には困難と考えられている問題を解く必要がある。
  • 素因数分解問題
  • 離散対数問題 etc.
• 素因数分解問題、離散対数問題には「解きやすい場合」があるので、 鍵の生成時にはそれらの場合を避けなければならない。

　「アルゴリズム論特論」の講義はこれで終了です。試験はありません。 課題がまだ正解に達していない人は頑張りましょう。

前へ / 戻る