☆数論アルゴリズム特論（Algorithms for Number Theory）[1307]

＜授業のねらい及び具体的な到達目標＞

　整数論における素数に関する理論とアルゴリズムを中心に解説する。素数を中心とした整数論の理論は近年RSA暗号法等の公開鍵暗号の中心を成すものであり情報工学の最近の話題でもある。その基礎になる数学的理論を素数の分布，素数判定を中心に基礎から解説し実際のプログラムの作り方の指針も示す。さらに時間の余裕があれば素因数分解も解説する。

＜授業計画及び準備学習＞

まず近年Net work等の発達で重要性が増した公開鍵暗号法について簡単に解説する。公開鍵暗号法は大きく分けて素因数分解によるもの，離散対数法によるものとの2つがあるがこれらの数学的な基礎を解説する。いずれにしても素数が重要な役割をしていることを示す。ここに素数判定法の重要性があることが理解される。その素数判定法のうち擬似素数（psp,esps,spsp）を扱うものを中心に解説し未だ解決されていない数学上の問題“一般Riemann予想”を仮定すれば素数判定が多項式時間で行われることを示す。

準備学習は以下のとおり
　講義中出した問題を考えておくこと。また教科書等の該当する箇所を呼んでおくこと。

＜成績評価方法及び水準＞

レポートによるが、内容の間違っているものは返却しどの点が不十分か解説し再提出を求める。（再提出、再々提出して正解なら採点の対象となる）合格に必要なレポートの問題は10題前後の予定。

＜教科書＞

“U-Basicによるコンピュータ整数論”木田，牧野　日本評論社
この本は絶版なのでhttp://www.rkmath.rikkyo.ac.jp/~kida/kima.htmからそのＰＤＦ版
をダウンロードしてください。

＜参考書＞

“初等整数論講義”高木貞治　共立出版

＜学生へのメッセージ＞

レポート問題の中にはかなり大変なものもあるので１，２回でへこたれず何度も手直して提出してください。

このページの著作権は学校法人工学院大学が有しています。 Copyright(c)2013 Kogakuin University. All Rights Reserved.