素数

小さな素数の求め方

素数のリストを見つける簡単な方法があります。エラトステネスがそれを作った。エラトステネスの篩（ふるい）という名前が付いている。素数でない数を（ふるいのように）受け止め、素数を通過させるのである。

この方法では、数字のリストと、メソッド中に変化するbという特別な数字が使われます。このメソッドでは、リストの中のいくつかの数字に丸をつけ、他の数字に線を引いていきます。丸で囲んだ数は素数で、消した数は合成数である。最初，すべての数は，丸もつけず，消しゴムもかけない，無地の数である．

やり方はいつも同じです。

1. 1枚の紙に、2からテストされる数までのすべての整数を書きます。1という数字は書かないでください。次のステップに進みます。
2. bを2にした状態でスタートし、次のステップに進みます。
3. リスト内のbを丸で囲む。次のステップに進みます。
4. bから始めて、リストの中のbをさらに数え上げ、その数字を消してください。リストの最後まで、さらにb個数えては消し、数えては消しを繰り返す。次のステップに進みます。
• (例)bが2のとき、2を丸で囲み、4、6、8、などを消します。bが3の場合、3を丸で囲み、6、9、12、...を消す。6と12はすでに消されています。もう一度消してください)
5. bを1つ増やして、次のステップへ。
6. bが消されている場合は、前のステップに戻る。bがリストの中で消されていない数字であれば、第3ステップに進みます。bがリストにない場合は、最後のステップに進みます。
7. (これが最終段階です。)これで完了です。素数にはすべて丸をつけ、合成数にはすべて×をつけました

例えば、2から10までの数字のリストに対して、この方法を行うことができます。最後に、2、3、5、7の数字が丸で囲まれて終わります。これらは素数である。4、6、8、9、10は消されてしまいます。これらは合成数です。

この方法、アルゴリズムは、非常に大きな素数を求めるには時間がかかりすぎる。しかし、フェルマーの原始テスト（ある数が素数かどうかを調べるテスト）やミラー・ラビンの原始テストのような非常に大きな素数に対して使われる方法よりは、複雑ではありません。

素数は何に使われるのか

素数は数学とコンピュータサイエンスにおいて非常に重要である。実際の使用例を以下に示します。非常に長い数は解くのが難しい。素因数を見つけるのが難しいので、暗号や秘密のコードに素数であろう数字が使われることが多い。

• ほとんどの人は銀行のカードを持っていて、ATMを使って自分の口座からお金を引き出すことができます。このカードは、秘密のアクセスコードで保護されています。このコードは秘密にする必要があるため、平文でカードに保存することはできません。そこで、暗号化によりコードを秘匿する。この暗号化には、乗算、除算、大きな素数の余りを求めることなどが使われる。実際にはRSAと呼ばれるアルゴリズムがよく使われる。これは中国の余りの定理を利用したものである。

• 誰かが電子メールにデジタル署名をしている場合、暗号化が行われます。これにより、誰も彼らからのメールを偽ることができないようにします。署名の前に、メッセージのハッシュ値が作成されます。このハッシュ値とデジタル署名を組み合わせて、署名されたメッセージを生成する。使用される方法は、上記の最初のケースと多かれ少なかれ同じである。

• これまでに知られている最大の素数を見つけることは、ある種のスポーツになっている。ある数が素数かどうかを調べるのは、その数が大きいと難しい場合があります。なぜなら、最も早く知られた素因数分解の方法はLucas-Lehmerテストであり、これはメルセンヌ数の特殊な形に依存しているからである。メルセンヌ素数を探索するグループはこちら[1]である。