シラバス参照

講義概要
2017/07/27 現在

科目基礎情報
授業科目名 数論アルゴリズム
英文授業科目名 Number Theoretic Algorithms
開講年度 2017年度 開講年次 3
開講学期 前学期 開講コース・課程 情報理工学部
授業の方法 講義 単位数 2
科目区分 専門科目
開講学科・専攻 総合情報学科
担当教員名 太田 和夫
居室 東3-928
公開E-Mail kazuo.ohta{at}uec.ac.jp
授業関連Webページ http://ohta-lab.jp/lecture/
更新日 2017/04/11 11:40:25 更新状況 公開中
講義情報
主題および
達成目標
公開鍵暗号の基礎となっている数論アルゴリズムを扱う。離散数学の復習をおこなった後に,初等整数論の基礎について概説する。公開鍵暗号の具体例を示し,いくつかの素因数分解アルゴリズムを解説する。これらのアルゴリズムの基礎となっている数学について深く理解するとともに,アルゴリズムを実装する上で必要なの技術を身につけることを目標とする。

前もって履修
しておくべき科目
離散数学
前もって履修しておくこ
とが望ましい科目
線形代数学
教科書等 教科書: コルメン他著 浅野他訳 アルゴリズムイントロダクション第3巻 近代科学社
参考図書: 尾関和彦著「情報技術のための離散系数学入門」共立出版
 

授業内容と
その進め方
先ず,離散数学で学び残した同値関係,商集合の概念を理解する。
次に,フェルマーの小定理,中国人剰余定理を含めた初等整数論を準備する。
RSA暗号,ElGamal暗号の仕組みを概説したのち,素数判定,整数の素因数分解,離散対数問題などのアルゴリズムに関して,実装技術を含めて学習する。

第1回(4/13):導入,ガイダンス,離散数学の復習
第2回(4/20):同値関係,商集合(離散数学からの準備)
第3回(4/27):初等整数論(1)整数,法計算,Zn
第4回(5/11):初等整数論(2)乗法逆元,拡張ユークリッドアルゴリム
第5回(5/18):初等整数論(3)フェルマーの小定理とオイラーの定理
第6回(5/25):初等整数論(4)中国人の剰余定理
第7回(6/01):公開鍵暗号 (1) 素因数分解問題とRSA暗号
第8回(6/08):公開鍵暗号(2)RSA暗号の数値例
第9回(6/15):RSA暗号の演習と課題の解説
第10回(6/22):離散対数問題と公開鍵暗号 (DH鍵配送,ElGamal暗号)
第11回(6/29):アルゴリズム(1)確率的素数判定法(1)
第12回(7/06):アルゴリズム(2)確率的素数判定法(2), ベーズの定理
第13回(7/13):アルゴリズム(3)素因数分解 rho-method
第14回(7/20):アルゴリズム (4) 素因数分解(つづき)課題の解説
第15回(7/27):達成度確認試験とその解説
授業時間外の学習
(予習・復習等)
授業中に証明しきれなかった内容については,復習時に自習すること。
復習余裕のある者はアルゴリズムを実装して,その動作を確認すること。
成績評価方法
および評価基準
(最低達成基準を含む)
数論アルゴリズムの理解について試験を実施する。試験の結果をもって評価する。
オフィスアワー:
授業相談
質問等があるときは事前にメールでアポイントメントを取ってから研究室を訪問すること。
学生へのメッセージ 現在の情報化社会の基盤技術の一つである公開鍵暗号を知るためには,数論アルゴリズムに関する知識とアルゴリズムの基礎となっている数学についての深い理解が不可欠です。興味を持って意欲的に取り組んでください。
その他 なし
キーワード 初等整数論,公開鍵暗号,素因数分解問題,離散対数問題