アルゴリズム論特論(塩田)第14回 (4) 今日のまとめ
前へ / 戻る
$\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}}}$
今日のまとめ
- 離散対数を計算する Pohlig-Hellman 法は、$\bmod p$ の離散対数が $\bmod{(p-1)}$ の数であることと、中国剰余アルゴリズムを利用している。
- $p-1$ が小さい素因数しか持たないとき、Pohlig-Hellman 法は高速に動作する。
従って、$\bmod p$ の離散対数を公開鍵暗号に用いる際は $p-1$ が大きな素因数をもつように注意しなければならない。
- 中国剰余アルゴリズムは秘密分散技術にも応用することができる。