カニンガム鎖

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

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

定義

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

これより



 とおけば（数  は鎖の要素ではなく、素数である必要もない） と書ける。

同様に、長さ n の第2種カニンガム鎖（Cunningham chain of the second kind of length n）とは、素数列 (p1, ..., pn) であって、任意の 1 ≤ i < n に対して pi+1 = 2pi − 1 を満たすもののことである。

一般項は



であり、 とおけば  と書ける。

カニンガム鎖の定義は、互いに素な整数 a, b を固定したとき、素数列 (p1, ..., pn) であって任意の 1 ≤ i < n に対して pi+1 = api + 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 = 112 は非素数）

カニンガム鎖は「ElGamal暗号システムに対する適切な設定を並列的に生成し ... （それらは）離散対数問題が困難であるようなどんな分野においても実装し得る」Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290ため、今日では暗号システムの分野で有用視されている。

 既知の巨大カニンガム鎖 

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

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

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

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

 カニンガム鎖の合同性 

奇素数  を、ある第1種カニンガム鎖の初項とする。奇数なので  である。後続の各素数は  より  となる。よって , , と続く。

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

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

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

第1種カニンガム鎖では  なので  である。ここでフェルマーの小定理より  だから、 は  を割り切る（  とおく）。これより、無限の長さのカニンガム鎖は存在しない。

 関連項目 
 　 （カニンガム鎖をプルーフ・オブ・ワークシステムに用いている）
 Bi-twin chain


脚注

 外部リンク 
 The Prime Glossary: Cunningham chain
 Primecoin discoveries (primes.zone): online database of primecoin findings with list of records and visualization
 PrimeLinks++: Cunningham chain

Category:数論
Category:素数
Category:素数の類
Category:数学のエポニム
Category:数学に関する記事