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

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

整数論における素数に関する理論とアルゴリズムを理解する。素数を中心とした整数論の理論の一つRSA暗号法等の公開鍵暗号の中心を理解する。またそのための元となる数学的理論の素数の分布，素数判定等の基礎的な部分を理解する。

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

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

１連分数
　１　連分数の定義と計算法
　２　いろいろな数の連分数表示
　３　平方根の連分数表示と循環性
　４　平方根の連分数展開の計算法
　５　Pellの方程式の解法
２素数判定法と各種擬似素数
　１　一般論
　２　擬似素数とカーマイケル数
　３　Euler擬似素数
　４　強擬似素数
　５　素数判定法　一般論
　６　　　　　　　Fermatの方法
　７　　　　　　　Eulreの方法
　８　　　　　　　Miller-Rabinの方法
　９　　　　　　　Eulerの方法,Miller-Rabinの方法における良い底の割合
１０　　　　　　　拡張されたRiemann予想と素数判定の計算量

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

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

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

＜教科書＞

“U-Basicによるコンピュータ整数論”木田，牧野　日本評論社
この本は絶版なのでそのＰＤＦ版をダウンロードしてください。
(http://trex.cc.kogakuin.ac.jp/master1/Number_Theory.pdfにあります）

＜参考書＞

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

＜オフィスアワー＞

月曜日　午前11時から12時　新宿校舎27階数学研究室

＜学生へのメッセージ＞

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