前へ / 戻る $\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$ が大きな素因数をもつように注意しなければならない。
• 中国剰余アルゴリズムは秘密分散技術にも応用することができる。

---