拡張ユークリッドアルゴリズムを応用した中国剰余アルゴリズムを今日は勉強します。 暗号の分野では、離散対数問題の解法や、秘密分散法に応用される基本的なアルゴリズムです。 $\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}}}$

1. 数当てゲーム
2. 中国剰余定理・中国剰余アルゴリズム
3. 3 式以上の中国剰余アルゴリズム
4. 今日のまとめ