カニンガム鎖

数学におけるカニンガム鎖（カニンガムさ、英: 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 を満たすもののことである（従ってこのような数列は末項を除いて全てソフィー・ジェルマン素数であり、初項を除いて全て安全素数である）。

これより

${\displaystyle {\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}}}$

${\displaystyle a={\frac {p_{1}+1}{2}}}$ とおけば（数 ${\displaystyle a}$ は鎖の要素ではなく、素数である必要もない）${\displaystyle 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 を満たすもののことである。

一般項は

${\displaystyle p_{i}=2^{i-1}p_{1}-(2^{i-1}-1)}$

であり、${\displaystyle a={\frac {p_{1}-1}{2}}}$ とおけば ${\displaystyle 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 のカニンガム鎖が存在することになる。しかしながら、そのような列を生成する直接的な方法はわかっていない。

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

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

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

カニンガム鎖の合同性

奇素数 ${\displaystyle p_{1}}$ を、ある第1種カニンガム鎖の初項とする。奇数なので ${\displaystyle p_{1}\equiv 1{\pmod {2}}}$ である。後続の各素数は ${\displaystyle p_{i+1}=2p_{i}+1}$ より ${\displaystyle p_{i}\equiv 2^{i}-1{\pmod {2^{i}}}}$ となる。よって ${\displaystyle p_{2}\equiv 3{\pmod {4}}}$, ${\displaystyle p_{3}\equiv 7{\pmod {8}}}$, と続く。

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

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

第1種カニンガム鎖では ${\displaystyle p_{i}=2^{i-1}p_{1}+(2^{i-1}-1)\,}$ なので ${\displaystyle p_{i}\equiv 2^{i-1}-1{\pmod {p_{1}}}}$ である。ここでフェルマーの小定理より ${\displaystyle 2^{p_{1}-1}\equiv 1{\pmod {p_{1}}}}$ だから、${\displaystyle p_{1}}$ は ${\displaystyle p_{p_{1}}}$ を割り切る（ ${\displaystyle i=p_{1}}$ とおく）。これより、無限の長さのカニンガム鎖は存在しない^[4]。

関連項目

• プライムコイン（英語版）　 （カニンガム鎖をプルーフ・オブ・ワークシステムに用いている）
• Bi-twin chain
• 等差数列における素数（英語版）

脚注

1. ^ “Cunningham Chains Mining”. lirmm.fr. 2018年11月7日閲覧。
2. ^ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
3. ^ ^{a b} Dirk Augustin, Cunningham Chain records. Retrieved on 2018-06-08.
4. ^ Löh, Günter (October 1989). “Long chains of nearly doubled primes”. Mathematics of Computation 53 (188): 751–759. doi:10.1090/S0025-5718-1989-0979939-8. http://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0979939-8/. 

外部リンク

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