Cunninghamův řetězec - Cunningham chain

v matematika, a Cunninghamův řetězec je určitá posloupnost prvočísla. Řetězy Cunningham jsou pojmenovány po matematik A. J. C. Cunningham. Také se jim říká řetězy téměř zdvojnásobených prvočísel.

Jedna aplikace pro řetězy Cunningham využívá výpočetní sílu k jejich identifikaci, aby bylo možné generovat virtuální měnu, podobně jak Bitcoin se těží.^[1]

Definice

A Cunninghamův řetězec prvního druhu délky n je posloupnost prvočísel (p₁, ..., p_n) tak, že pro všechny 1 ≤i < n, p_i+1 = 2p_i + 1. (Proto každý člen takového řetězce kromě posledního je a Sophie Germain prime a každý výraz kromě prvního je a bezpečný prime ).

Z toho vyplývá, že

${ 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 {zarovnáno}}}$

Nebo nastavením ${ displaystyle a = { frac {p_ {1} +1} {2}}}$ (číslo ${ displaystyle a}$ není součástí posloupnosti a nemusí být prvočíslem), máme ${ displaystyle p_ {i} = 2 ^ {i} a-1}$

Podobně, a Cunninghamův řetězec druhého druhu délky n je posloupnost prvočísel (p₁,...,p_n) tak, že pro všechny 1 ≤i < n, p_i+1 = 2p_i − 1.

Z toho vyplývá, že obecný pojem je

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

Nyní nastavením ${ displaystyle a = { frac {p_ {1} -1} {2}}}$, my máme ${ displaystyle p_ {i} = 2 ^ {i} a + 1}$.

Cunninghamovy řetězce se také někdy zobecňují na sekvence prvočísel (p₁, ..., p_n) tak, že pro všechny 1 ≤i ≤ n, p_i+1 = ap_i + b pro pevné coprime celá čísla A, b; výsledné řetězce se nazývají zobecněné Cunninghamovy řetězy.

Říká se Cunninghamův řetězec kompletní pokud ji nelze dále prodloužit, tj. pokud předchozí a následující výrazy v řetězci nejsou prvočísla.

Příklady

Mezi příklady kompletních řetězců Cunningham prvního druhu patří:

2, 5, 11, 23, 47 (Další číslo by bylo 95, ale to není prvočíslo.)

3, 7 (Další číslo bude 15, ale to není prvočíslo.)

29, 59 (Další číslo bude 119 = 7 * 17, ale to není prvočíslo.)

41, 83, 167 (Další číslo bude 335, ale to není prvočíslo.)

89, 179, 359, 719, 1439, 2879 (Další číslo bude 5759 = 13 * 443, ale to není prvočíslo.)

Mezi příklady kompletních řetězců Cunningham druhého druhu patří:

2, 3, 5 (Další číslo bude 9, ale to není prvočíslo.)

7, 13 (Další číslo bude 25, ale to není prvočíslo.)

19, 37, 73 (Další číslo bude 145, ale to není prvočíslo.)

31, 61 (Další číslo bude 121 = 11², ale to není hlavní.)

Cunninghamovy řetězce jsou nyní považovány za užitečné v kryptografických systémech, protože „poskytují dvě souběžná vhodná nastavení pro Kryptosystém ElGamal ... [které] lze implementovat v jakémkoli oboru, kde je obtížný problém diskrétního logaritmu. “^[2]

Největší známé řetězy Cunningham

Vyplývá to z Dicksonova domněnka a širší Schinzelova hypotéza H, oba široce věřil být pravdivý, že pro každého k existuje nekonečně mnoho Cunninghamových řetězců délky k. Neexistují však žádné známé přímé metody generování takových řetězců.

Existují počítačové soutěže o nejdelší Cunninghamův řetězec nebo o ten, který je sestaven z největších prvočísel, ale na rozdíl od průlomu Ben J. Green a Terence Tao - Věta o Green-Tao, že existují aritmetické průběhy prvočísel libovolné délky - o velkých Cunninghamových řetězcích není dosud znám žádný obecný výsledek.

q# označuje primitivní 2×3×5×7×...×q.

Od roku 2018^{[Aktualizace]}, nejdelší známý řetězec Cunninghamů jakéhokoli druhu, má délku 19, objevil Jaroslaw Wroblewski v roce 2014.^[3]

Shodnosti Cunninghamových řetězců

