プロスプライム

プロスプライム
名前の由来	フランソワ・プロス
出版年	1878
出版物の著者	プロス、フランソワ
既知の用語の数	4304683178 2 72以下
推定される項数	無限
の部分列	プロス数、素数
式	k × 2 n + 1
最初の学期	3、5、13、17、41、97、113
最大の既知の用語	10223 × 2 31172165 + 1（2019年12月現在）
OEIS指数	A080076; 正素数: k *2^ m + 1 の形の素数で、k < 2^ m、m ≥ 1が奇数であるもの;

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

素数判定

プロス数の素数性はプロスの定理で検証できる。プロス数が素数であるのは、 $p$ $a$

a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.

^[3]^[5]

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

2008年、Szeは最大で時間で実行される決定論的アルゴリズムを作成した。ここでÕはソフトO記法である。Proth素数の典型的な探索では、は通常、固定値（例：321素数探索やシェルピンスキー問題）またはの位数（例：カレン素数探索）のいずれかである。これらの場合、アルゴリズムは最大で時間、あるいはすべてのに対して時間で実行される。時間で実行されるアルゴリズムも存在する。^[2]^[6] ${\tilde {O}}((k\log k+\log N)(\log N)^{2})$ $k$ $O(\log N)$ ${\tilde {O}}((\log N)^{3})$ $O((\log N)^{3+\epsilon })$ $\epsilon >0$ ${\tilde {O}}((\log N)^{24/7})$

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

大きな素数

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

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

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

2025年1月現在、PrimeGridはProth素数探索における主要なコンピューティングプロジェクトです。主なプロジェクトは以下のとおりです。

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

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]

ランク	プライム	数字	いつ	コメント	発見者（プロジェクト）	参考文献
1	10223 × 2 ^31172165 + 1	9383761	2016年10月31日		シャボルクス・ペテル (シェルピンスキー問題)	^[12]
2	202705 × 2 ^21320516 + 1	6418121	2021年12月1日		パベル・アトナシェフ (拡張シェルピンスキー問題)	^[13]
3	81 × 2 ^20498148 + 1	6170560	2023年7月13日	一般化フェルマー F ₂ (3 × 2 ^5124537 )	ライアン・プロッパー（LLR）	^[11]
4	7 × 2 ^20267500 + 1	6101127	2022年7月21日	分割数 F _20267499 (12)	ライアン・プロッパー（LLR）	^[11]^[14]
5	168451 × 2 ^19375200 + 1	5832522	2017年9月17日		ベン・マロニー (プライム・シェルピンスキー問題)	^[15]
6	7 × 2 ^18233956 + 1	5488969	2020年10月1日	フェルマー F _18233954とF _18233952を割り算する（7）	ライアン・プロッパー	^[16]^[14]
7	13 × 2 ^16828072 + 1	5065756	2023年10月11日		ライアン・プロッパー	^[11]
8	3 × 2 ^16408818 + 1	4939547	2020年10月28日	F _16408814 (3)、F _16408817 (5)、およびF _16408815 (8)を割ります	ジェームス・ブラウン（プライムグリッド）	^[14]
9	11 × 2 ^15502315 + 1	4666663	2023年1月8日	分割F _15502313 (10)	ライアン・プロッパー	^[14]
10	37 × 2 ^15474010 + 1	4658143	2022年11月8日		ライアン・プロッパー	^[14]
11	(2 ^7658613 + 1) × 2 ^7658614 + 1	4610945	2020年7月31日	ガウスメルセンヌノルム	ライアン・プロッパーとセルジュ・バタロフ	^[11]
12	13 × 2 ^15294536 + 1	4604116	2023年9月30日		ライアン・プロッパー	^[11]
13	37 × 2 ^14166940 + 1	4264676	2022年6月24日		ライアン・プロッパー	^[11]
14	99739 × 2 ^14019102 + 1	4220176	2019年12月24日		ブライアン・ニーゴッキ (拡張シェルピンスキー問題)	^[17]
15	404849 × 2 ^13764867 + 1	4143644	2021年3月10日	基数131072の一般化カレン	ライアン・プロッパーとセルジュ・バタロフ	^[11]
16	25 × 2 ^13719266 + 1	4129912	2022年9月21日	F ₁ (5 × 2 ^6859633 )	ライアン・プロッパー	^[11]
17	81 × 2 ^13708272 + 1	4126603	2022年10月11日	F ₂（3 × 2 ^3427068）	ライアン・プロッパー	^[11]
18	81 × 2 ^13470584 + 1	4055052	2022年10月9日	F ₂（3 × 2 ^3367646）	ライアン・プロッパー	^[11]
19	9 × 2 ^13334487 + 1	4014082	2020年3月31日	F _13334485 (3)、F _13334486 (7)、F _13334484 (8)を割ります	ライアン・プロッパー	^[14]
20	19249 × 2 ^13018586 + 1	3918990	2007年3月26日		コンスタンチン・アガフォノフ（セブンティーン・オア・バスト）	^[12]

