数学において、カニンガム連鎖とは、素数の特定の列を指します。カニンガム連鎖は数学者 A. J. C. カニンガムにちなんで名付けられました。また、ほぼ2倍の素数の連鎖とも呼ばれます。

意味

長さnの第一種カニンガム連鎖とは、すべての 1 ≤ i < nに対してp _i₊₁ = 2 p _i + 1 となるような素数列 ( p ₁ , ..., p _n ) である。(したがって、このような連鎖の最後の項を除く各項はソフィー・ジェルマン素数であり、最初の項を除く各項は安全素数である。)

すると、

{\begin{aligned}p_{2}&=2p_{1}+1,\\p_{3}&=4p_{1}+3,\\p_{4}&=8p_{1}+7,\\&{}\ \vdots \\p_{i}&=2^{i-1}p_{1}+(2^{i-1}-1),\end{aligned}}

または、（その数は数列の一部ではなく、素数である必要はない）と設定することで、 $a={\frac {p_{1}+1}{2}}$ $a$ $p_{i}=2^{i}a-1.$

同様に、長さnの第 2 種のカニンガム連鎖は、すべての 1 ≤ i < nに対してp _i₊₁ = 2 p _i − 1 となるような素数 ( p ₁、...、p _n )のシーケンスです。

したがって、一般的な用語は

p_{i}=2^{i-1}p_{1}-(2^{i-1}-1).

ここで、を設定すると、が得られます。 $a={\frac {p_{1}-1}{2}}$ $p_{i}=2^{i}a+1$

カニンガム連鎖は、固定された互いに素な整数aとbに対して、すべての 1 ≤ i ≤ nに対してp _i₊₁ = ap _i + bとなるような素数列 ( p ₁、...、p _n ) に一般化されることもあります。結果として得られる連鎖は、一般化カニンガム連鎖と呼ばれます。

カニンガム連鎖は、それ以上拡張できない場合、つまり連鎖内の前の項と次の項が素数でない場合、完全であると呼ばれます。

例

第一種の完全なカニンガム連鎖の例には次のものがあります。

2、5、11、23、47 (次の数字は 95 ですが、これは素数ではありません。)

3、7 (次の数字は 15 ですが、これは素数ではありません。)

29、59（次の数字は119ですが、これは素数ではありません。）

41、83、167（次の数字は 335 ですが、これは素数ではありません。）

89、179、359、719、1439、2879（次の数字は5759ですが、これは素数ではありません。）

第二種の完全なカニンガム連鎖の例には次のものがあります。

2、3、5 (次の数字は 9 ですが、これは素数ではありません。)

7、13 (次の数字は 25 ですが、これは素数ではありません。)

19、37、73 (次の数字は 145 ですが、これは素数ではありません。)

31、61（次の数字は 121 = 11 ²ですが、これは素数ではありません。）

カニンガム連鎖は、エルガマル暗号システムに2つの適切な同時設定を提供するため、暗号システムで有用であると考えられています。^{[ 1 ]}

最大のカニンガムチェーン

ディクソンの予想と、より広義のシンツェルの仮説 Hはどちらも広く正しいと考えられており、任意のkに対して長さkのカニンガム鎖が無限に存在することが導かれる。しかしながら、そのような鎖を直接生成する方法は知られていない。

最長のカニンガム連鎖や、最大の素数で構成される連鎖を求める計算コンテストは行われているが、ベン・J・グリーンとテレンス・タオによる画期的な発見（任意の長さの素数の等差数列が存在するというグリーン・タオ定理）とは異なり、大規模なカニンガム連鎖に関する一般的な結果は今のところ知られていない。