Nechte liché připravit ${ displaystyle p_ {1}}$ být prvním vrcholem řetězce Cunningham prvního druhu. První prvočíslo je tedy liché ${ displaystyle p_ {1} equiv 1 { pmod {2}}}$. Protože každý následující prime v řetězci je ${ displaystyle p_ {i + 1} = 2p_ {i} +1}$ z toho vyplývá, že ${ displaystyle p_ {i} equiv 2 ^ {i} -1 { pmod {2 ^ {i}}}}$. Tím pádem, ${ displaystyle p_ {2} equiv 3 { pmod {4}}}$, ${ displaystyle p_ {3} equiv 7 { pmod {8}}}$, a tak dále.

Výše uvedená vlastnost může být neformálně pozorována zvážením prvočísel řetězce v základně 2. (Všimněte si, že stejně jako u všech bází, vynásobení počtem základen „posune“ číslice doleva.) Když vezmeme v úvahu ${ displaystyle p_ {i + 1} = 2p_ {i} +1}$ v základně 2 to vidíme vynásobením ${ displaystyle p_ {i}}$ o 2, nejméně významná číslice ${ displaystyle p_ {i}}$ se stává druhou nejméně významnou číslicí ${ displaystyle p_ {i + 1}}$. Protože ${ displaystyle p_ {i}}$ je liché - to znamená, že nejméně významná číslice je 1 v základně 2 - víme, že druhá nejmenší významná číslice z ${ displaystyle p_ {i + 1}}$ je také 1. A konečně to vidíme ${ displaystyle p_ {i + 1}}$ bude liché kvůli přidání 1 do ${ displaystyle 2p_ {i}}$. Tímto způsobem jsou postupná prvočísla v Cunninghamově řetězci v podstatě posunuta doleva v binárním formátu, přičemž ty vyplňují nejméně významné číslice. Například zde je kompletní řetězec délky 6, který začíná na 141361469:

Podobný výsledek platí pro řetězy Cunningham druhého druhu. Z pozorování ${ displaystyle p_ {1} equiv 1 { pmod {2}}}$ a vztah ${ displaystyle p_ {i + 1} = 2p_ {i} -1}$ z toho vyplývá, že ${ displaystyle p_ {i} equiv 1 { pmod {2 ^ {i}}}}$. V binární notaci končí prvočísla v Cunninghamově řetězci druhého druhu vzorem „0 ... 01“, kde pro každou ${ displaystyle i}$, počet nul ve vzoru pro ${ displaystyle p_ {i + 1}}$ je o více než počet nul pro ${ displaystyle p_ {i}}$. Stejně jako u Cunninghamových řetězců prvního druhu se bity vlevo od vzoru posouvají doleva o jednu pozici s každým následujícím prvočíslem.

Podobně proto ${ displaystyle p_ {i} = 2 ^ {i-1} p_ {1} + (2 ^ {i-1} -1) ,}$ z toho vyplývá, že ${ displaystyle p_ {i} equiv 2 ^ {i-1} -1 { pmod {p_ {1}}}}$. Ale tím Fermatova malá věta, ${ displaystyle 2 ^ {p_ {1} -1} equiv 1 { pmod {p_ {1}}}}$, tak ${ displaystyle p_ {1}}$ rozděluje ${ displaystyle p_ {p_ {1}}}$ (tj. s ${ displaystyle i = p_ {1}}$). Žádný Cunninghamův řetězec tedy nemůže mít nekonečnou délku.^[4]

Viz také

• Primecoin, který používá řetězy Cunningham jako systém proof-of-work
• Dvojitý řetěz
• Prvočísla v aritmetickém postupu

Reference

externí odkazy

• Prime Glossary: ​​Cunningham chain
• Objevy Primecoinů (primes.zone): online databáze nálezů primecoinů se seznamem záznamů a vizualizací
• PrimeLinks ++: Cunninghamův řetězec
• OEIS sekvence A005602 (Nejmenší prvočíslo začínající kompletní Cunninghamův řetězec o délce n (prvního druhu)) - první člen nejnižších úplných Cunninghamových řetězců prvního druhu délkyn, pro 1 ≤n ≤ 14
• OEIS sekvence A005603 (Řetězce délky n téměř zdvojnásobených prvočísel) - první člen nejnižšího úplného Cunninghamova řetězce druhého druhu s délkoun, pro 1 ≤n ≤ 15