数学におけるカニンガム鎖（カニンガムさ、）とは、ある種の漸化式を満たす素数列のことである。名称は数学者アラン・カニンガムにちなむ。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