プロスの定理

数論において、プロスの定理はプロス数の素数性判定である。

これは^[1] [ ^2]で、pがProth数でk 2 ⁿ + 1の形式 でkが奇数かつk < 2 n^であり、

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}},}$

pは素数です。この場合、pはProth 素数と呼ばれます。これは実用的なテストです。p が素数の場合、選択されたaが機能する確率は約 50 パーセントであり、さらに、計算はmod pであるため、 pより小さいaの値のみを考慮する必要があります。

しかし、実際には、pの2乗非剰余は修正ユークリッドの互除法^{[引用が必要]}によって見つけられ、 aの値として取られる。なぜなら、a がp を法とする2乗非剰余であれば、その逆も真であり、テストは決定的だからである。そのようなaの場合、ルジャンドル記号は

${\displaystyle \left({\frac {a}{p}}\right)=-1.}$

したがって、多くのモンテカルロ 素数判定(偽陽性を返す可能性のあるランダム化アルゴリズム)とは対照的に、Proth の定理に基づく素数判定アルゴリズムはラスベガス アルゴリズムであり、常に正しい答えを返しますが、実行時間はランダムに変化します。上記のように、a が二次非剰余として選択される場合、そのような二次非剰余を見つけるのに費やされる時間を除いて、実行時間は一定であることに注意してください。そのような値を見つけるのは、実際のテストに比べて非常に高速です。

定理の例としては次のようなものがあります。

• p = 3 = 1(2 ¹ ) + 1の場合、2 ^(3-1)/2 + 1 = 3 は 3 で割り切れるので、3 は素数です。
• p = 5 = 1(2 ² ) + 1の場合、3 ^(5-1)/2 + 1 = 10 は 5 で割り切れるので、5 は素数です。
• p = 13 = 3(2 ² ) + 1の場合、5 ^(13-1)/2 + 1 = 15626 は 13 で割り切れるので、13 は素数です。
• p = 9 は素数ではないので、 a ^(9-1)/2 + 1 が 9 で割り切れるようなa は存在しません。

最初の Proth 素数は次のとおりです ( OEISの配列A080076 )。

3、5、13、17、41、97、113、193、241、257、353、449、577、641、673、769、929、1153 … 。​​​​​​

2016年時点で知られている最大のProth素数^{[アップデート]}は で、9,383,761桁の長さです。^{[3]これは、} PrimeGridボランティアコンピューティングプロジェクトでPeter Szabolcsによって発見され、2016年11月6日に発表されました。 ^[4]これは、2024年1月時点で11番目に大きい既知の素数であり、2023年に追い抜かれるまで最大の既知の非メルセンヌ素数でした。 ^[5]そして最大のコルベール数です。^[要出典] 2番目に大きい既知のProth素数は で、PrimeGridによって発見されました。^[6]${\displaystyle 10223\cdot 2^{31172165}+1}$ ${\displaystyle 202705\cdot 2^{21320516}+1}$

この定理の証明にはポックリントン・レーマー素数判定法が使われており、ペパンの判定法の証明とよく似ています。証明は参考文献にあるリベンボイムの本の 52 ページにあります。

フランソワ・プロス（1852–1879）は1878年にこの定理を発表した。^{[7] [8]}

• ペパン検定（ k = 1 の特別なケース 、ただしa  = 3 を選択）
• シェルピンスキー数

• Weisstein, Eric W.「Proth の定理」。MathWorld。