: ここまでの補足
: JavaScript 言語を通してみる情報処理のしくみ
: for による繰り返し
目次
索引
例題 2.5 与えらた数を素数の積で表すことを素因数分解という.
新聞等に, ``計算機にとっても大きい数の素因数分解は難しい
計算で日常生活のさまざまな場面で利用されている暗号の
安全性の基礎となってる'' という記述があるのを
見たことがないだろうか.
暗号通信の原理は専門的になるのでここでは説明しないが,
簡単な素因数分解のプログラムを書き実行時間
を計測してみよう.
このプログラムは n の素因子をすべて印刷する
プログラムである.
<script language="JavaScript">
n = prompt("n?",3);
i = 2;
while (i <= n) {
while (n % i == 0) {
document.write(i,"<BR>");
n = Math.floor(n/i);
}
i = i+1;
}
</script>
|
n % i は, n を i で割ったあまり,
Math.floor(n/i) は, n を i で割った時の商を戻す.
|
練習 2.4 素数(5 桁, 10 桁, 20 桁, 100 桁, ...)
を二つ掛けた数の素因数分解にどの程度の時間がかかるか
上のプログラムを用いて計測せよ.
桁数を増やすと急激に必要とする時間が増大していくであろう.
もちろん, 高度な数学を用いた素因数分解アルゴリズムをもちいると,
もう少し計算速度は早くなる.
しかしながら, 本質的速度の改善にはなっておらず, すこし桁の大きい数の
素因数分解になるともうお手上げである.
近年, 量子力学を利用した素因数分解の高速計算法が発見されたが,
このような計算を実行できる量子計算機の構築には至っていない.
例えば, ここで紹介した素因数分解の方法
のような計算機で実行可能な手続きのことを, アルゴリズムと呼ぶ.
同じ問題を解く場合でもアルゴリズムの違いにより,
計算の速度はいろいろかわる.
高校数学 A, B の教科書 にとりあげられている,
アルゴリズムには,
- 方程式の近似根を求めるニュートン法.
- 最大公約数 (GCD) を求めるユークリッドの互除法.
- データを並べかえるソート法.
などがある.
余力があれば,
これらのアルゴリズムを JavaScript で記述してみる
とよい.
Nobuki Takayama
平成15年12月5日