第二種プロス素数

第二種プロス数とは、 kとnが正の整数、kが奇数、 nが負の整数である自然数 Nのことである。第二種プロス素数とは、nが素数である第二種プロス数である。第二種プロス素数の最初のいくつかは以下の通りである。 $N=k\times 2^{n}-1$ $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 ) 。

第二種最大の Proth 素数は、Lucas-Lehmer-Riesel テストを使用して素数かどうかをテストできます。

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

一般的なProth素数の第2種探索
321 素数探索（形式の素数、タビト素数とも呼ばれる） $3\times 2^{n}-1$
27121 素数探索（およびの形式の素数探索） $27\times 2^{n}-1$ $121\times 2^{n}-1$
ウッドオール素数探索（形式の素数探索） $n\times 2^{n}-1$
リーゼル問題（およびその素数と拡張一般化） - kが次のリストに含まれる形式の素数を探す: $k\times 2^{n}-1$

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]^{[より良い情報源が必要]}）

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

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

参考文献

^ ab ボルソス、ベルタラン;コヴァチ、アッティラ; Tihanyi、Norbert (2022)、「Proth primes の逆数和のタイトな上限と下限」、Ramanujan Journal、59、Springer: 181–198、doi : 10.1007/s11139-021-00536-2、hdl : 10831/83020、S2CID 246024152
^ abc Sze, Tsz-Wo (2008). 「Proth数における決定論的素数証明」. arXiv : 0812.2596 [math.NT].
^ ab Weisstein, Eric W. 「Proth Prime」. mathworld.wolfram.com . 2019年12月6日閲覧。
^ Weisstein, Eric W. 「Proth数」. mathworld.wolfram.com . 2019年12月7日閲覧。
^ Weisstein, Eric W.「Prothの定理」. MathWorld .
^ Konyagin, Sergei; Pomerance, Carl (2013), Graham, Ronald L.; Nešetřil, Jaroslav; Butler, Steve (eds.)「On Primes Recognizable in Deterministic Polynomial Time」The Mathematics of Paul Erdős I , Springer New York, pp. 159– 186, doi :10.1007/978-1-4614-7258-2_12, ISBN 978-1-4614-7258-2
^ コールドウェル、クリス. 「トップ20：プロス」. ザ・プライム・ページズ.
^ Van Zimmerman (2016年11月30日) [2016年11月9日]. 「コルベール数の世界記録が発見されました！」PrimeGrid .
^ コールドウェル、クリス. 「トップ20：最も大きな既知の素数」. The Prime Pages .
^ “The Prime Glossary: Fermat divisor”. primes.utm.edu . 2021年11月14日閲覧。
^ abcdefghijk Caldwell, Chris K. 「The top twenty: Proth」. The Top Twenty . 2019年12月6日閲覧。
^ ab Goetz, Michael (2018年2月27日). 「Seventeen or Bust」. PrimeGrid . 2019年12月6日閲覧。
^ 「PrimeGridの拡張 シェルピンスキー問題素数探索」（PDF）primegrid.comPrimeGrid . 2021年12月28日閲覧。
^ abcdef 「新しいGFN因子」www.prothsearch.com . 2021年11月14日閲覧。
^ 「素数168451×219375200+1の公式発見」（PDF）PrimeGrid . 2019年12月6日閲覧。
^ 「フェルマー因数分解の現状」www.prothsearch.com . 2021年11月14日閲覧。
^ 「素数99739×214019102+1の公式発見」（PDF）PrimeGrid . 2019年12月24日. 2021年11月14日閲覧。
^ Helfgott, HA; Platt, David J. (2013). 「8.875e30までの三元ゴールドバッハ予想の数値的検証」arXiv : 1305.3062 [math.NT].
^ Helfgott, Harald A. (2013). 「三元ゴールドバッハ予想は正しい」. arXiv : 1312.7748 [math.NT].
^ “ハラルド・アンドレス・ヘルフゴット”.アレクサンダー・フォン・フンボルト教授。2019年12月8日に取得。
^ Brown, Daniel RL (2015年2月24日). 「CM55: デン・ブールの縮約をほぼ最適化する特殊素体楕円曲線、Diffie-Hellmanと離散対数の間」(PDF) .国際暗号研究協会: 1–3 .
^ Acar, Tolga; Shumow, Dan (2010). 「特殊モジュライの事前計算なしのモジュラー縮約」(PDF) . Microsoft Research .

