確率的素数のソースを表示

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

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

決まった底''a''の場合、合成数がその底で確率的素数（つまり擬素数）になることは珍しい。例えば、最大{{Nowrap|25 × 10<sup>9</sup>}}のとき、11,408,012,595個の奇数の合成数があるが、底が2の擬素数は21,853個のみである<ref name="PSW">{{Cite journal|last=Carl Pomerance|last2=John L. Selfridge|last3=Samuel S. Wagstaff, Jr.|date=July 1980|title=The pseudoprimes to 25·10<sup>9</sup>|url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf|journal=Mathematics of Computation|volume=35|issue=151|pages=1003–1026|DOI=10.1090/S0025-5718-1980-0572872-7|JSTOR=2006210}}</ref>{{Rp|p. 1005}}。同じ範囲にある奇数の素数の数は1,091,987,404である。

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

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

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

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

== バリエーション ==
'''底''a''のオイラー確率的素数'''は、任意の素数''p''に対して''a''<sup>(''p''&nbsp;&#x2212;&nbsp;1)/2</sup> = <math>(\tfrac{a}{p})</math> (mod&nbsp;''p'')（ここで <math>(\tfrac{a}{p})</math> は[[ヤコビ記号]]）というやや強い定理により素数と示される整数である。合成数であるオイラー確率的素数は、底''a''の[[オイラー・ヤコビ擬素数]]と呼ばれる。底2のオイラー・ヤコビ擬素数で最小のものは561である（<ref name="PSW">{{Cite journal|last=Carl Pomerance|last2=John L. Selfridge|last3=Samuel S. Wagstaff, Jr.|date=July 1980|title=The pseudoprimes to 25·10<sup>9</sup>|url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf|journal=Mathematics of Computation|volume=35|issue=151|pages=1003–1026|DOI=10.1090/S0025-5718-1980-0572872-7|JSTOR=2006210}}</ref>の1004ページ参照）。25·10<sup>9</sup>未満には底2のオイラー・ヤコビ擬素数は11347個ある（の1005ページ参照）。

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

: <math>a^d\equiv 1\pmod n,\;</math>

もしくは

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

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

底2の強い擬素数で最小のものは2047である（<ref name="PSW">{{Cite journal|last=Carl Pomerance|last2=John L. Selfridge|last3=Samuel S. Wagstaff, Jr.|date=July 1980|title=The pseudoprimes to 25·10<sup>9</sup>|url=//math.dartmouth.edu/~carlp/PDF/paper25.pdf|journal=Mathematics of Computation|volume=35|issue=151|pages=1003–1026|DOI=10.1090/S0025-5718-1980-0572872-7|JSTOR=2006210}}</ref>の1004ページ参照）。25·10<sup>9</sup>未満には底2の強い擬素数は4842個ある（の1005ページ参照）。

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

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

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

== 関連項目 ==

* {{仮リンク|ベイリー–PSW素数判定法|en|Baillie-PSW primality test}}
* {{仮リンク|オイラー・ヤコビ擬素数|en|Euler–Jacobi pseudoprime}}
* [[カーマイケル数]]
* [[リュカ擬素数]]
* [[ミラー–ラビン素数判定法]]
* [[:en:Provable prime]]

== 外部リンク ==

* [http://primes.utm.edu/glossary/page.php?sort=PRP The prime glossary &#x2013; Probable prime]
* [http://www.primenumbers.net/prptop/ The PRP Top 10000 (the largest known probable primes)]

== 脚注 ==
{{Reflist}}
{{素数の分類}}

{{DEFAULTSORT:かくりつてきそすう}}
[[Category:擬素数]]
[[Category:数学に関する記事]]