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