next up previous contents index
: ここまでの補足 : 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 は, ni で割ったあまり, Math.floor(n/i) は, ni で割った時の商を戻す.

練習 2.4   素数(5 桁, 10 桁, 20 桁, 100 桁, ...) を二つ掛けた数の素因数分解にどの程度の時間がかかるか 上のプログラムを用いて計測せよ. 桁数を増やすと急激に必要とする時間が増大していくであろう. もちろん, 高度な数学を用いた素因数分解アルゴリズムをもちいると, もう少し計算速度は早くなる. しかしながら, 本質的速度の改善にはなっておらず, すこし桁の大きい数の 素因数分解になるともうお手上げである. 近年, 量子力学を利用した素因数分解の高速計算法が発見されたが, このような計算を実行できる量子計算機の構築には至っていない.

例えば, ここで紹介した素因数分解の方法 のような計算機で実行可能な手続きのことを, アルゴリズムと呼ぶ. 同じ問題を解く場合でもアルゴリズムの違いにより, 計算の速度はいろいろかわる.

高校数学 A, B の教科書 にとりあげられている, アルゴリズムには,

  1. 方程式の近似根を求めるニュートン法.
  2. 最大公約数 (GCD) を求めるユークリッドの互除法.
  3. データを並べかえるソート法.
などがある. 余力があれば, これらのアルゴリズムを JavaScript で記述してみる とよい.



Nobuki Takayama 平成15年12月5日