カニンガム鎖のソースを表示

[[数学]]における'''カニンガム鎖'''（カニンガムさ、{{Lang-en-short|Cunningham chain}}）とは、ある種の[[漸化式]]を満たす[[素数]]列のことである。名称は[[数学者]][[アラン・カニンガム (数学者)|アラン・カニンガム]]にちなむ。'''chains of nearly doubled primes''' とも呼ばれる。 

応用の一つに、計算機の力を使ってカニンガム鎖の特定を行い、それによって[[仮想通貨]]を生成するというものがある。これは[[ビットコイン]]のマイニングと類似している<ref>{{cite web|url= http://www.lirmm.fr/~imbert/sujets/cunningham-chains.pdf |title=Cunningham Chains Mining |website=lirmm.fr |date= |accessdate=2018-11-07}}</ref>。

==定義==

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

これより

: <math>
\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}
</math>

<math> a = \frac{p_1 + 1}{2} </math> とおけば（数 <math> a </math> は鎖の要素ではなく、素数である必要もない）<math> p_i = 2^{i} a - 1 </math> と書ける。

同様に、'''長さ ''n'' の第2種カニンガム鎖'''（Cunningham chain of the second kind of length n）とは、素数列 (''p''<sub>1</sub>,&nbsp;...,&nbsp;''p''<sub>''n''</sub>) であって、任意の 1&nbsp;≤&nbsp;''i''&nbsp;<&nbsp;''n'' に対して ''p''<sub>''i''+1</sub>&nbsp;=&nbsp;2''p''<sub>''i''</sub>&nbsp;−&nbsp;1 を満たすもののことである。

一般項は

: <math> p_i = 2^{i-1}p_1 - (2^{i-1}-1) </math>

であり、<math> a = \frac{p_1 - 1}{2} </math> とおけば <math> p_i = 2^{i} a + 1 </math> と書ける。

カニンガム鎖の定義は、[[互いに素 (整数論)|互いに素]]な整数 ''a'',&nbsp;''b'' を固定したとき、素数列 (''p''<sub>1</sub>,&nbsp;...,&nbsp;''p''<sub>''n''</sub>) であって任意の 1&nbsp;≤&nbsp;''i''&nbsp;<&nbsp;''n'' に対して ''p''<sub>''i''+1</sub> =&nbsp;''ap''<sub>''i''</sub>&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 = 11<sup>2</sup> は非素数）

カニンガム鎖は「[[ElGamal暗号]]システムに対する適切な設定を並列的に生成し ... （それらは）[[離散対数]]問題が困難であるようなどんな分野においても実装し得る」<ref>Joe Buhler, ''Algorithmic Number Theory: Third International Symposium, ANTS-III''. New York: Springer (1998): 290</ref>ため、今日では[[暗号]]システムの分野で有用視されている。

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

広く真であると信じられている、{{仮リンク|ディクソン予想|en|Dickson's conjecture}}・およびより包括的な{{仮リンク|シンゼルの仮説H|en|Schinzel's hypothesis H}}（Schinzel's hypothesis H）によれば、任意の ''k'' に対し無限に多くの長さ ''k'' のカニンガム鎖が存在することになる。しかしながら、そのような列を生成する直接的な方法はわかっていない。

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

{| class="wikitable"
|+ 長さ ''k'' の既知の巨大カニンガム鎖のリスト（2018年6月5日現在<ref name="records">Dirk Augustin, [http://primerecords.dk/Cunningham_Chain_records.htm ''Cunningham Chain records'']. Retrieved on 2018-06-08.</ref>）
|-
! ''k'' !! 種別 !! ''p''<sub>1</sub> (初項) !! 桁数 !! 発見年 !! 発見者
|-
| 1 || 1st / 2nd || 2<sup>77232917</sup> − 1 || align="right" | 23249425 || 2017 || [[Curtis Cooper (mathematician)|Curtis Cooper]], [[Great Internet Mersenne Prime Search|GIMPS]]
|-
| rowspan="2" | 2 || 1st || 2618163402417×2<sup>1290000</sup> − 1 || align="right" | 388342 || 2016 || [[PrimeGrid]]
|-
| 2nd || 7775705415×2<sup>175115</sup> + 1 || align="right" | 52725 || 2017 || Serge Batalov
|-
| rowspan="2" | 3 || 1st || 1815615642825×2<sup>44044</sup> − 1 || align="right" | 13271 || 2016 || Serge Batalov
|-
| 2nd || 742478255901×2<sup>40067</sup> + 1 || align="right" | 12074 || 2016 || Michael Angel & Dirk Augustin
|-
| rowspan="2" | 4 || 1st || 13720852541*7877# − 1 || align="right" | 3384 || 2016 || Michael Angel & Dirk Augustin
|-
| 2nd || 17285145467*6977# + 1 || align="right" | 3005 || 2016 || Michael Angel & Dirk Augustin
|-
| rowspan="2" | 5 || 1st || 31017701152691334912*4091# − 1 || align="right" | 1765 || 2016 || Andrey Balyakin
|-
| 2nd || 181439827616655015936*4673# + 1 || align="right" | 2018 || 2016 || Andrey Balyakin
|-
| rowspan="2" | 6 || 1st || 2799873605326×2371# - 1 || align="right" | 1016 || 2015 || Serge Batalov
|-
| 2nd || 52992297065385779421184*1531# + 1 || align="right" | 668 || 2015 || Andrey Balyakin
|-
| rowspan="2" | 7 || 1st || 82466536397303904*1171# − 1 || align="right" | 509 || 2016 || Andrey Balyakin
|-
| 2nd || 25802590081726373888*1033# + 1 || align="right" | 453 || 2015 || Andrey Balyakin
|-
| rowspan="2" | 8 || 1st || 89628063633698570895360*593# − 1 || align="right" | 265 || 2015 || Andrey Balyakin
|-
| 2nd || 2373007846680317952*761# + 1 || align="right" | 337 || 2016 || Andrey Balyakin
|-
| rowspan="2" | 9 || 1st || 553374939996823808*593# − 1 || align="right" | 260 || 2016 || Andrey Balyakin
|-
| 2nd || 173129832252242394185728*401# + 1 || align="right" | 187 || 2015 || Andrey Balyakin
|-
| rowspan="2" | 10 || 1st || 3696772637099483023015936*311# − 1 || align="right" | 150 || 2016 || Andrey Balyakin
|-
| 2nd || 2044300700000658875613184*311# + 1 || align="right" | 150 || 2016 || Andrey Balyakin
|-
| rowspan="2" | 11 || 1st || 73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1 || align="right" | 140 || 2013 || Primecoin ([https://primes.zone/#records block 95569])
|-
| 2nd || 341841671431409652891648*311# + 1 || align="right" | 149 || 2016 || Andrey Balyakin
|-
| rowspan="2" | 12 || 1st || 288320466650346626888267818984974462085357412586437032687304004479168536445314040×83# − 1 || align="right" | 113 || 2014 || Primecoin ([https://primes.zone/#records block 558800])
|-
| 2nd || 906644189971753846618980352*233# + 1 || align="right" | 121 || 2015 || Andrey Balyakin
|-
| rowspan="2" | 13 || 1st || 106680560818292299253267832484567360951928953599522278361651385665522443588804123392×61# − 1 || align="right" | 107 || 2014 || Primecoin ([https://primes.zone/#records block 368051])
|-
| 2nd || 38249410745534076442242419351233801191635692835712219264661912943040353398995076864×47# + 1 || align="right" | 101 || 2014 || Primecoin ([https://primes.zone/#records block 539977])
|-
| rowspan="2" | 14 || 1st || 4631673892190914134588763508558377441004250662630975370524984655678678526944768*47# - 1  || align="right" | 97 || 2018 || Primecoin ([https://primes.zone/#records block 2659167])
|-
| 2nd || 5819411283298069803200936040662511327268486153212216998535044251830806354124236416×47# + 1 || align="right" | 100 || 2014 || Primecoin ([https://primes.zone/#records block 547276])
|-
| rowspan="2" | 15 || 1st || 14354792166345299956567113728*43# - 1 || align="right" | 45 || 2016 || Andrey Balyakin
|-
| 2nd || 67040002730422542592*53# + 1 || align="right" | 40 || 2016 || Andrey Balyakin
|-
| rowspan="2" | 16 || 1st || 91304653283578934559359 || align="right" | 23 || 2008 || Jaroslaw Wroblewski
|-
| 2nd || 2×1540797425367761006138858881 − 1 || align="right" | 28 || 2014 || Chermoni & Wroblewski
|-
| rowspan="2" | 17 || 1st || 2759832934171386593519 || align="right" | 22 || 2008 || Jaroslaw Wroblewski
|-
| 2nd || 1540797425367761006138858881 || align="right" | 28 || 2014 || Chermoni & Wroblewski
|-
| 18 || 2nd || 658189097608811942204322721 || align="right" | 27 || 2014 || Chermoni & Wroblewski
|-
| 19 || 2nd || 79910197721667870187016101 || align="right" | 26 || 2014 || Chermoni & Wroblewski
|}

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

{{As of|2018}}、（両種について）最長のカニンガム鎖は長さ19で、Jaroslaw Wroblewski によって2014年に発見された<ref name="records"/>。

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

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

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

{| border="1" align="center" class="wikitable"
! 二進法 || [[十進法]]
|- align="right"
| 1000011011010000000100111101 || 141361469
|- align="right"
| 10000110110100000001001111011 || 282722939
|- align="right"
| 100001101101000000010011110111 || 565445879
|- align="right"
| 1000011011010000000100111101111 || 1130891759
|- align="right"
| 10000110110100000001001111011111 || 2261783519
|- align="right"
| 100001101101000000010011110111111 || 4523567039
|}

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

第1種カニンガム鎖では <math> p_i = 2^{i-1}p_1 + (2^{i-1}-1) \, </math> なので <math>p_i \equiv 2^{i-1} - 1 \pmod{p_1}</math> である。ここで[[フェルマーの小定理]]より <math>2^{p_1-1} \equiv 1 \pmod{p_1}</math> だから、<math>p_1</math> は <math>p_{p_1}</math> を割り切る（ <math> i = p_1 </math> とおく）。これより、無限の長さのカニンガム鎖は存在しない<ref>{{cite journal|last=Löh|first=Günter|title=Long chains of nearly doubled primes|journal=Mathematics of Computation|date=October 1989|volume=53|issue=188|pages=751–759|doi=10.1090/S0025-5718-1989-0979939-8|url=http://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0979939-8/}}</ref>。

== 関連項目 ==
* {{仮リンク|プライムコイン|en|Primecoin}}　 （カニンガム鎖を[[プルーフ・オブ・ワークシステム]]に用いている）
* [[Bi-twin chain]]
* {{仮リンク|等差数列における素数|en|Primes in arithmetic progression}}

==脚注==
<references/>

== 外部リンク ==
* [http://primes.utm.edu/glossary/page.php?sort=CunninghamChain The Prime Glossary: Cunningham chain]
* [https://primes.zone/ Primecoin discoveries (primes.zone): online database of primecoin findings with list of records and visualization]
* [http://primes.utm.edu/links/theory/special_forms/Cunningham_chains/ PrimeLinks++: Cunningham chain]

{{素数の分類}}
{{DEFAULTSORT:かにんかむさ}}
[[Category:数論]]
[[Category:素数]]
[[Category:素数の類]]
[[Category:数学のエポニム]]
[[Category:数学に関する記事]]