[:proth-1] ボルソス、ベルタラン;コヴァチ、アッティラ; Tihanyi、Norbert (2022)、「Proth primes の逆数和のタイトな上限と下限」、Ramanujan Journal、59、Springer: 181–198、doi : 10.1007/s11139-021-00536-2、hdl : 10831/83020、S2CID 246024152

[:0-2] Sze, Tsz-Wo (2008). 「Proth数における決定論的素数証明」. arXiv : 0812.2596 [math.NT].

[:1-3] Weisstein, Eric W. 「Proth Prime」. mathworld.wolfram.com . 2019年12月6日閲覧。

[4] Weisstein, Eric W. 「Proth数」. mathworld.wolfram.com . 2019年12月7日閲覧。

[5] Weisstein, Eric W.「Prothの定理」. MathWorld .

[6] Konyagin, Sergei; Pomerance, Carl (2013), Graham, Ronald L.; Nešetřil, Jaroslav; Butler, Steve (eds.)「On Primes Recognizable in Deterministic Polynomial Time」The Mathematics of Paul Erdős I , Springer New York, pp. 159– 186, doi :10.1007/978-1-4614-7258-2_12, ISBN 978-1-4614-7258-2

[7] コールドウェル、クリス. 「トップ20：プロス」. ザ・プライム・ページズ.

[8] Van Zimmerman (2016年11月30日) [2016年11月9日]. 「コルベール数の世界記録が発見されました！」PrimeGrid .

[9] コールドウェル、クリス. 「トップ20：最も大きな既知の素数」. The Prime Pages .

[10] “The Prime Glossary: Fermat divisor”. primes.utm.edu . 2021年11月14日閲覧。

[top20-11] Caldwell, Chris K. 「The top twenty: Proth」. The Top Twenty . 2019年12月6日閲覧。

[:2-12] Goetz, Michael (2018年2月27日). 「Seventeen or Bust」. PrimeGrid . 2019年12月6日閲覧。

[13] ^ 「PrimeGridの拡張 シェルピンスキー問題素数探索」（PDF）primegrid.comPrimeGrid . 2021年12月28日閲覧。

[gfermat-14] 「新しいGFN因子」www.prothsearch.com . 2021年11月14日閲覧。

[15] 「素数168451×219375200+1の公式発見」（PDF）PrimeGrid . 2019年12月6日閲覧。

[fermat-16] 「フェルマー因数分解の現状」www.prothsearch.com . 2021年11月14日閲覧。

[17] 「素数99739×214019102+1の公式発見」（PDF）PrimeGrid . 2019年12月24日. 2021年11月14日閲覧。

[18] Helfgott, HA; Platt, David J. (2013). 「8.875e30までの三元ゴールドバッハ予想の数値的検証」arXiv : 1305.3062 [math.NT].

[:02-19] Helfgott, Harald A. (2013). 「三元ゴールドバッハ予想は正しい」. arXiv : 1312.7748 [math.NT].

[humboldt-professur.de-20] “ハラルド・アンドレス・ヘルフゴット”.アレクサンダー・フォン・フンボルト教授。2019年12月8日に取得。

[21] Brown, Daniel RL (2015年2月24日). 「CM55: デン・ブールの縮約をほぼ最適化する特殊素体楕円曲線、Diffie-Hellmanと離散対数の間」(PDF) .国際暗号研究協会: 1–3 .

[22] Acar, Tolga; Shumow, Dan (2010). 「特殊モジュライの事前計算なしのモジュラー縮約」(PDF) . Microsoft Research .