*長さk*の最大のカニンガム連鎖（2025年2月18日現在^{[ 2 ]}）
け	親切	p ₁ (開始素数)	数字	年	発見者
1	1位 / 2位	2 ^136279841 − 1	41024320	2024	ルーク・デュラント、GIMPS
2	1位	2618163402417×2 ^1290000 − 1	388342	2016	プライムグリッド
2	2位	213778324725×2 ⁵⁶¹⁴¹⁷ + 1	169015	2023	ライアン・プロッパー＆セルジュ・バタロフ
3	1位	1128330746865×2 ⁶⁶⁴³⁹ − 1	20013	2020	マイケル・パリドン
3	2位	214923707595×2 ⁴⁹⁰⁷³ + 1	14784	2025	セルジュ・バタロフ
4	1位	93003628384×10111# − 1	4362	2025	セルジュ・バタロフ
4	2位	49325406476×9811# + 1	4234	2019	オスカー・オストリン
5	1位	475676794046977267×4679# − 1	2019	2024	アンドレイ・バリャキン
5	2位	181439827616655015936×4673# + 1	2018	2016	アンドレイ・バリャキン
6	1位	2799873605326×2371# − 1	1016	2015	セルジュ・バタロフ
6	2位	37015322207094×2339# + 1	1001	2025	セルジュ・バタロフ
7	1位	82466536397303904×1171# − 1	509	2016	アンドレイ・バリャキン
7	2位	25802590081726373888×1033# + 1	453	2015	アンドレイ・バリャキン
8	1位	89628063633698570895360×593# − 1	265	2015	アンドレイ・バリャキン
8	2位	2373007846680317952×761# + 1	337	2016	アンドレイ・バリャキン
9	1位	553374939996823808×593# − 1	260	2016	アンドレイ・バリャキン
9	2位	173129832252242394185728×401# + 1	187	2015	アンドレイ・バリャキン
10	1位	3696772637099483023015936×311# − 1	150	2016	アンドレイ・バリャキン
10	2位	2044300700000658875613184×311# + 1	150	2016	アンドレイ・バリャキン
11	1位	73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1	140	2013	プライムコイン（ブロック95569）
11	2位	341841671431409652891648×311# + 1	149	2016	アンドレイ・バリャキン
12	1位	288320466650346626888267818984974462085357412586437032687304004479168536445314040×83# − 1	113	2014	プライムコイン（ブロック558800）
12	2位	906644189971753846618980352×233# + 1	121	2015	アンドレイ・バリャキン
13	1位	106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1	107	2014	プライムコイン（ブロック368051）
13	2位	38249410745534076442242419351233801191635692835712219264661912943040353398995076864×47# + 1	101	2014	プライムコイン（ブロック539977）
14	1位	4631673892190914134588763508558377441004250662630975370524984655678678526944768×47# − 1	97	2018	プライムコイン（ブロック2659167）
14	2位	5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 1	100	2014	プライムコイン（ブロック547276）
15	1位	14354792166345299956567113728×43# - 1	45	2016	アンドレイ・バリャキン
15	2位	67040002730422542592×53# + 1	40	2016	アンドレイ・バリャキン
16	1位	91304653283578934559359	23	2008	ヤロスワフ・ウォロブレフスキ
16	2位	2×1540797425367761006138858881 − 1	28	2014	チェルモニ＆ウォロブレフスキ
17	1位	2759832934171386593519	22	2008	ヤロスワフ・ウォロブレフスキ
17	2位	1540797425367761006138858881	28	2014	チェルモニ＆ウォロブレフスキ
18	2位	658189097608811942204322721	27	2014	チェルモニ＆ウォロブレフスキ
19	2位	79910197721667870187016101	26	2014	チェルモニ＆ウォロブレフスキ

q # は原始的な2 × 3 × 5 × 7 × ... × qを表します。

2018年現在^{[アップデート]}、どちらの種類のカニンガム鎖でも最も長いものは長さ19で、2014年にヤロスワフ・ウォロブレフスキによって発見された。^{[ 2 ]}

カニンガム連鎖の合同性

奇数素数を第一種カニンガム連鎖の最初の素数とします。最初の素数は奇数なので、となります。連鎖内の連続する素数はそれぞれなので、となります。したがって、、、などとなります。 $p_{1}$ $p_{1}\equiv 1{\pmod {2}}$ $p_{i+1}=2p_{i}+1$ $p_{i}\equiv 2^{i}-1{\pmod {2^{i}}}$ $p_{2}\equiv 3{\pmod {4}}$ $p_{3}\equiv 7{\pmod {8}}$

