de.wikipedia.org

Cunningham-Kette – Wikipedia

Eine Cunningham-Kette (nach Allan Joseph Champneys Cunningham, englisch Cunningham chain, abgekürzt als CC) ist eine streng monoton wachsende endliche Folge $(a_{0},a_{1},\dotsc ,a_{k})$ von Primzahlen mit speziellen Eigenschaften. Dabei gibt solche der ersten Art und solche der zweiten Art.

Eine Cunningham-Kette der ersten Art ist eine Folge $(a_{0},a_{1},\dotsc ,a_{k})$ von Primzahlen, welche für einen Index $k\in \mathbb {N}$ und eine Primzahl $p\in \mathbb {N}$ die folgende Rekursionsvorschrift erfüllen:

$a_{0}=p\;,\quad a_{n+1}=2\!\cdot \!a_{n}+1\quad (n=0,1,\dotsc ,k-1)$ .

Es handelt sich also um eine Folge, die mit $a_{0}=p\;,a_{1}=2p+1,\;,a_{2}=4p+3,\;\dotsc$ beginnt. Die ersten $k$ dieser Primzahlen einer Cunningham-Kette der ersten Art sind also Sophie-Germain-Primzahlen.^{[A 1]} Ein einfaches Beispiel hierfür ist etwa 2, 5, 11, 23, 47.^{[A 2]}

In ähnlicher Weise wird unter einer Cunningham-Kette der zweiten Art eine endliche Folge $(a_{0},a_{1},\dotsc ,a_{k})$ von Primzahlen verstanden, welche die Rekursionsvorschrift

$a_{0}=p\;,\quad a_{n+1}=2\!\cdot \!a_{n}-1\quad (n=0,1,\dotsc ,k-1)$ .

erfüllen. Zwei einfache Beispiele für Cunningham-Ketten der zweiten Art sind etwa die Folge 2, 3, 5 und die Folge 1531, 3061, 6121, 12241, 24481.

Die Zahl $k+1$ bezeichnet man bei beiden Arten von Cunningham-Ketten als die Länge (englisch length) dieser (jeweiligen) Cunningham-Kette.

Die längste bislang bekannte Cunningham-Kette erster Art hat die Länge 17 und startet mit der Primzahl $a_{0}=2759832934171386593519$ . Sie wurde von Jaroslaw Wróblewski im Mai 2008 gefunden.^{[A 3]}

Die erste Cunningham-Kette der zweiten Art der Länge 16 wurde im Dezember 1997 von Tony Forbes gefunden. Sie beginnt mit der Primzahl $a_{0}=3203000719597029781$ . Im März 2014 fanden Raanan Chermoni und Jaroslaw Wróblewski sogar Cunningham-Ketten zweiter Art mit den Längen 18 und 19.^{[A 4]}

Cunningham-Ketten werden in der Kryptographie untersucht, da sie den Rahmen für eine Implementierung des Elgamal-Kryptosystems bieten, das als Elgamal-Verschlüsselungsverfahren und Elgamal-Signaturverfahren Anwendung findet.^[1]

Kleinste Cunningham-Kette mit k Kettengliedern
k	p
1	13
2	3
3	41
4	509
5	2
6	89
7	1.122.659
8	19.099.919
9	85.864.769
10	26.089.808.579
11	665.043.081.119
12	554.688.278.429
13	4.090.932.431.513.069
14	95.405.042.230.542.329

k=5:

p	2p+1	4p+3	8p+7	16p+15
2	5	11	23	47
53639	107279	214559	429119	858239
53849	107699	215399	430799	861599
61409	122819	245639	491279	982559
66749	133499	266999	533999	1067999
143609	287219	574439	1148879	2297759
167729	335459	670919	1341839	2683679
186149	372299	744599	1489199	2978399
206369	412739	825479	1650959	3301919
268049	536099	1072199	2144399	4288799
296099	592199	1184399	2368799	4737599
340919	681839	1363679	2727359	5454719
422069	844139	1688279	3376559	6753119
446609	893219	1786439	3572879	7145759

k=6:

p	2p+1	4p+3	8p+7	16p+15	32p+31
89	179	359	719	1439	2879
63419	126839	253679	507359	1014719	2029439
127139	254279	508559	1017119	2034239	4068479
405269	810539	1621079	3242159	6484319	25937279

Kleinste Cunningham-Kette mit k Kettengliedern
k	p
1	11
2	7
3	2
4	2131
5	1531

k=5:

p	2p-1	4p-3	8p-7	16p-15
1531	3061	6121	12241	24481
6841	13681	27361	54721	109441
15391	30781	61561	123121	246241
44371	88741	177481	354961	709921
57991	115981	231961	463921	927841
83431	166861	333721	667441	1334881
105871	211741	423481	846961	1693921

