確率的素数

数論において、確率的素数（probable prime, PRP）は、ほとんどの合成数は満たさないが全ての素数が満たす特定の条件を満たす整数。確率的素数には様々な条件がある。合成数である確率的素数（擬素数と呼ばれる）が存在する可能性があるが、一般的にはこのような例外を少なくするために条件が選ばれる。

フェルマーの小定理に基づくフェルマーの合成数判定は次のように進む。整数nが与えられ、nの倍数ではない整数aをいくつか選び出す（通常は1 < a < n − 1の範囲でaを選ぶ）。a^{n − 1} modulo nを計算する。結果が1でない場合、nは合成数である。結果が1である場合、nは素数である可能性がある。nはこのときaを底とする確率的素数という。aを底とする弱い確率的素数はaを底とする確率的素数であるが、aを底とする強い確率的素数ではない整数のことである（以下参照）。

決まった底aの場合、合成数がその底で確率的素数（つまり擬素数）になることは珍しい。例えば、最大25 × 10⁹のとき、11,408,012,595個の奇数の合成数があるが、底が2の擬素数は21,853個のみである^[1]^{:p. 1005}。同じ範囲にある奇数の素数の数は1,091,987,404である。

性質

確率的素数の性質は効率的な素数判定アルゴリズムの基礎であり、これは暗号理論に応用されている。これらのアルゴリズムは通常本質的に確率的である。任意の固定したaに対してaを底とする合成数の確率的素数がある一方、任意の合成数nに対して任意にaを選択した場合nが底aに対して擬素数である確率が最大Pであるような決まったP<1が存在することを期待することができる。この判定法をk回繰り返し、毎回新たなaを選ぶと、判定した全てのaに対してnが擬素数である確率は最大P^kであり、これは指数関数的に減少するため、この確率を無視できるほど小さくするためには適度なkのみが必要である（例えばコンピュータハードウェアのエラーの確率と比較して）。

カーマイケル数が存在するため、このことは弱い確率的素数については残念ながら間違いである。ただし、強い確率的素数（P = 1/4, ミラー-ラビン素数判定法）やオイラー確率的素数（P = 1/2, ソロベイ-シュトラッセン素数判定法）などより洗練された確率的素数の概念にはあてはまる。

決定的素数の証明が必要な場合であっても、有用な最初の段階は確率的素数を判定することである。これによりほとんどの合成数を（確実に）迅速に取り除くことができる。

PRP判定は、いくつかのしきい値よりも小さい数の素数性を迅速に確立するために、小さな擬素数の表と組み合わされることがある。

バリエーション

底aのオイラー確率的素数は、任意の素数pに対してa^{(p − 1)/2} = $({\tfrac {a}{p}})$ (mod p)（ここで $({\tfrac {a}{p}})$ はヤコビ記号）というやや強い定理により素数と示される整数である。合成数であるオイラー確率的素数は、底aのオイラー・ヤコビ擬素数と呼ばれる。底2のオイラー・ヤコビ擬素数で最小のものは561である（^[1]の1004ページ参照）。25·10⁹未満には底2のオイラー・ヤコビ擬素数は11347個ある（の1005ページ参照）。

この判定法は1を法とする素数の平方根が1と−1であるという事実を用いることで改善できる。n = d · 2^s + 1（dは奇数）と書ける。nは、底aとする強い確率的素数(SPRP)である。

a^{d}\equiv 1{\pmod {n}},\;

もしくは

a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}{\text{ for some }}0\leq r\leq s-1.\,

底aの強い確率的素数で合成数であるものは、底aの強い擬素数と呼ばれる。全ての底aの強い確率的素数は同じ底のオイラー確率的素数でもあるが、逆は真ではない。

底2の強い擬素数で最小のものは2047である（^[1]の1004ページ参照）。25·10⁹未満には底2の強い擬素数は4842個ある（の1005ページ参照）。

リュカ数列に基づくリュカ確率的素数もある。リュカ確率的素数判定は単独で使うことができる。Baillie-PSW素数判定法は、リュカ判定法と強い確率的素数判定法を組み合わせたものである。

SPRPの例

97が底2の強い確率的素数かどうかを判定する。

ステップ1: $96=d\cdot 2^{s}$ の $d$ と $s$ （ $d$ は奇数）を見つけ出す。
- $s=0$ のとき、 $d$ は $96$ である。
- $s$ を大きくすると、 $96=3\cdot 2^{5}$ より $d=3$ 、 $s=5$ である。
ステップ2: $a$ を $1<a<97-1$ で選び、 $a=2$ を選ぶ。
ステップ3: $a^{d}{\pmod {n}}$ つまり $2^{3}{\pmod {97}}$ を計算する。 $1{\pmod {97}}$ ではないため、次の条件で判定を続ける。
ステップ4: $0\leq r<s$ で $2^{3\cdot 2^{r}}{\pmod {97}}$ を計算する。 $96{\pmod {97}}$ である場合、 $97$ は確率的素数である。そうでなければ、 $97$ は確実に合成数である。
- $r=0:2^{3}\equiv 8{\pmod {97}}$
- $r=1:2^{6}\equiv 64{\pmod {97}}$
- $r=2:2^{12}\equiv 22{\pmod {97}}$
- $r=3:2^{24}\equiv 96{\pmod {97}}$
よって、 $97$ は底2の強い確率的素数である（よって底2の確率的素数である）。

外部リンク

脚注

^ ^a ^b ^c Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). “The pseudoprimes to 25·10⁹”. Mathematics of Computation 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7. JSTOR 2006210.

[PSW-1] Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). “The pseudoprimes to 25·10⁹”. Mathematics of Computation 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7. JSTOR 2006210.

[1]

確率的素数

目次

性質

バリエーション

SPRPの例

関連項目

外部リンク

脚注