Eine Cunningham-Kette (nach Allan Joseph Champneys Cunningham, , 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.Die Frage, ob auch die Primzahl eine Sophie-Germain-Primzahl ist, wird offen gelassen. Ein einfaches Beispiel hierfür ist etwa 2, 5, 11, 23, 47.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.
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 () 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.Siehe Weblinks!
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.Siehe Weblinks!
Kryptographie 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.Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290
Tabellen mit Cunningham-Ketten
Cunningham-Ketten der ersten Art mit k Gliedern
Kleinste Cunningham-Kettemit k Kettengliedernk p1 132 33 414 5095 26 897 1.122.6598 19.099.9199 85.864.76910 26.089.808.57911 665.043.081.11912 554.688.278.42913 4.090.932.431.513.06914 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
Kleinste Cunningham-Kettemit k Kettengliedernk p1 112 73 24 21315 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
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 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.Paulo Ribenboim: The New Book of Prime Number Records. 1996, S. 333
Literatur 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.
Weblinks längste CC (der ersten Art) und andere Rekorde (englisch) längste CC (der zweiten Art) und andere Rekorde (englisch)
Anmerkungen
Einzelnachweise
Kategorie:Ganzzahlmenge Kategorie:Primzahl Kategorie:Zahlentheorie