上記の性質は、 2進数の素数連鎖を考えることで、非公式に観察できます。（すべての基数と同様に、基数を掛けると桁が左に「シフト」することに注意してください。例えば、10進数では314 × 10 = 3140となります。） 2進数で考えると、 2を掛けることで、の最下位桁がの最下位から2番目の桁になります。は奇数であるため（つまり、2進数では最下位桁は1です）、の最下位から2番目の桁も1であることがわかります。そして最後に、に1を加えることでは奇数になります。このように、カニンガム連鎖における連続する素数は、基本的に2進数では左にシフトされ、最下位桁が1で埋められます。例えば、141361469から始まる長さ6の完全な連鎖は次のとおりです。 $p_{i+1}=2p_{i}+1$ $p_{i}$ $p_{i}$ $p_{i+1}$ $p_{i}$ $p_{i+1}$ $p_{i+1}$ $2p_{i}$

バイナリ	小数点
1000011011010000000100111101	141361469
10000110110100000001001111011	282722939
100001101101000000010011110111	565445879
1000011011010000000100111101111	1130891759
10000110110100000001001111011111	2261783519
100001101101000000010011110111111	4523567039

第二種カニンガム連鎖についても同様の結果が得られます。と関係式の観察から、が成り立ちます。2進表記法では、第二種カニンガム連鎖の素数は「0...01」というパターンで終わります。ここで、の各について、のパターンにおけるゼロの数はのゼロの数より1つ多くなります。第一種カニンガム連鎖と同様に、パターンの左側のビットは、後続の素数ごとに1つずつ左にシフトします。 $p_{1}\equiv 1{\pmod {2}}$ $p_{i+1}=2p_{i}-1$ $p_{i}\equiv 1{\pmod {2^{i}}}$ $i$ $p_{i+1}$ $p_{i}$

同様に、となるため、となる。しかし、フェルマーの小定理によれば、はを割り切る（つまりで割り切る）。したがって、カニンガム連鎖は無限長にはならない。^[³^] $p_{i}=2^{i-1}p_{1}+(2^{i-1}-1)\,$ $p_{i}\equiv 2^{i-1}-1{\pmod {p_{1}}}$ $2^{p_{1}-1}\equiv 1{\pmod {p_{1}}}$ $p_{1}$ $p_{p_{1}}$ $i=p_{1}$

参照

プライムコインは、カニンガムチェーンをプルーフオブワークシステムとして使用しています。
バイツインチェーン
等差数列における素数

参考文献

^ ジョー・ブラー『アルゴリズム数論：第三回国際シンポジウム ANTS-III』ニューヨーク：シュプリンガー（1998年）：290
^ ^a ^b Norman Luhn & Dirk Augustin, Cunningham Chain records . 2025年2月18日閲覧。
^ Löh, Günter (1989年10月). 「ほぼ2倍の素数の長い連鎖」 .計算数学. 53 (188): 751– 759. doi : 10.1090/S0025-5718-1989-0979939-8 .

外部リンク

プライム用語集：カニンガム連鎖
プライムコイン発見（primes.zone）：記録リストと視覚化を備えたプライムコイン発見のオンラインデータベース
PrimeLinks++: カニンガムチェーン
OEIS シーケンスA005602（長さnの完全カニンガム連鎖（第1種）の始まりとなる最小の素数） - 長さnの第1種の最小完全カニンガム連鎖の第1項（1 ≤ n ≤ 14）
OEIS シーケンスA005603（長さnのほぼ2倍の素数の連鎖） - 長さnの第二種最小完全カニンガム連鎖の最初の項、 1≤n≤15

[1] ジョー・ブラー『アルゴリズム数論：第三回国際シンポジウム ANTS-III』ニューヨーク：シュプリンガー（1998年）：290

[records-2] Norman Luhn & Dirk Augustin, Cunningham Chain records . 2025年2月18日閲覧。

[3] Löh, Günter (1989年10月). 「ほぼ2倍の素数の長い連鎖」 .計算数学. 53 (188): 751– 759. doi : 10.1090/S0025-5718-1989-0979939-8 .

[ 1 ]

[ 2 ]

[