工学部 2015 年度「情報数学」(富永) 課題レポート第3回(150 点) 問題

■ 工学部 2015 年度「情報数学」(富永)
課題レポート第３回(150 点)
問題
2015.08.28(金)
P.1
配点合計がほぼ 150 点満点となるように、2～4 問を選択して解答せよ。満点が 150 点に達しなくても提出してよい。
配点合計を超える解答は、超過分について、×0.5 換算の加点とする。ただし、200 点で打切とする。
オンラインの提出先は、\\stfile\Report\tominaga\InfoMath\Report3\ のアカウント名の下で、主ファイル名は Report3 とする。
【問題 3-01】 50 点
線形合同法による疑似乱数
[第 2-1 章第 10 節]
疑似乱数の生成算法である線形合同法について説明せよ。
出典を明記して、複数の文献を参考にし、文章を再構成する。例示を追加したり、情報数学の授業内容との関連性を補足する。
(1)
(2)
(3)
(4)
定義式と周期性について、例を挙げながら述べよ。
利点と欠点を挙げよ。
MS Excel またはプログラム言語で実装し、幾つかの実験をして考察せよ。
非常に高性能な擬似乱数の生成算法であるメルセンヌ・ツイスターについて説明せよ。
非常に難しいので、原理は概要だけでよい。どこが優れているか、何に実装されているかについても述べる。
【問題 3-02】 50 点
線形帰還シフトレジスタによる疑似乱数
[第 4-3 章第 08,09 節]
線形合同法に代わる疑似乱数の生成算法について調べよ。
(1) 線形帰還シフトレジスタ LFSR について説明せよ。定義、例示、性質、用途など。
(2) 新しい擬似乱数の生成算法である Xorshift 法について説明せよ。
(3) Xorshift 法をプログラム言語で実装して、幾つかの実験をして、線形合同法と比較しながら考察せよ。
【問題 3-03】 50 点
RSA 式公開鍵暗号系
[第 2-1 章第 04～08 節]
RSA 式公開鍵暗号系について、説明せよ。
出典を明記して、複数の文献を参考にし、文章を再構成する。例示を追加したり、情報数学の授業内容との関連性を補足する。
(1)
(2)
(3)
(4)
公開鍵暗号系について、秘密鍵暗号系と対比して、説明せよ。
フェルマーの定理など、RSA 暗号の基本原理について、説明せよ。
RSA 暗号を実際に利用するための方法や注意点を述べよ。
公開鍵暗号系について、他の手法である離散対数法について、説明せよ。定義、例示、性質、欠点、応用など。
楕円暗号法は難しいので、触れる程度でよい。
【問題 3-04】 50 点
素数判定
[第 1-3 章第 03,06 節]
レポート本文には、ソースコードの主要な部分を掲載し、解説を付ける。実行結果も掲載する。
(1) 8 桁までの正整数 n が素数であるかどうかを、2 から順に割って調べるプログラムを実装せよ。効率化を考えよ。
このプログラムを利用して、8 桁の素数 p を見つけよ。
(2) p が素数であるための必要十分条件は、(p-1)!+1 が p で割り切れることである。これをウィルソンの定理という。
4 桁までの正整数(1 万未満)に対し、ウィルソンの定理による素数判定を実装せよ。
32 ビット符号付整数でのオーバーフローに注意する(乗算が正しく行われないことがある)。
(3) ウィルソンの定理により、理論的には、素数であるかどうかを、素因数分解せずに調べることができるが、効率はそれほど良くない。
(1)と(2)の計算時間を比較する。処理時間を計る関数を利用するか、同じ計算を大量に繰り返して目測する(反復回数で割る)。
桁数の異なる素数で幾つか実験し、桁数と計算時間の相関性を考察する。
■ 工学部 2015 年度「情報数学」(富永)
【問題 3-05】 50 点
課題レポート第３回(150 点)
1 次不定方程式とユークリッドの互除法
問題
2015.08.28(金)
P.2
[第 2-1 章第 05 節] [第 2-2 章第 02 節]
1 次不定方程式 aX + bY = c の具体解を、ユークリッドの互除法で求めるプログラムを作成せよ。
ただし、定数項 c が、d＝gcd(a,b) で割り切れないと、解は存在しない。
レポート本文には、ソースコードの主要な部分を掲載し、解説を付ける。実行結果も掲載する。
係数を r[0]＝a, r[1]＝b とおき、変数を x[0]＝Y, x[1]＝X とおく。与式は、 r[0]×x[1]＋r[1]×x[0]＝c と表される。
ここで、除法等式 r[k] ＝ r[k+1]×q[k+1]＋r[k+2] を考える。
すなわち、剰余列 r[k+2]＝r[k]%r[k+1] および整商列 q[k+1]＝r[k]/r[k+1] と定義する。
このとき、より簡単な場合に帰着した方程式は r[k+1]×x[k+2]＋r[k+2]×x[k+1]＝c ; x[k+2]＝q[k+1]×x[k+1]＋x[k] と表せる。
r[k+2]＝0 に達したとき、 x[k+2]＝c/r[k+1], x[k+1]＝0 と具体解が求められる。
これから、x[k]＝x[k+2]－q[k+1]×x[k+1] を逆算していく。
ポインタ引数を使うと、関数 int euclid(int a, int, b, int c, int *x, int, *y) として、再帰法で簡潔に実装できる。
返却値は、解の存在を 0/1 で返す。この場合、整商列を用いず、 x[k+1]＝(c－r[k+1]×x[k+2])/r[k+2] で求める。
初期条件および漸化式の両方で、解の有無による場合分けに注意する。
euclid(28,11,1, *, *) → euclid(11,6,1, *, *) → euclid(6,5,1, *, *) → euclid(5,1,1, *, *) → euclid(1,0,1, *, *)
↓
euclid(28,11,1, 2,-5) ← euclid(11,6,1,-1, 2) ← euclid(6,5,1, 1,-1) ← euclid(5,1,1, 0, 1) ← euclid(1,0,1, 1, 0)
【問題 3-06】 50 点
多倍長整数の加減乗算
[第 3-3 章第 04 節]
レポート本文には、ソースコードの主要な部分を掲載し、解説を付ける。実行結果も掲載する。
(1) 16 桁までの正整数の加算ができるプログラムを実装せよ。17 桁目への繰上りは、起こらないとする。
8 桁以下と 9 桁以上で、下位桁と上位桁に分け、それぞれ加算する。繰上りに注意する。
被加数と加数は、1 行ずつ入力する。各行の入力は、1234 億 1234 万 5678 なら 1234 12345678 のように、8 桁区切りで空白を入れる。
書式付入力 scanf(“%d”) では、16 桁の正整数は入力できないためである。
ここで、1234 1234 は、1234 億(0 万)1234 すなわち 1234 00001234 を意味する。8 桁以下の場合、0 2345 のように入力する。
加算結果の出力は、1234 00005678 のように、8 桁区切りとし、必要な 0 を補う。
(2) (1)のプログラムを以下のように、改良する。
1234 00001234 や 5678 のように、より自然な入力が可能なようにする。
17 桁目に繰上った場合も正しく出力するが、オーバーフローであることを明記する。
演算子 + または - も入力し、減算にも対応する。
ただし、先頭に 0 がある数字列は、8 進数と解釈されるので、少し工夫が必要である。
行入力 fgets() と sscanf() を使う、文字入力 getchar() で先頭の 0 を読み捨てる(改行も自分で検出)、
文字配列を走査して 0 を飛ばす、数値変換 atoi() を使うなど。
(3) 8 桁までの正整数の乗算ができるプログラムを実装せよ。入力は、12345678 のように、区切りなしのままとする。
内部では、A＝a1×1 万＋a0 のように、下位桁(4 桁以下)と上位桁(5 桁以上)に分けて格納する。
乗法公式 A×B＝(a1×1 万＋a0)×(b1×1 万＋b0)＝(a1×b1)×1 億＋(a1×b0＋a0×b1)×1 万＋(a0×b0) で展開して計算する。
繰上りに注意する。乗算結果は、16 桁になる可能性がある。カラツバ法を使うと少し計算が速くなる。
【問題 3-07】 50 点
実数の多進法表記
[第 3-3 章第 06 節]
基数 r と桁数 n、有理分数の分子 p と分母 q を入力し、p/q を r 進法で、小数点以下 n 桁までを表すプログラムを実装せよ。
ただし、0＜p＜q とする。0. の部分は省略する。また、n+1 桁目は、切り捨てる(n 桁目まで正しい値になっている)。
レポート本文には、ソースコードの主要な部分を掲載し、解説を付ける。実行結果も掲載する。
入力
出力
n
p
p r
2
1
2 2 ⇒ 10
5 124 1000 5 ⇒ 03022
; 1/2
＝ 0.5[10]
＝ 0.1[2]
; 124/1000 ＝ 0.124[10] ＝ 0.03022‥[5]

Download Report