カニンガム鎖

数学におけるカニンガム鎖（カニンガムさ、英: Cunningham chain）とは、ある種の漸化式を満たす素数列のことである。名称は数学者アラン・カニンガムにちなむ。chains of nearly doubled primes とも呼ばれる。

応用の一つに、計算機の力を使ってカニンガム鎖の特定を行い、それによって仮想通貨を生成するというものがある。これはビットコインのマイニングと類似している^[1]。

定義

長さ n の第1種カニンガム鎖（Cunningham chain of the first kind of length n）とは、素数列 (p₁, ..., p_n) であって、任意の 1 ≤ i < n に対して p_i+1 = 2p_i + 1 を満たすもののことである（従ってこのような数列は末項を除いて全てソフィー・ジェルマン素数であり、初項を除いて全て安全素数である）。

これより

{\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種カニンガム鎖（Cunningham chain of the second kind of length n）とは、素数列 (p₁, ..., p_n) であって、任意の 1 ≤ i < n に対して p_i+1 = 2p_i − 1 を満たすもののことである。

一般項は

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 を固定したとき、素数列 (p₁, ..., p_n) であって任意の 1 ≤ i < n に対して p_i+1 = ap_i + b を満たすもの、と一般化されることもある。このような素数列は一般化カニンガム鎖（generalized Cunningham chain）と呼ばれる。

カニンガム鎖がそれ以上延長できない（鎖の先にも後にも、漸化式を満たすような素数が並ばない）とき完全（complete）であると言う。

例

第1種完全カニンガム鎖の例を挙げる。

2, 5, 11, 23, 47 （この次に来るはずの 95 は素数でない）

3, 7 （同様に次の 15 は非素数）

29, 59 （次の 119 = 7×17 は非素数）

41, 83, 167 （次の 335 は非素数）

89, 179, 359, 719, 1439, 2879 （次の 5759 = 13×443 は非素数）

第2種完全カニンガム鎖の例を挙げる。

2, 3, 5 （この次に来るはずの 9 は素数でない）

7, 13 （同様に次の 25 は非素数）

19, 37, 73 （同様に次の 145 は非素数）

31, 61 （同様に次の 121 = 11² は非素数）

カニンガム鎖は「ElGamal暗号システムに対する適切な設定を並列的に生成し ... （それらは）離散対数問題が困難であるようなどんな分野においても実装し得る」^[2]ため、今日では暗号システムの分野で有用視されている。

既知の巨大カニンガム鎖

広く真であると信じられている、ディクソン予想（英語版）・およびより包括的なシンゼルの仮説H（英語版）（Schinzel's hypothesis H）によれば、任意の k に対し無限に多くの長さ k のカニンガム鎖が存在することになる。しかしながら、そのような列を生成する直接的な方法はわかっていない。

最長の、もしくは最大の素数から始まるようなカニンガム鎖を求める計算機コンテストが存在するが、ベン・グリーンとテレンス・タオによるブレイクスルー - グリーン・タオの定理：素数全体の集合は任意の長さの等差数列を含んでいる - とは異なり、巨大なカニンガム鎖についての一般的な結果は現在に至るまで何も得られていない。

長さ k の既知の巨大カニンガム鎖のリスト（2018年6月5日現在^[3]）
k	種別	p₁ (初項)	桁数	発見年	発見者
1	1st / 2nd	2^77232917 − 1	23249425	2017	Curtis Cooper, GIMPS
2	1st	2618163402417×2^1290000 − 1	388342	2016	PrimeGrid
2	2nd	7775705415×2¹⁷⁵¹¹⁵ + 1	52725	2017	Serge Batalov
3	1st	1815615642825×2⁴⁴⁰⁴⁴ − 1	13271	2016	Serge Batalov
3	2nd	742478255901×2⁴⁰⁰⁶⁷ + 1	12074	2016	Michael Angel & Dirk Augustin
4	1st	13720852541*7877# − 1	3384	2016	Michael Angel & Dirk Augustin
4	2nd	17285145467*6977# + 1	3005	2016	Michael Angel & Dirk Augustin
5	1st	31017701152691334912*4091# − 1	1765	2016	Andrey Balyakin
5	2nd	181439827616655015936*4673# + 1	2018	2016	Andrey Balyakin
6	1st	2799873605326×2371# - 1	1016	2015	Serge Batalov
6	2nd	52992297065385779421184*1531# + 1	668	2015	Andrey Balyakin
7	1st	82466536397303904*1171# − 1	509	2016	Andrey Balyakin
7	2nd	25802590081726373888*1033# + 1	453	2015	Andrey Balyakin
8	1st	89628063633698570895360*593# − 1	265	2015	Andrey Balyakin
8	2nd	2373007846680317952*761# + 1	337	2016	Andrey Balyakin
9	1st	553374939996823808*593# − 1	260	2016	Andrey Balyakin
9	2nd	173129832252242394185728*401# + 1	187	2015	Andrey Balyakin
10	1st	3696772637099483023015936*311# − 1	150	2016	Andrey Balyakin
10	2nd	2044300700000658875613184*311# + 1	150	2016	Andrey Balyakin
11	1st	73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1	140	2013	Primecoin (block 95569)
11	2nd	341841671431409652891648*311# + 1	149	2016	Andrey Balyakin
12	1st	288320466650346626888267818984974462085357412586437032687304004479168536445314040×83# − 1	113	2014	Primecoin (block 558800)
12	2nd	906644189971753846618980352*233# + 1	121	2015	Andrey Balyakin
13	1st	106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1	107	2014	Primecoin (block 368051)
13	2nd	38249410745534076442242419351233801191635692835712219264661912943040353398995076864×47# + 1	101	2014	Primecoin (block 539977)
14	1st	4631673892190914134588763508558377441004250662630975370524984655678678526944768*47# - 1	97	2018	Primecoin (block 2659167)
14	2nd	5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 1	100	2014	Primecoin (block 547276)
15	1st	14354792166345299956567113728*43# - 1	45	2016	Andrey Balyakin
15	2nd	67040002730422542592*53# + 1	40	2016	Andrey Balyakin
16	1st	91304653283578934559359	23	2008	Jaroslaw Wroblewski
16	2nd	2×1540797425367761006138858881 − 1	28	2014	Chermoni & Wroblewski
17	1st	2759832934171386593519	22	2008	Jaroslaw Wroblewski
17	2nd	1540797425367761006138858881	28	2014	Chermoni & Wroblewski
18	2nd	658189097608811942204322721	27	2014	Chermoni & Wroblewski
19	2nd	79910197721667870187016101	26	2014	Chermoni & Wroblewski

q# は素数階乗 2×3×5×7×...×q を表す。

2018年現在^[update]、（両種について）最長のカニンガム鎖は長さ19で、Jaroslaw Wroblewski によって2014年に発見された^[3]。

カニンガム鎖の合同性

奇素数 $p_{1}$ を、ある第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}}$ , と続く。

