平成１３年度 専門コア情報処理演習
y
（理学部 数理情報科学科イ組 対象、塩田教官）
y
１月８日の教材
今日は計算量理論を体験します。
上手な計算と下手な計算ではどれだけコスト（時間、電気代等々）に差が出るか実感しましょう。
□ サンプルプログラムのコピー
塩田のホームディレクトリからサンプルプログラムをコピーしてください。
cp ~shiota/test5.p .
cp ~shiota/test6.p .
(
授業終了に伴い、教材はこちらに移動しました
:
test5.p
test6.p
)
□ べき乗計算
代表的な公開鍵暗号である RSA 暗号では、
a^e mod n
というべき乗計算が、10進150桁程度の a, e, n に対して行われます。 test5.p はそのサンプルプログラムです。
コンパイルして実行してみましょう。
pc -o test5 test5.p ; test5
実行時間が表示されますが、 単純に１回１回掛けて行くと10進8桁程度でもこれだけの時間が掛かってしまうのに対し、 反復２乗法というテクニックを用いると瞬時に計算が終わっていることに注目してください。
□ 素数判定
test6.p は素数判定のサンプルプログラムです。
定義を正直に読むと、自然数 n は、2 以上 n 未満の数で割り切れないとき、素数である訳ですが、
n が奇数なら、偶数で割ってみる必要はない
n の平方根より大きい数で割ってみる必要はない
（n の平方根より大きい約数があれば、商は平方根より小さい約数になるので）
ということを考慮すると計算は飛躍的に早くなります。
コンパイルして実行してみましょう。
pc -o test6 test6.p ; test6
□ ユークリッドのアルゴリズム
前回のユークリッドのアルゴリズムは ふたつの自然数 a, b の最大公約数 d と
d = a×x + b×y
を満たす整数 x, y を求めるアルゴリズムでした。
a, b を素因数分解してから最大公約数 d を求めることは絶望的に時間が掛かります。
（素因数分解の困難さが RSA 暗号の安全性のキーポイントです。）
また、「 d が求まった段階で x, y を求める」という問題も
x = 1, 2, 3 , ...
について順番に
d - a×x が b で割り切れるかどうか
調べていたのでは、やはり絶望的に時間が掛かってしまいます。
という訳で、ユークリッドのアルゴリズムは極めて優秀なアルゴリズムと言えます。
□ 今日は課題はありません
今日は課題はありません。サンプルプログラムの数字を変えたりして 計算量理論を楽しんでください。
専門コア情報処理演習 '01 のページへ