計算代数（後期2単位）

客員講師　小�ｱ 俊二

１．授業のねらい・到達目標

計算代数はコンピュータを利用した代数アルゴリズムを研究する学問である。これは、情報セキュリティ技術という大きな応用分野を得て、コンピュータ技術の進歩とともに長足の進歩を続けている分野である。そこで、本科目では現代的な計算代数の研究やその情報セキュリティ技術への応用に必要な素養の習得を目的とし、基本的な計算代数アルゴリズムについて解説するとともに、様々なアルゴリズムやその着想についても触れる。具体的には、計算代数の基本的対象であり、情報セキュリティ技術の理解に必要な多倍長整数及び1変数多項式の基本演算アルゴリズムについて、その構成と漸近計算量を理解することを目標に講義を行う。

２．授業計画

1. 1変数多項式の基本演算
   1. 1変数多項式のコンピュータ上の表現
   2. 1変数多項式の四則演算
   3. 1変数多項式の最大公約元の計算
2. 多倍長整数演算
   4. 多倍長整数のコンピュータ上の表現
   5. 多倍長整数の四則演算
   6. 多倍長整数の最大公約数の計算
3. 1変数多項式の高速乗算アルゴリズム
   7. Karatsuba乗算アルゴリズム
   8. 基本FFT乗算アルゴリズム
   9. SchonhageとStrassenのFFT乗算アルゴリズム
   10. ShoupのFFT乗算アルゴリズム
   11. 高速除算アルゴリズム

３．教科書

特に指定しない。

４．参考書

1. von zur Gathen, Gerhard, Modern Computer Algebra 3rd ed., Cambridge U.P., 2013.
2. Knuth. The Art of Computer Programming vol.2 3rd ed., Addison-Wesley, 1998.
3. Crandall, Pomerance. Prime Numbers, 2nd ed., Springer, 2005.
4. Brent, Zimmermann. Modern Computer Arithmetic, Cambridge U.P., 2011.
5. Warren. Hacker's Delight, Addison-Wesley, 2003.
6. Shoup. A Computational Introduction to Number Theory and Algebra 2nd ed., Cambridge U.P., 2008.

５．関連科目

「アルゴリズム基礎」で扱う漸近計算量について事前知識として必要とする。 また、理工系一般教養レベルの線形代数で扱う行列等の知識を必要とする。

６．成績評価の方法

出席状況と課題レポート（１回）の成績による。

シラバス一覧に戻る