プロスプライム

プロス数とは、次の形式の自然数Nのことである。${\displaystyle N=k\times 2^{n}+1}$ここで、kとnは正の整数であり、kは奇数であり、${\displaystyle 2^{n}>k}$プロス素数とは、素数であるプロス数のことです。これらはフランスの数学者フランソワ・プロスにちなんで名付けられました。^{[ 2 ]}最初のいくつかのプロス素数は

3、5、13、17、41、97、113、193、241、257、353、449、577、641、673、769、929、1153、1217、1409、1601、2113、2689、 2753、3137、3329、3457、4481、4993、6529、7297、7681、7937、9473、9601、9857 ( OEIS : A080076  )。

プロス素数が無限に存在するかどうかは未解決の問題である。2022年に、プロス素数の逆数の和が0.747392479に近い実数に収束することが示されたが、これはプロス数の逆数の和の値1.093322456よりもかなり小さい。^{[ 1 ]}

プロス数の素数性は、同程度の大きさの他の多くの数よりも容易に検証できる。

プロス数は次の形式をとる。${\displaystyle N=k\times 2^{n}+1}$ここで、kとnは正の整数である。${\displaystyle k}$奇妙で${\displaystyle 2^{n}>k}$プロス素数とは、素数であるプロス数のことである。^{[ 2 ] [ 3 ]}条件なしで${\displaystyle 2^{n}>k}$1より大きいすべての奇数はプロス数となる。^{[ 4 ]}

プロス数の素数性はプロスの定理で判定でき、プロス数は${\displaystyle p}$素数であるのは、整数が存在する場合に限る。${\displaystyle a}$そのために

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$^{[ 3 ] [ 5 ]}

この定理は、多くのランダムな選択をチェックすることによって、素数の確率的テストとして使用できます。${\displaystyle a}$かどうか${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$ これがいくつかのランダムな場合に成り立たない場合${\displaystyle a}$そうなると、その数は非常に${\displaystyle p}$は合成数です。 このテストはラスベガスアルゴリズムです。偽陽性を返すことはありませんが、偽陰性を返す可能性があります。つまり、合成数を「おそらく素数」と報告することはありませんが、素数を「合成数の可能性あり」と報告する可能性があります。

2008年、Szeは最大で${\displaystyle {\tilde {O}}((k\log k+\log N)(\log N)^{2})}$時間、ここで Õ はソフト O表記です。プロス素数の典型的な検索では、通常${\displaystyle k}$は固定されているか（例：321 素数探索またはシェルピンスキー問題）、またはオーダーが${\displaystyle O(\log N)}$（例：カレン素数探索）。これらの場合、アルゴリズムは最大で$\displaystyle {\tilde {O}}((\log N)^{3})}$、 または${\displaystyle O((\log N)^{3+\epsilon })}$全員のための時間${\displaystyle \epsilon >0}$また、次のようなアルゴリズムも存在します。$\displaystyle {\tilde {O}}((\log N)^{24/7})}$時間。^{[ 2 ] [ 6 ]}

フェルマー数はプロス数の特殊なケースであり、k = 1の場合である。このような場合、ペパンの判定法によれば、フェルマー数の素数性を決定論的に検証または反証するには、基数a = 3のみをチェックすればよい。

2022年現在既知の最大のプロス素数は${\displaystyle 10223\times 2^{31172165}+1}$桁数は 9,383,761 桁です。^{[ 7 ]}これは、 PrimeGridボランティアコンピューティングプロジェクトで Szabolcs Peter によって発見され、2016 年 11 月 6 日に発表されました。^{[ 8 ]}また、既知の非メルセンヌ素数としては 3 番目に大きいものです。^{[ 9 ]}

プロジェクトSeventeen or Bust は、特定の Proth 素数を探す${\displaystyle t}$78557が最小のシェルピンスキー数であることを証明するために（シェルピンスキー問題）、2007年までに11個の大きなプロス素数が発見された。素数シェルピンスキー問題および拡張シェルピンスキー問題に対する同様の解決により、さらにいくつかの数が発見されている。

