数学において素数は重要な存在である。数学と密接な関係にある暗号の世界においても、素数は重要な存在である。公開鍵暗号系のアルゴリズムの仕様を確認してもらえれば、多くの場合において素数をランダムに選択する必要があることがわかると思う。例えば、RSA暗号の鍵生成アルゴリズムでは大きな素数を2つ生成しなければならない。この部分できちんとした素数が作られなければ、暗号の安全性が脆弱になってしまうのである。つまり、素数をランダムに生成するということは暗号の世界において重要と言える。
今回の記事では、素数をランダムに生成するアルゴリズム（以降、素数生成アルゴリズムと呼ぶことにする）を単に紹介するだけでは面白くないので、試行錯誤しながら素数生成アルゴリズムを考えていくことにする。その後、いくつかの素数生成アルゴリズムを紹介し、コストの面（必要となる速度・メモリ）の観点で比較する。最後に、指定されたビット数の素数の生成について言及する。
原始元生成アルゴリズムでは、確定的に（100%の確率で）原始元を生成するアルゴリズムを作るよりも、ある程度大きな確率で原始元を生成するアルゴリズムを作る方が効率がよいという話をした。このある程度大きな確率で原始元を生成するアルゴリズムというのは、ランダムな値を生成するアルゴリズムと、原始元判定アルゴリズムの組み合わせであった。
今回の素数生成アルゴリズムも、同様のアプローチで考えた方が高速であることがわかっている。つまり、素数生成アルゴリズムを考える上で重要な部分は、優秀な素数判定アルゴリズムを考えるという点に帰着される。素数生成アルゴリズムの一部として利用できるぐらい優秀な素数判定アルゴリズムのことを素数テストを呼ぶことにする。
[定義]Primes={bin(n)|n：素数}
つまり、Primesは素数nの2進表現を意味する。
[定義]アルゴリズムMが素数テストとは、MがPrimes⊂coRPを証言するアルゴリズムであるときである。
これは次を意味する。
つまり、素数テストは次の2つの条件を同時に満たしている。
つまり、素数テストに素数でない値が入力されれば1/2以上の確率でrejectされ、素数が入力されれば必ずacceptされるということである。
理想的なアルゴリズムはaccept（素数と判定）されたものは必ず素数で、reject（素数でない）と判定されたものは必ず素数でないものである。しかし、この理想的なものがないとしても、上記の定義のような素数テストさえ存在すれば、このアルゴリズムを何度も繰り返すことで素数でないのにaccpet（素数と判定）される可能性はどんどん低くすることができる。つまり、実質的に素数テストを多段で使ってaccpet（素数と判定）されたものはほとんど素数と考えてよいといえる。
素数判定アルゴリズムには他の方式も存在する。
Miller-Rabinテストなどで効率的に素数を生成できることは示されたが、まだ固定されたビット長の素数の生成についてはまだ言及していない。実際に多くの暗号スキームの鍵生成アルゴリズムなどでは、固定されたビット長のランダムな素数を生成する必要が生じる。
ここではkビットの素数を生成したいとする。そのとき、次の手順で実行すればよい。
1：kビットの奇数nをランダムに生成する。ただし、nの最初と最後のビットを1とおき、残りのk-2ビットの数をそれぞれ独立でランダムに生成する。
2：このnが素数かどうかを調べる。
最初に素数表を使用して、nがある一定の値であるBよりも小さい素数で割り切れるかどうかを調べる。利用するハードウェアやソフトウェアがMiller-Rabinテストでの割り算をどのくらい速いかによって、このBの値は決定される。Miller-Rabinテストより、試行割算法の方がずっと効率的な場合は、より大きなBを選ぶとよい。一般的な例として、B=106と選ばれる。nの約数が見つからなければ、以降を実行する。
次に、k回の繰り返しのMiller-RabinテストのアルゴリズムMR_kにnを入力する。ここでnのMR-witnessが見つからなければ、nは素数である。見つからなければ、nは合成数であるので、ステップ1に戻ってやり直す。
3：最終的に得られたnはkビットの素数とみなせる。
