オイラーの定理とカーマイケルの定理

• 2018/07/25 09:32
• Elementary number theoryGroup theorymath

以前の記事, エルガマル暗号では, エルガマル暗号に関する諸々の前提の説明と, その実装について示した. 同エントリ内で, フェルマーの小定理¹については取り扱ったものの, その一般形であるオイラーの定理およびカーマイケルの定理について特に触れなかったため, 本エントリでそれらに関してまとめる. しばしば値の確認には, 簡単のため Haskell を使う.

目次

1. オイラーの定理
2. ラグランジュの定理
3. カーマイケルの定理

Read more

---

エルガマル暗号

• 2018/07/14 07:50
• mathElementary number theoryGroup theoryHaskellPython

エルガマル暗号が離散対数問題の応用であることは認知していたものの, きっちりと自分でまとめたことが無かったと思うので, それに関連する諸々の前提についてもふまえて, 一度書くことにした. また, その処理系を実装した. 本エントリでは, 同暗号プロトコルの話の前にまず前提を示し, その後, 実装の観点から見た要点を示す.

目次

1. ユークリッドの互除法
2. ガロア体
3. オイラーの $\phi$ 関数
4. フェルマーの小定理
5. 原始元
6. 離散対数問題
7. 実装
   1. フェルマーテスト, Miller-Rabin 素数判定法
   2. 原始根の生成
   3. 鍵と暗号文の生成
   4. 暗号文の復号
   5. 実行
8. 参考文献

Read more

---