シラバス参照

講義概要/Course Information
2024/11/12 現在

科目基礎情報/General Information
授業科目名
/Course title (Japanese)
数論アルゴリズム
英文授業科目名
/Course title (English)
Number Theoretic Algorithms
科目番号
/Code
開講年度
/Academic year
2015年度 開講年次
/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 update
2015/07/19 14:31:25 更新状況
/Update status
公開中
/now open to public
講義情報/Course Description
主題および
達成目標(2,000文字以内)
/Themes and goals(up to 2,000 letters)
公開鍵暗号の基礎となっている数論アルゴリズムを扱う。離散数学の復習をおこなった後に,初等整数論の基礎について概説する。公開鍵暗号の具体例を示し,いくつかの素因数分解アルゴリズムを解説する。これらのアルゴリズムの基礎となっている数学について深く理解するとともに,アルゴリズムを実装する上で必要なの技術を身につけることを目標とする。

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

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

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