数論基礎特論（Elementary Number Theory）[1308]

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

　Mathemactica, Maple等いわゆる数式処理に用いられる整数計算アルゴリズムの基本を解説する。内容はEuclidの互除法，連立一次合同式，中国剰余の定理，二次合同式，平方剰余の理論を中心に解説する。これらの定理がいかにして具体的な計算応用できるか，その計算効率はどの程度かを丁寧に述べる。また同じ計算でも数学の深い定理を用いると計算速度が格段に速くなることを示す。
上記のような基本的な計算アルゴリズムの内容を理解し実際に作譜する。

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

まず計算における速さ，即ち計算量というものを定義し多項式時間で計算できないと実用的でないことを解説する。さらに商と剰余を厳密に定義し最大公約数，最小公倍数を定義する。これらの値の多項式時間での計算にEuclidの互除法が重要であることを示す。また自明なような定義の合同式からFermat，Wilson，Eulerの各定理のような重要なものが得られることを詳述する。最後に現代整数論のはじまりとなった二次合同式とGaussの平方剰余の定理を述べる。
　

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

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

レポートによるが、内容の間違っているものは返却しどの点が不十分か解説し再提出を求める。（再提出、再々提出して正解なら採点の対象となる）
またレポート問題にはプログラム作成（作譜）もありC言語等に習熟していればこれらの面でも評価する。

＜教科書＞

“U-Basicによるコンピュータ整数論”木田，牧野　日本評論社
この本は絶版なのでこの内容をデータ化したもの
（http://www.rkmath.rikkyo.ac.jp/~kida/kima.htmにある）
をダウンロードして印刷してください。

＜参考書＞

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

＜学生へのメッセージ＞

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

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