Cunninghamský řetěz

Cunninghamův řetězec ( řetězec téměř zdvojených čísel ) - posloupnost prvočísel určitého typu, pojmenovaná po matematikovi Alanu Cunninghamovi.

Cunninghamův řetězec prvního druhu délky n je posloupnost prvočísel ( p 1 ,…, p n ) taková, že pro všechna 1 ≤ i < n , p i +1 = 2 p i + 1 (tedy každý člen tohoto řetězce, s výjimkou druhého, je číslo Sophie Germainové a s výjimkou prvního je bezpečné prvočíslo ): , , , …, . $p_{2}=2p_{1}+1$ $p_{3}=4p_{1}+3$ $p_{4}=8p_{1}+7$ $p_{i}=2^{i-1}p_{1}+(2^{i-1}-1)$

Cunninghamský řetězec druhého druhu délky n je posloupnost prvočísel ( p 1 ,…, p n ) taková, že pro všechna 1 ≤ i < n , p i +1 = 2 p i — 1 : $p_{i}=2^{i-1}p_{1}+(2^{i-1}+1)$

Cunninghamovy řetězce jsou někdy zobecněny jako posloupnost prvočísel ( p 1 ,…, p n ) tak, že pro všechna 1 ≤ i < n , p i +1 = api + b pro pevná koprime celá čísla a , b . Takový řetězec se nazývá zobecněný Cunninghamův řetězec .

Cunninghamův řetězec se nazývá úplný, pokud jej nelze rozšířit, to znamená, pokud předchozí a následující členy posloupnosti nejsou jednoduché.

Cunninghamské řetězce jsou nyní uznávány jako užitečné pro kryptografické systémy, protože „poskytují dvě konkurenční přijatelná nastavení pro schéma ElGamal šifry , které lze použít kdekoli, kde je problém s počítáním jednotlivého logaritmu obtížný“ [1] .

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

Podle Dixonovy hypotézy a Schinzelovy obecnější hypotézy H , o které se většina vědců domnívá, že je pravdivá, pro každé k existuje nekonečný počet Cunninghamových řetězců délky k . Není však známa žádná metoda pro generování takových obvodů.

Největší známý Cunninghamův řetězec délky k k 6.8.2013 [2] )

k	Typ	p 1 (počáteční prvočíslo)	Počet číslic	Rok	objevil
jeden		2 57885161 - 1	17425170	2013	GIMPS/Curtis Cooper
2	1	183027×2 265440 − 1	200701	2012	T.Wu
3	1	914546877×2 34772 − 1	10477	2010	T.Wu
čtyři	1	1249097877×6599# − 1	2835	2011	Michael Angel
5	1	4250172704×2749# − 1	1183	2012	D. Augustin
6	1	37488065464×1483# − 1	633	2010	D. Augustin
7	1	162597166369×827# − 1	356	2010	D. Augustin
osm	2	1148424905221×509# + 1	224	2010	D. Augustin
9	1	65728407627×431# − 1	185	2005	D. Augustin
deset	1	2×73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1	140	2013	primární mince
jedenáct	1	73853903764168979088206401473739410396455001112581722569026969860983656346568919×151# − 1	140	2013	primární mince
12	2	2636633268864093784733341387047271336974122837948496277769621396327294641140893808×43# + 1	97	2013	primární mince
13	1	1753286498051×71# − 1	39	2005	D. Augustin
čtrnáct	2	335898524600734221050749906451371	33	2008	JK Andersen
patnáct	2	28320350134887132315879689643841	32	2008	J. Wroblewski
16	2	2368823992523350998418445521	28	2008	J. Wroblewski
17	2	1302312696655394336638441	25	2008	J. Wroblewski

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

Do roku 2011 měl největší známý Cunninghamský řetěz jakéhokoli druhu délku 17. První nalezený byl řetěz prvního druhu, začínající na 2759832934171386593519 (nalezen Yaroslavem Wroblewskim v roce 2008). [2]

Kompatibilita řetězů Cunningham

Nechť je liché prvočíslo prvním číslem v Cunninghamově řetězci prvního druhu. Protože první číslo je liché, . Protože všechna následující čísla v řetězci jsou stejná , pak . Proto, , , a tak dále. $p_{1}$ $p_{1}\equiv 1{\pmod {2))$ $p_{i+1}=2p_{i}+1$ ${\displaystyle p_{i}\equiv 2^{i}-1{\pmod {2^{i))))$ $p_{2}\equiv 3{\pmod {4}}$ $p_{3}\equiv 7{\pmod {8}}$

Tuto vlastnost lze neformálně pozorovat při reprezentaci čísel v dvojkové soustavě (všimněte si, že pro jakýkoli základ vynásobení čísla základem způsobí posunutí číslic doleva) Pokud budeme reprezentovat binárně, uvidíme, že při vynásobení 2 bude nejmenší významný znak čísla se stává druhým znakem čísla . Od lichého je nejméně významné znaménko 1 a stává se druhým znaménkem zprava . A nakonec vidíme, co se stane lichým, když se k 1 přidá 1 . Jednoduché deriváty v Cunninghamově řetězci se tedy získají posunutím binárního čísla doleva o jednu pozici a obsazením volné pozice jedničkou. Zde je například kompletní řetězec délky 6, počínaje 141361469: $p_{i+1}=2p_{i}+1$ $p_{i}$ $p_{i}$ $p_{{i+1}}$ $p_{i}$ $p_{{i+1}}$ $p_{{i+1}}$ ${\displaystyle 2p_{i))$

Binární	Desetinný
1000011011010000000100111101	141361469
10000110110100000001001111011	282722939
100001101101000000010011110111	565445879
1000011011010000000100111101111	1130891759
10000110110100000001001111011111	2261783519
100001101101000000010011110111111	4523567039

Podobný výsledek lze získat také pro řetězy druhého druhu. Všimněte si, že z a ze vztahu vyplývá, že . V binárním zápisu končí prvočísla v Cunninghamově řetězci druhého druhu "0... 01", kde pro libovolný počet nul pro je o jednu větší než počet nul . Stejně jako v případě čísel prvního druhu jsou bity nalevo od nich posunuty doleva o jednu pozici v každém následujícím článku řetězce. $p_{1}\equiv 1{\pmod {2))$ $p_{i+1}=2p_{i}-1$ ${\displaystyle p_{i}\equiv 1{\pmod {2^{i))))$ $i$ $p_{{i+1}}$ $p_{i}$

Poznámky

↑ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III . New York: Springer (1998): 290
↑ 1 2 Dirk Augustin, Cunningham Chain records . Získáno dne 2011-11-08.

Odkazy

Hlavní glosář: Řetěz Cunningham
PrimeLinks++: Řetěz Cunningham
sekvence A005602 v OEIS : první člen minimálního kompletního Cunninghamského řetězce prvního druhu délky , pro $n$ $1\leq n\leq 14$
sekvence A005603 v OEIS : první člen minimálního kompletního Cunninghamského řetězce druhého druhu délky , např. $n$ $1\leq n\leq 15$