情報数学特論
Mathematics for Information Science
目的
近年，ネットワーク社会における情報漏洩，情報改ざんを防ぎ, さらに本人認証 を行う基盤技術として暗号理論が存在する．本講義では，暗号理論で用いられる 代数・整数論・計算量理論のそれぞれの基本概念について講義する．代数・整数 論では，群論，合同式と剰余計算などの基本理論と，計算量理論に基づいた素数 判定法，素因数分解法などの数論アルゴリズムについて講義する．また計算量理 論では，計算モデル，計算可能性，計算量クラスなどの説明を行い，これらの理 論がどのように公開鍵暗号方式に用いられているか解説する．
概要
計算量の理論と非対称鍵暗号系の暗号理論の基礎を理解する．
キーワード
計算量理論，暗号
注意
学部レベルの代数学，離散数学を習得していること
計画
| 1. | 計算可能性の理論 |
| 2. | 判定可能性 |
| 3. | 帰着可能性 |
| 4. | 複雑さの理論 |
| 5. | クラスP，クラスNP |
| 6. | NP完全性 |
| 7. | 領域の複雑さ |
| 8. | 四則演算の複雑さ |
| 9. | 剰余環 |
| 10. | 剰余環の演算に関する計算量 |
| 11. | 暗号化方式 |
| 12. | RAS暗号化方式 |
| 13. | 離散対数 |
| 14. | デジタル著名 |
評価
授業への取り組み状況により総合的に評価する．
連絡先
中山(1204, 088-656-7223, shin@ias.tokushima-u.ac(no-spam).jp)
片山(1304, 656-7228, katayama@ias.tokushima-u.ac(no-spam).jp)