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

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

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

　This is a graduate-level prime number. Algorithms on prime number are very important in the
field of information. For example cryptography and code theory. Public key cryptography
are based on a theory of prime factorization.

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

�T 連分数
　１　連分数の定義と計算法
　２　いろいろな数の連分数表示
　３　平方根の連分数表示と循環性
　４　平方根の連分数展開の計算法
　５　Pellの方程式の解法
�U 素数判定法と各種擬似素数
　6　一般論
　7　擬似素数とカーマイケル数
　8　Euler擬似素数
　9　強擬似素数
　10　素数判定法　一般論
　11　　　　　　　Fermatの方法,Eulerf の方法　　　　　　
　12　　　　　　　Miller-Rabinの方法
　13　　　　　　　Eulerの方法,Miller-Rabinの方法における良い底の割合
14　　　　　　　拡張されたRiemann予想と素数判定の計算量

準備学習は以下のとおり
　講義中出した問題を考えておくこと。また教科書等の該当する箇所を呼んでおくこと。
�T Continued fraction
1 Definition of continued fraction
2 same examples of continued fractions
3 continued fractions of square root
4 calculation method of square root
5 Pell'sequation
II Primarity testing and pseudo primes
6 general theory
7 pseudo primes and Carmichael number
8 Euler pseud prime
9 Strong pseudo prime
10 Primarity testing general theory
11　Fermat's method
　12 Miller-Rabin method
13 Euler method
14 Extended Riemann Hypothes

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

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

Students must submit a report some problem given in lecture.

＜教科書＞

“U-Basicによるコンピュータ整数論”木田，牧野　日本評論社
"Number Thoery used U-Basic" Kida&Makino, Nihon Hyouronsha

＜参考書＞

“初等整数論講義”高木貞治　共立出版
"Elementary Number Theory" Teiji Takagi, Kyoritsu Syuppan

＜オフィスアワー＞

月曜日　昼休み　新宿校舎12F講師室
Monday lunch break　12F staff room

＜学生へのメッセージ＞

レポート問題の中にはかなり大変なものもあるので１，２回でへこたれず何度も手直して提出してください。整数の合同関係を予習（復習）しておくと理解がしやすい。