カニンガム鎖

数学におけるカニンガム鎖（カニンガムさ、）とは、ある種の漸化式を満たす素数列のことである。名称は数学者アラン・カニンガムにちなむ。chains of nearly doubled primes とも呼ばれる。 
応用の一つに、計算機の力を使ってカニンガム鎖の特定を行い、それによって仮想通貨を生成するというものがある。これはビットコインのマイニングと類似している。
定義.
長さ "n" の第1種カニンガム鎖（Cunningham chain of the first kind of length n）とは、素数列 ("p"1, ..., "p""n") であって、任意の 1 ≤ "i" &lt; "n" に対して "p""i"+1 = 2"p""i" + 1 を満たすもののことである（従ってこのような数列は末項を除いて全てソフィー・ジェルマン素数であり、初項を除いて全て安全素数である）。
これより
formula_2 とおけば（数 formula_3 は鎖の要素ではなく、素数である必要もない）formula_4 と書ける。
同様に、長さ "n" の第2種カニンガム鎖（Cunningham chain of the second kind of length n）とは、素数列 ("p"1, ..., "p""n") であって、任意の 1 ≤ "i" &lt; "n" に対して "p""i"+1 = 2"p""i" − 1 を満たすもののことである。
一般項は
であり、formula_6 とおけば formula_7 と書ける。
カニンガム鎖の定義は、互いに素な整数 "a", "b" を固定したとき、素数列 ("p"1, ..., "p""n") であって任意の 1 ≤ "i" &lt; "n" に対して "p""i"+1 = "ap""i" + "b" を満たすもの、と一般化されることもある。このような素数列は一般化カニンガム鎖（generalized Cunningham chain）と呼ばれる。
カニンガム鎖がそれ以上延長できない（鎖の先にも後にも、漸化式を満たすような素数が並ばない）とき完全（complete）であると言う。
例.
第1種完全カニンガム鎖の例を挙げる。
第2種完全カニンガム鎖の例を挙げる。
カニンガム鎖は「ElGamal暗号システムに対する適切な設定を並列的に生成し ... （それらは）離散対数問題が困難であるようなどんな分野においても実装し得る」ため、今日では暗号システムの分野で有用視されている。
既知の巨大カニンガム鎖.
広く真であると信じられている、・およびより包括的な（Schinzel's hypothesis H）によれば、任意の "k" に対し無限に多くの長さ "k" のカニンガム鎖が存在することになる。しかしながら、そのような列を生成する直接的な方法はわかっていない。
最長の、もしくは最大の素数から始まるようなカニンガム鎖を求める計算機コンテストが存在するが、ベン・グリーンとテレンス・タオによるブレイクスルー - グリーン・タオの定理：素数全体の集合は任意の長さの等差数列を含んでいる - とは異なり、巨大なカニンガム鎖についての一般的な結果は現在に至るまで何も得られていない。
"q"# は素数階乗 2×3×5×7×...×"q" を表す。
、（両種について）最長のカニンガム鎖は長さ19で、Jaroslaw Wroblewski によって2014年に発見された。
カニンガム鎖の合同性.
奇素数 formula_8 を、ある第1種カニンガム鎖の初項とする。奇数なので formula_9 である。後続の各素数は formula_10 より formula_11 となる。よって formula_12, formula_13, と続く。
この性質は二進法で表記すると簡単に見てとれる（位取り記数法の底が何であっても、底をかけると数字列が左に1桁シフトする）。formula_10 を底2で考えると、2を掛けることで formula_15 の最下位桁は formula_16 の最下位から2番目の桁に移り、また formula_16 は奇数なので最下位桁はやはり1である。このように二進法では本質的に、カニンガム鎖の各項は1桁の左シフトと最下位桁への"1"の挿入で得られる。例えば141361469から始まる長さ6のカニンガム鎖の場合は次のようになる:
同様のことが第2種カニンガム鎖についても成り立つ。formula_9 と formula_19 から、formula_20 がわかる。二進法では、第2種カニンガム鎖の各項の末尾は "0...01" となる。ここで各 formula_21 に対し、formula_16 の末尾で0が連続する個数は formula_15 のものより1だけ多い。第1種カニンガム鎖と同じく、この末尾の左側の部分は項が進むにつれて1桁ずつ左にシフトしていく。
第1種カニンガム鎖では formula_24 なので formula_25 である。ここでフェルマーの小定理より formula_26 だから、formula_8 は formula_28 を割り切る（ formula_29 とおく）。これより、無限の長さのカニンガム鎖は存在しない。