プロスプライム

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

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]

Proth 数の素数性は、同様の大きさを持つ他の多くの数よりも簡単にテストできます。

Proth数はの形をとり、kとnは正の整数、は奇数、 です。Proth素数とは、素数であるProth数です。^{[2] [3]}という条件がなければ、1より大きい奇数はすべてProth数になります。^[4]${\displaystyle N=k2^{n}+1}$${\displaystyle k}$${\displaystyle 2^{n}>k}$${\displaystyle 2^{n}>k}$

プロス数の素数性はプロスの定理で検証できる。プロス数が素数であるのは、 ${\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 は最大で時間で実行される決定論的アルゴリズムを作成しました。ここで、Õ はソフト O表記です。Proth 素数の一般的な検索では、通常、は固定 (例: 321 素数検索またはシェルピンスキー問題) または の順序(例: カレン素数検索) のいずれかです。これらの場合、アルゴリズムは最大で 時間で実行されます。または、すべての に対して 時間です。時間で実行されるアルゴリズムもあります。^{[2] [6]}${\displaystyle {\tilde {O}}((k\log k+\log N)(\log N)^{2})}$${\displaystyle k}$${\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})}$

フェルマー数はプロス数の特殊なケースであり、k =1です。このようなシナリオでは、ペパンのテストにより、フェルマー数の素数性を決定論的に検証または偽とするには、基数a = 3のみをチェックする必要があることが証明されています。

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

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

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

2023 年 7 月現在、PrimeGridは Proth 素数探索の主要なコンピューティング プロジェクトです。主なプロジェクトは次のとおりです。

• 一般的なProth素数検索
• 321 素数探索（ の形の素数、第二種タビト素数とも呼ばれる）${\displaystyle 3\times 2^{n}+1}$
• 27121 素数探索（およびの形式の素数探索）${\displaystyle 27\times 2^{n}+1}$${\displaystyle 121\times 2^{n}+1}$
• カレン素数探索（形式の素数を探す）${\displaystyle n\times 2^{n}+1}$
• シェルピンスキー問題 (およびその素数と拡張一般化) - kが次のリストに含まれる形式の素数を検索します。${\displaystyle k\times 2^{n}+1}$

21181, 22699, 24737, 55459, 67607, 79309, 79817, 91549, 99739, 131179, 152267, 156511, 163187, 200749, 209611, 222113, 225931, 227723, 229673, 237019, 238411} です。

2023年6月現在、発見された最大のプロス素数は以下の通りである。^[11]

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

また、Proth素数は、ディフィー・ヘルマン問題と離散対数問題の間のデン・ブール還元を最適化することができる。素数55×2286 ⁺  1はこのように使用されている。^[21]

Proth素数は単純な2進表現を持つため、例えばMicrosoftでは事前計算を必要とせずに高速なモジュラー縮約にも使用されてきた。^[22]