2002年8月25日更新
ある自然数nが素数かどうか判定する方法について考えます。
nを2からn-1までのすべての数で割ってみて、割り切れないかどうか調べる。
この方法の場合、nが例えば200桁の数だとすると、200桁回の計算が必要になります。今のパソコンは1GHz CPUと歌っているので、仮に1秒間に9桁回計算できると考えると、計算を完了するのに191桁秒掛かります。1年は8桁秒(31536000秒)なので183桁年掛かることになります。
実際にはn-1まで計算しなくてもよさそうです。nが合成数(素数でない数)の場合、n=abとなる自然数a, bが存在します。aとbを掛けると、nになるのだから、a, bのうちどちらかはnの平方根以下であり、どちらかはnの平方根以上です。従って、合成数かどうか(素数でないかどうか)を確認するには、nの平方根以下の自然数で割り切れるかどうか調べればよいです。
nを2から√nまでのすべての数で割ってみて、割り切れないかどうか調べる。
この方法の場合、nが200桁の数だとすると、100桁回の計算が必要になります。今のパソコンで計算を完了するのに91桁秒掛かります。83桁年掛かることになります。
もし√nまでの素数のテーブルを持っているとしたら、素数についてだけ調べたらいいです。
nを2から√nまでのすべての素数で割ってみて、割り切れないかどうか調べる。
xまでの素数の数は、素数定理からおよそ、個あります。従って、この方法の場合、nが200桁の数だとすると、98桁回の計算が必要になります。パソコンで81桁年掛かることになります。
方法2と3の間に、テーブルを作りながら調べる方法が考えられますが、これがエラトステネスの篩と呼ばれる方法です。
これらの方法は、ある数の因数を探す、すなわち、ある数の素因数分解を試みる方法です。大きな数を素因素分解することは、大変な計算を必要とする感じがします。実際、今のところ、大きな数を効率よく素因数分解するアルゴリズムは発見されていません。
しかし、約数(因数)を知らなくても、ある条件を満たす数は合成数であることを示すことができます。
nを奇数とする。すると、nは(k: 整数、q: 奇数)と表すことができる。ある自然数aに対して以下の2つの条件が成り立つ時、nは合成数である。
(a) aqをnで割った余りが1でない。
(b) i=0, 1, ..., k-1すべてに対して、をnで割った余りがn-1でない。
例えば、200桁の数nからkとqを求めるには、660回程度の割り算で求めることができます。(以下、工事中)
Copyright © 2001-2002 ICHIKAWA, Yuji