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 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 von Primzahlen, welche für einen Index und eine Primzahl die folgende Rekursionsvorschrift erfüllen:
- .
Es handelt sich also um eine Folge, die mit beginnt. Die ersten 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 von Primzahlen verstanden, welche die Rekursionsvorschrift
- .
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 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 . 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 . 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]
Kryptographie
[Bearbeiten | Quelltext bearbeiten]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]
Tabellen mit Cunningham-Ketten
[Bearbeiten | Quelltext bearbeiten]Cunningham-Ketten der ersten Art mit k Gliedern
[Bearbeiten | Quelltext bearbeiten]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 |
Cunningham-Ketten der zweiten Art mit k Gliedern
[Bearbeiten | Quelltext bearbeiten]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 verallgemeinerte Cunningham-Kette
[Bearbeiten | Quelltext bearbeiten]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 = a2p+ab+b | a(a2p+ab+b)+b = a3p+a2b+ab+b | a(a3p+a2b+ab+b)+b = a4p+a3b+a2b+ab+b |
---|---|---|---|---|---|---|
3 | 2 | 1129 | 3389 | 10169 | 30509 | 91529 |
5 | 2 | 373 | 1867 | 9337 | 46687 | 233437 |
Offenes Problem
[Bearbeiten | Quelltext bearbeiten]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 solche existieren, welche mindestens von der Länge sind.[2]
Literatur
[Bearbeiten | Quelltext bearbeiten]- 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.
Weblinks
[Bearbeiten | Quelltext bearbeiten]- längste CC (der ersten Art) und andere Rekorde (englisch)
- längste CC (der zweiten Art) und andere Rekorde (englisch)
Anmerkungen
[Bearbeiten | Quelltext bearbeiten]- ↑ Die Frage, ob auch die Primzahl eine Sophie-Germain-Primzahl ist, wird offen gelassen.
- ↑ Sie ergibt sich für und lässt sich explizit wie folgt darstellen: an = 3 · 2n - 1 für n = 0, 1, 2, 3, 4.
- ↑ Siehe Weblinks!
- ↑ Siehe Weblinks!