この性質は二進法で表記すると簡単に見てとれる（位取り記数法の底が何であっても、底をかけると数字列が左に1桁シフトする）。 $p_{i+1}=2p_{i}+1$ を底2で考えると、2を掛けることで $p_{i}$ の最下位桁は $p_{i+1}$ の最下位から2番目の桁に移り、また $p_{i+1}$ は奇数なので最下位桁はやはり1である。このように二進法では本質的に、カニンガム鎖の各項は1桁の左シフトと最下位桁への"1"の挿入で得られる。例えば141361469から始まる長さ6のカニンガム鎖の場合は次のようになる:

二進法	十進法
1000011011010000000100111101	141361469
10000110110100000001001111011	282722939
100001101101000000010011110111	565445879
1000011011010000000100111101111	1130891759
10000110110100000001001111011111	2261783519
100001101101000000010011110111111	4523567039

同様のことが第2種カニンガム鎖についても成り立つ。 $p_{1}\equiv 1{\pmod {2}}$ と $p_{i+1}=2p_{i}-1$ から、 $p_{i}\equiv 1{\pmod {2^{i}}}$ がわかる。二進法では、第2種カニンガム鎖の各項の末尾は "0...01" となる。ここで各 $i$ に対し、 $p_{i+1}$ の末尾で0が連続する個数は $p_{i}$ のものより1だけ多い。第1種カニンガム鎖と同じく、この末尾の左側の部分は項が進むにつれて1桁ずつ左にシフトしていく。

第1種カニンガム鎖では $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}$ とおく）。これより、無限の長さのカニンガム鎖は存在しない^[4]。