About: 確率的素数

数論において、確率的素数（probable prime, PRP）は、ほとんどの合成数は満たさないが全ての素数が満たす特定の条件を満たす整数。確率的素数には様々な条件がある。合成数である確率的素数（擬素数と呼ばれる）が存在する可能性があるが、一般的にはこのような例外を少なくするために条件が選ばれる。 フェルマーの小定理に基づくフェルマーの合成数判定は次のように進む。整数nが与えられ、nの倍数ではない整数aをいくつか選び出す（通常は1 < a < n − 1の範囲でaを選ぶ）。an − 1 modulo nを計算する。結果が1でない場合、nは合成数である。結果が1である場合、nは素数である可能性がある。nはこのときaを底とする確率的素数という。aを底とする弱い確率的素数はaを底とする確率的素数であるが、aを底とする強い確率的素数ではない整数のことである（以下参照）。 決まった底aの場合、合成数がその底で確率的素数（つまり擬素数）になることは珍しい。例えば、最大25 × 109のとき、11,408,012,595個の奇数の合成数があるが、底が2の擬素数は21,853個のみである。同じ範囲にある奇数の素数の数は1,091,987,404である。