カニンガム鎖

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

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

## 定義

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

これより

: 
\begin{align}
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{align}


 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*1,&nbsp;...,&nbsp;*p**n*) であって、任意の 1&nbsp;≤&nbsp;*i*&nbsp;*i*+1&nbsp;=&nbsp;2*p**i*&nbsp;−&nbsp;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*,&nbsp;*b* を固定したとき、素数列 (*p*1,&nbsp;...,&nbsp;*p**n*) であって任意の 1&nbsp;≤&nbsp;*i*&nbsp;*i*+1 =&nbsp;*ap**i*&nbsp;+&nbsp;*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暗号システムに対する適切な設定を並列的に生成し ... （それらは）離散対数問題が困難であるようなどんな分野においても実装し得る」ため、今日では暗号システムの分野で有用視されている。

## 既知の巨大カニンガム鎖

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

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

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

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

## カニンガム鎖の合同性

奇素数 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のカニンガム鎖の場合は次のようになる:

同様のことが第2種カニンガム鎖についても成り立つ。p_1 \equiv 1 \pmod{2} と p_{i+1} = 2 p_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  とおく）。これより、無限の長さのカニンガム鎖は存在しない。

## 関連項目
* 　 （カニンガム鎖をプルーフ・オブ・ワークシステムに用いている）
* 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