カニンガムチェーン

数学 において、カニンガム連鎖とは、ある特定の素数列のことである。カニンガム連鎖は、数学者A.J.C.カニンガムにちなんで名付けられた。また、ほぼ2倍の素数の連鎖とも呼ばれる。

長さnの第一種カニンガム連鎖とは、すべての 1 ≤ i < nに対してp _{i +1} = 2 p _i + 1となる素数列 ( p ₁ , ..., p _n ) のことである。(したがって、このような連鎖の最後の項を除く各項はソフィー・ジェルマン素数であり、最初の項を除く各項は安全素数である)。        

したがって、

${\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 種のカニンガム鎖は、すべての 1 ≤ i < nに対してp _{i +1} = 2 p _i − 1となる素数 ( p ₁ , ..., p _n )の列です。        

したがって、一般項は

${\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に対して、すべての 1 ≤ i ≤ nに対してp _{i +1} = ap _i + bとなるような素数列 ( p ₁ , ..., p _n ) に一般化されることもあります。結果として得られる鎖は、一般化カニンガム鎖と呼ばれます。       

カニンガム連鎖は、それ以上拡張できない場合、つまり連鎖の前後の項が素数でない場合、完全であると呼ばれます。

第一種カニンガム連鎖の完全な例としては、以下のようなものがある。

2、5、11、23、47 （次の数は95ですが、これは素数ではありません。）

3、7（次の数字は15だが、15は素数ではない。）

29、59（次の数字は119ですが、これは素数ではありません。）

41、83、167（次の数字は335ですが、これは素数ではありません。）

89、179、359、719、1439、2879（次の数は5759ですが、これは素数ではありません。）

第2種カニンガム連鎖の完全な例としては、以下のようなものがある。

2、3、5（次の数字は9だが、9は素数ではない。）

7、13（次の数字は25ですが、これは素数ではありません。）

19、37、73（次の数字は145ですが、これは素数ではありません。）

31、61（次の数は121 = 11 ²ですが、これは素数ではありません。）

カニンガムチェーンは、「エルガマル暗号システムに適した2つの同時設定を提供する」ため、暗号システムにおいて有用であると考えられている。「離散対数問題が難しいあらゆる分野で実装できる」 ^{[ 1 ]。}

ディクソンの予想と、より広範なシンツェルの仮説H（いずれも広く正しいとされている）から、任意のkに対して、長さkのカニンガム鎖が無限に存在することが導かれる。しかしながら、そのような鎖を直接生成する方法は知られていない。

最長のカニンガム鎖や、最大の素数で構成されたカニンガム鎖を競うコンピューター競技は存在するが、ベン・J・グリーンとテレンス・タオによる画期的な発見、すなわち任意の長さの素数の算術級数が存在するというグリーン・タオの定理とは異なり、現在までに大きなカニンガム鎖に関する一般的な結果は知られていない。

q # は、原始2 × 3 × 5 × 7 × ... × qを表します。

2018年現在いずれのタイプのカニンガム連鎖でも、最も長いものは長さ19で、2014年にヤロスワフ・ヴロブレフスキによって発見された。^{[ 2 ]}

奇数の素数${\displaystyle p_{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}}}$などなど。

上記の性質は、 2進数の素数列を考えることで非公式に観察できます。（すべての基数と同様に、基数を掛けると桁が左に「シフト」されることに注意してください。たとえば、10進数では 314 × 10 = 3140 となります。） ${\displaystyle p_{i+1}=2p_{i}+1}$2進数では、乗算すると ${\displaystyle p_{i}}$2 によって、最下位桁は ${\displaystyle p_{i}}$の2番目に下位の桁になります ${\displaystyle p_{i+1}}$。 なぜなら${\displaystyle p_{i}}$は奇数です。つまり、2 進数では最下位桁は 1 です。2 番目に最下位桁は 1 であることがわかっています。 ${\displaystyle p_{i+1}}$も 1 です。そして最後に、次のことがわかります。 ${\displaystyle p_{i+1}}$1 を加えることで奇数になります$2p_i$このように、カニンガム連鎖における連続する素数は、実質的にバイナリで左にシフトされ、最下位桁には1が入ります。例えば、141361469から始まる長さ6の完全な連鎖を以下に示します。

第二種のカニンガム連鎖についても同様の結果が得られる。${\displaystyle p_{1}\equiv 1{\pmod {2}}}$そしてその関係${\displaystyle p_{i+1}=2p_{i}-1}$したがって、${\displaystyle p_{i}\equiv 1{\pmod {2^{i}}}}$2進表記では、第2種カニンガム連鎖の素数は「0...01」というパターンで終わります。ここで、各${\displaystyle i}$、パターン内のゼロの数${\displaystyle p_{i+1}}$は、ゼロの数より 1 つ多い。${\displaystyle p_{i}}$第一種カニンガム連鎖と同様に、パターンの左側のビットは、素数が連続するごとに1つずつ左にシフトします。

同様に、${\displaystyle p_{i}=2^{i-1}p_{1}+(2^{i-1}-1)\,}$したがって、${\displaystyle p_{i}\equiv 2^{i-1}-1{\pmod {p_{1}}}}$しかし、フェルマーの小定理によれば、$2^{p_{1}-1}\equiv 1{\pmod {p_{1}}}}$、 それで${\displaystyle p_{1}}$分ける${\displaystyle p_{p_{1}}}$（つまり、${\displaystyle i=p_{1}}$したがって、カニンガム鎖は無限長にはなり得ない。^{[ 3 ]}

• プルーフ・オブ・ワーク・システムとしてカニンガム・チェーンを使用するプライムコイン
• バイツインチェーン
• 等差数列における素数

• プライム用語集：カニンガムチェーン
• Primecoinの発見（primes.zone）：Primecoinの発見に関するオンラインデータベース。記録リストと視覚化機能付き。
• PrimeLinks++: カニンガムチェーン
• OEIS数列A005602 （長さnの完全なカニンガム連鎖（第一種）の最小の素数） -- 1 ≤ n ≤ 14の場合の長さnの第一種の最小の完全なカニンガム連鎖の最初の項       
• OEIS数列A005603 （ほぼ2倍になった素数の長さnの連鎖） -- 1 ≤ n ≤ 15の場合の長さnの最小完全カニンガム連鎖の第1項