k=7:

p	2p-1	4p-3	8p-7	16p-15	32p-31	64p-63
16651	33301	66601	133201	266401	532801	1065601

Eine Folge von Primzahlen der Form: p, ap+b, a(ap+b)+b, ... mit festem a und festem b, die zueinander teilerfremd sind, nennt man eine verallgemeinerte Cunningham-Kette.

Beispiele verallgemeinerter Cunningham-Ketten mit der Gliedzahl k=5

k=5:

a	b	p	a(p)+b = ap+b	a(ap+b)+b = a²p+ab+b	a(a²p+ab+b)+b = a³p+a²b+ab+b	a(a³p+a²b+ab+b)+b = a⁴p+a³b+a²b+ab+b
3	2	1129	3389	10169	30509	91529
5	2	373	1867	9337	46687	233437

Sowohl für die Cunningham-Ketten der ersten Art als auch für die Cunningham-Ketten der zweiten Art ist es eine bislang ungeklärte Frage, ob zu jeder vorgegebenen Zahl $k\in \mathbb {N}$ solche existieren, welche mindestens von der Länge $k+1$ sind.^[2]

David Darling: The Universal Book of Mathematics. From Abracadabra to Zeno's Paradoxes. John Wiley and Sons, Hoboken NJ 2004, ISBN 0-471-27047-4, S. 84.
Paulo Ribenboim: The New Book of Prime Number Records. Springer Science+Business Media, New York 1996, ISBN 978-1-4612-6892-5, S. 333.

längste CC (der ersten Art) und andere Rekorde (englisch)
längste CC (der zweiten Art) und andere Rekorde (englisch)

↑ Die Frage, ob auch die Primzahl $a_{k}$ eine Sophie-Germain-Primzahl ist, wird offen gelassen.
↑ Sie ergibt sich für $a_{0}=2$ und lässt sich explizit wie folgt darstellen: a_n = 3 · 2ⁿ - 1 für n = 0, 1, 2, 3, 4.
↑ Siehe Weblinks!
↑ Siehe Weblinks!

↑ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
↑ Paulo Ribenboim: The New Book of Prime Number Records. 1996, S. 333

formelbasiert	Carol ((2ⁿ − 1)² − 2) \| Doppelte Mersenne (2^{2^p − 1} − 1) \| Fakultät (n! ± 1) \| Fermat (2^2ⁿ + 1) \| Kubisch (x³ − y³)/(x − y) \| Kynea ((2ⁿ + 1)² − 2) \| Leyland (x^y + y^x) \| Mersenne (2^p − 1) \| Mills (A^3ⁿ) \| Pierpont (2^u⋅3^v + 1) \| Primorial (p_n# ± 1) \| Proth (k⋅2ⁿ + 1) \| Pythagoreisch (4n + 1) \| Quartisch (x⁴ + y⁴) \| Thabit (3⋅2ⁿ − 1) \| Wagstaff ((2^p + 1)/3) \| Williams ((b-1)⋅bⁿ − 1) \| Woodall (n⋅2ⁿ − 1)
Primzahlfolgen	Bell \| Fibonacci \| Lucas \| Motzkin \| Pell \| Perrin
eigenschaftsbasiert	Elitär \| Fortunate \| Gut \| Glücklich \| Higgs \| Hochkototient \| Isoliert \| Pillai \| Ramanujan \| Regulär \| Stark \| Stern \| Wall–Sun–Sun \| Wieferich \| Wilson
basisabhängig	Belphegor \| Champernowne \| Dihedral \| Einzigartig \| Fröhlich \| Keith \| Lange \| Minimal \| Mirp \| Permutierbar \| Primeval \| Palindrom \| Repunit-Primzahl ((10ⁿ − 1)/9) \| Schwach \| Smarandache–Wellin \| Strobogrammatisch \| Tetradisch \| Trunkierbar \| Zirkular
basierend auf Tupel	Ausbalanciert (p − n, p, p + n) \| Chen \| Cousin (p, p + 4) \| Cunningham (p, 2p ± 1, …) \| Drilling (p, p + 2 oder p + 4, p + 6) \| Konstellation \| Sexy (p, p + 6) \| Sichere (p, (p − 1)/2) \| Sophie Germain (p, 2p + 1) \| Vierling (p, p + 2, p + 6, p + 8) \| Zwilling (p, p + 2) \| Zwillings-Bi-Kette (n ± 1, 2n ± 1, …)
nach Größe	Titanisch (1.000+ Stellen) \| Gigantisch (10.000+ Stellen) \| Mega (1.000.000+ Stellen) \| Beva (1.000.000.000+ Stellen)