フェルマー数の約数は${\displaystyle F_{n}=2^{2^{n}}+1}$常に次の形式${\displaystyle k\times 2^{n+2}+1}$新しいプロス素数がフェルマー数を割り切るかどうかを判定するのが慣例である。^{[ 10 ]}

2025年1月現在、PrimeGridはプロス素数探索における主要な計算プロジェクトである。主なプロジェクトは以下のとおりである。

• 一般的なプロスプライム検索
• 321 素数探索（次の形式の素数を検索）$3×2n+1$（第2種タビット素数とも呼ばれる）
• 27121 素数探索（次の形式の素数を検索）$27×2^n+1$そして${\displaystyle 121\times 2^{n}+1}$）
• カレン素数探索（次の形式の素数を検索）${\displaystyle n\times 2^{n}+1}$）
• シェルピンスキー問題（およびその素数および拡張一般化） – の形の素数を探す${\displaystyle k\times 2^{n}+1}$ここでkはこのリストに含まれる：

k ∈ {21181, 22699, 24737, 55459, 67607, 79309, 79817, 91549, 99739, 131179, 152267, 156511, 163187, 200749, 209611, 222113, 225931, 227723, 229673, 237019, 238411}

2023年6月現在、発見された最大のプロス素数は次のとおりです。^{[ 11 ]}

第2種プロス数は、次の形式の自然数Nである。${\displaystyle N=k\times 2^{n}-1}$ここで、kとnは正の整数であり、kは奇数であり、${\displaystyle 2^{n}>k}$第二種プロス素数とは、素数である第二種プロス数のことである。 第二種プロス素数の最初の数個は

3, 7, 11, 23, 31, 47, 79, 127, 191, 223, 239, 383, 479, 607, 863, 991, 1087, 1151, 1279, 1471, 1663, 2111, 2239, 2687, 2879, 3391, 3583, 3967, 5119, 5503, 6143, 6271, 6911, 7039, 8191, 8447, 8831, 9343 ( OEIS : A112715  )。

2 種最大の Proth 素数は、Lucas–Lehmer–Riesel テストを使用して素数判定できます。

2025年1月現在、PrimeGridは第二種プロス素数を探索する主要な計算プロジェクトである。主なプロジェクトは以下のとおりである。

• 第二種プロス素数探索
• 321 素数探索（次の形式の素数を検索）$3×2ⁿ⁻¹$（タビット素数とも呼ばれる）
• 27121 素数探索（次の形式の素数を検索）$27×2ⁿ⁻¹$そして${\displaystyle 121\times 2^{n}-1}$）
• ウッドール素数探索（次の形式の素数を検索）${\displaystyle n\times 2^{n}-1}$）
• リーゼル問題（およびその素数および拡張一般化） – の形の素数を探す${\displaystyle k\times 2^{n}-1}$ここでkはこのリストに含まれる：

k ∈ {23669, 31859, 38473, 46663, 67117, 74699, 81041, 121889, 129007, 143047, 161669, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 384539、386801、397027、409753、444637、470173、474491、477583、485557、494743 }

^{小さなプロス素数（10 200}未満）は、素数ラダー、つまり各項が前の項と「近い」（約10 ^{11以内）素数列を構成するために使用されてきました。このようなラダーは、素数関連の}予想を経験的に検証するために使用されてきました。たとえば、ゴールドバッハの弱い予想は、2008年にプロス​​素数から構成された素数ラダーを使用して8.875 × 10 ³⁰まで検証されました。^{[ 18 ]} （この予想は後にハラルド・ヘルフォットによって証明されました。^{[ 19 ] [ 20 ]}）

また、プロス素数は、ディフィー・ヘルマン問題と離散対数問題の間のデン・ボーア還元を最適化することができる。素数 55 × 2 ²⁸⁶ + 1 はこのように使用されている。^{[ 21 ]}  

プロス素数は単純な二進数表現を持つため、例えばマイクロソフト社によって、事前計算を必要とせずに高速なモジュラー還元にも使用されています。^{[ 22 ]}