情報システム評価学’02 レポート問題

問題１　〔やさしい問題）

整数 a と 奇数r を入力とし、 a の (r-1)/2　乗をr で割った剰余を計算するプログラムを書きなさい。
但し、できるだけ高速なもの。　計算時間についても簡単に述べよ。 使用言語は何でも構わない

問題２

上記のプログラムを用い、 r = 21701 とr = 748747 に対して a=2,3,...,10 までの結果を出力しなさい。　
また、 この結果から何が言えるかを述べなさい。　

問題３

　有限体Fの乗法群には必ず生成元があること、 即ちFがn個の元を持つとき、Fの元ｇで、n-1乗すると初めて１になる ものが存在する事を示しなさい。
　　 参考文献：　藤崎源二郎：体とGalois理論I　（岩波基礎数学講座） 定理２．２７．

問題４

　ある整数a と自然数ｋを与えられた時、 aが他の整数のｋ乗になるかどうか （即ち、aのｋ乗根が整数であるかどうか）を判定する アルゴリズムを考えよ。
但し、計算時間はaの桁数（つまりlog a) の多項式で押さえられないといけない。
ヒント：　二分探索もしくはニュートン法を用いればできる。 他の手法でもよい。

問題５

　授業で示した２通りの素数判定アルゴリズム （ランダムアルゴリズムと、乱数を用いないアルゴリズム） それぞれの計算時間を比較せよ。

問題６　（Research　Problem)

　上記の計算時間を改良するためのアイデアを考えよ。 （アイデアのみで、解析が無くても、あるいは正しくなくてもよい）

問題７　〔難しい問題）

　有限体$F_p$ を係数に持つ　n 次多項式　 f(x) が与えられた時、それが 既約多項式であるかどうかを高速に判定する方法を考えなさい。
因数分解をするBerlekamp's algorithmを用いるのなら、 その概略を述べること。
参考文献：　D. Knuth, The art of programming II (Seminumerical Algorithms) pp.439--450.

　問題８

　１月２７日の数理談話会 2003年1月27日（月）13:30--15:00　 に出席し、ノートを提出せよ。（談話会は出席者をチェックするので そのつもりで）。

　問題９　

　自分が興味を持っているコンピュータ科学の問題に付いて 徳山にわかるように説明してください。