シラバス参照

講義概要/Course Information
2018/05/21 現在

科目基礎情報/General Information
授業科目名
/Course title (Japanese)
数論アルゴリズム
英文授業科目名
/Course title (English)
Number Theoretic Algorithms
開講年度
/Academic year
2017年度 開講年次
/Year offered
3
開講学期
/Semester(s) offered
前学期 開講コース・課程
/Faculty offering the course
情報理工学部
授業の方法
/Teaching method
講義 単位数
/Credits
2
科目区分
/Category
専門科目
開講学科・専攻
/Cluster/Department
総合情報学科
担当教員名
/Lecturer(s)
太田 和夫
居室
/Office
東3-928
公開E-Mail
/e-mail
kazuo.ohta{at}uec.ac.jp
授業関連Webページ
/Course website
http://ohta-lab.jp/lecture/
更新日
/Last updated
2017/04/11 11:40:25 更新状況
/Update status
公開中
/now open to public
講義情報/Course Description
主題および
達成目標
/Topic and goals
公開鍵暗号の基礎となっている数論アルゴリズムを扱う。離散数学の復習をおこなった後に,初等整数論の基礎について概説する。公開鍵暗号の具体例を示し,いくつかの素因数分解アルゴリズムを解説する。これらのアルゴリズムの基礎となっている数学について深く理解するとともに,アルゴリズムを実装する上で必要なの技術を身につけることを目標とする。

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

授業内容と
その進め方
/Course outline and weekly schedule
先ず,離散数学で学び残した同値関係,商集合の概念を理解する。
次に,フェルマーの小定理,中国人剰余定理を含めた初等整数論を準備する。
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):達成度確認試験とその解説
授業時間外の学習
(予習・復習等)
/Preparation and review outside class
授業中に証明しきれなかった内容については,復習時に自習すること。
復習余裕のある者はアルゴリズムを実装して,その動作を確認すること。
成績評価方法
および評価基準
(最低達成基準を含む)
/Evaluation and grading
数論アルゴリズムの理解について試験を実施する。試験の結果をもって評価する。
オフィスアワー:
授業相談
/Office hours
質問等があるときは事前にメールでアポイントメントを取ってから研究室を訪問すること。
学生へのメッセージ
/Message for students
現在の情報化社会の基盤技術の一つである公開鍵暗号を知るためには,数論アルゴリズムに関する知識とアルゴリズムの基礎となっている数学についての深い理解が不可欠です。興味を持って意欲的に取り組んでください。
その他
/Others
なし
キーワード
/Keyword(s)
初等整数論,公開鍵暗号,素因数分解問題,離散対数問題