www.wikidata.de-de.nina.az

Cunningham Kette Eine nach Allan Joseph Champneys Cunningham englisch Cunningham chain abgekürzt als CC ist eine streng

Cunningham-Kette

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. Ein einfaches Beispiel hierfür ist etwa 2, 5, 11, 23, 47.

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.

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.

Kryptographie 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.

Tabellen mit Cunningham-Ketten Bearbeiten

Cunningham-Ketten der ersten Art mit k Gliedern 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

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

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

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.

Literatur 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

Anmerkungen Bearbeiten

  1. Die Frage, ob auch die Primzahl eine Sophie-Germain-Primzahl ist, wird offen gelassen.
  2. 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.
  3. Siehe Weblinks!
  4. Siehe Weblinks!

Einzelnachweise Bearbeiten

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


formelbasiert

Carol ((2n − 1)2 − 2) | Doppelte Mersenne (22p − 1 − 1) | Fakultät (n! ± 1) | Fermat (22n + 1) | Kubisch (x3 − y3)/(x − y) | Kynea ((2n + 1)2 − 2) | Leyland (xy + yx) | Mersenne (2p − 1) | Mills (A3n) | Pierpont (2u⋅3v + 1) | Primorial (pn# ± 1) | Proth (k⋅2n + 1) | Pythagoreisch (4n + 1) | Quartisch (x4 + y4) | Thabit (3⋅2n − 1) | Wagstaff ((2p + 1)/3) | Williams ((b-1)⋅bn − 1) | Woodall (n⋅2n − 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

basis­abhängig

Belphegor | Champernowne | Dihedral | Einzigartig | Fröhlich | Keith | Lange | Minimal | Mirp | Permutierbar | Primeval | Palindrom | Repunit-Primzahl ((10n − 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)

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Eine Cunningham Kette nach Allan Joseph Champneys Cunningham englisch Cunningham chain abgekurzt als CC ist eine streng monoton wachsende endliche Folge a 0 a 1 a k displaystyle 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 a k displaystyle a 0 a 1 dotsc a k von Primzahlen welche fur einen Index k N displaystyle k in mathbb N und eine Primzahl p N displaystyle p in mathbb N die folgende Rekursionsvorschrift erfullen a 0 p a n 1 2 a n 1 n 0 1 k 1 displaystyle 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 2 p 1 a 2 4 p 3 displaystyle a 0 p a 1 2p 1 a 2 4p 3 dotsc beginnt Die ersten k displaystyle k dieser Primzahlen einer Cunningham Kette der ersten Art sind also Sophie Germain Primzahlen A 1 Ein einfaches Beispiel hierfur ist etwa 2 5 11 23 47 A 2 In ahnlicher Weise wird unter einer Cunningham Kette der zweiten Art eine endliche Folge a 0 a 1 a k displaystyle a 0 a 1 dotsc a k von Primzahlen verstanden welche die Rekursionsvorschrift a 0 p a n 1 2 a n 1 n 0 1 k 1 displaystyle a 0 p quad a n 1 2 cdot a n 1 quad n 0 1 dotsc k 1 erfullen Zwei einfache Beispiele fur Cunningham Ketten der zweiten Art sind etwa die Folge 2 3 5 und die Folge 1531 3061 6121 12241 24481 Die Zahl k 1 displaystyle k 1 bezeichnet man bei beiden Arten von Cunningham Ketten als die Lange englisch length dieser jeweiligen Cunningham Kette Die langste bislang bekannte Cunningham Kette erster Art hat die Lange 17 und startet mit der Primzahl a 0 2759832934171386593519 displaystyle a 0 2759832934171386593519 Sie wurde von Jaroslaw Wroblewski im Mai 2008 gefunden A 3 Die erste Cunningham Kette der zweiten Art der Lange 16 wurde im Dezember 1997 von Tony Forbes gefunden Sie beginnt mit der Primzahl a 0 3203000719597029781 displaystyle a 0 3203000719597029781 Im Marz 2014 fanden Raanan Chermoni und Jaroslaw Wroblewski sogar Cunningham Ketten zweiter Art mit den Langen 18 und 19 A 4 Inhaltsverzeichnis 1 Kryptographie 2 Tabellen mit Cunningham Ketten 2 1 Cunningham Ketten der ersten Art mit k Gliedern 2 2 Cunningham Ketten der zweiten Art mit k Gliedern 3 Eine verallgemeinerte Cunningham Kette 4 Offenes Problem 5 Literatur 6 Weblinks 7 Anmerkungen 8 EinzelnachweiseKryptographie BearbeitenCunningham Ketten werden in der Kryptographie untersucht da sie den Rahmen fur eine Implementierung des Elgamal Kryptosystems bieten das als Elgamal Verschlusselungsverfahren und Elgamal Signaturverfahren Anwendung findet 1 Tabellen mit Cunningham Ketten BearbeitenCunningham Ketten der ersten Art mit k Gliedern Bearbeiten 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 329k 5 p 2p 1 4p 3 8p 7 16p 152 5 11 23 4753639 107279 214559 429119 85823953849 107699 215399 430799 86159961409 122819 245639 491279 98255966749 133499 266999 533999 1067999143609 287219 574439 1148879 2297759167729 335459 670919 1341839 2683679186149 372299 744599 1489199 2978399206369 412739 825479 1650959 3301919268049 536099 1072199 2144399 4288799296099 592199 1184399 2368799 4737599340919 681839 1363679 2727359 5454719422069 844139 1688279 3376559 6753119446609 893219 1786439 3572879 7145759k 6 p 2p 1 4p 3 8p 7 16p 15 32p 3189 179 359 719 1439 287963419 126839 253679 507359 1014719 2029439127139 254279 508559 1017119 2034239 4068479405269 810539 1621079 3242159 6484319 25937279Cunningham Ketten der zweiten Art mit k Gliedern Bearbeiten Kleinste Cunningham Kettemit k Kettengliedernk p1 112 73 24 21315 1531k 5 p 2p 1 4p 3 8p 7 16p 151531 3061 6121 12241 244816841 13681 27361 54721 10944115391 30781 61561 123121 24624144371 88741 177481 354961 70992157991 115981 231961 463921 92784183431 166861 333721 667441 1334881105871 211741 423481 846961 1693921k 7 p 2p 1 4p 3 8p 7 16p 15 32p 31 64p 6316651 33301 66601 133201 266401 532801 1065601Eine verallgemeinerte Cunningham Kette BearbeitenEine 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 5k 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 b3 2 1129 3389 10169 30509 915295 2 373 1867 9337 46687 233437Offenes Problem BearbeitenSowohl fur die Cunningham Ketten der ersten Art als auch fur die Cunningham Ketten der zweiten Art ist es eine bislang ungeklarte Frage ob zu jeder vorgegebenen Zahl k N displaystyle k in mathbb N nbsp solche existieren welche mindestens von der Lange k 1 displaystyle k 1 nbsp sind 2 Literatur BearbeitenDavid 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 Bearbeitenlangste CC der ersten Art und andere Rekorde englisch langste CC der zweiten Art und andere Rekorde englisch Anmerkungen Bearbeiten Die Frage ob auch die Primzahl a k displaystyle a k nbsp eine Sophie Germain Primzahl ist wird offen gelassen Sie ergibt sich fur a 0 2 displaystyle a 0 2 nbsp und lasst sich explizit wie folgt darstellen an 3 2n 1 fur n 0 1 2 3 4 Siehe Weblinks Siehe Weblinks Einzelnachweise Bearbeiten 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 333V DPrimzahl mengenformelbasiert Carol 2n 1 2 2 Doppelte Mersenne 22p 1 1 Fakultat n 1 Fermat 22n 1 Kubisch x3 y3 x y Kynea 2n 1 2 2 Leyland xy yx Mersenne 2p 1 Mills A3n Pierpont 2u 3v 1 Primorial pn 1 Proth k 2n 1 Pythagoreisch 4n 1 Quartisch x4 y4 Thabit 3 2n 1 Wagstaff 2p 1 3 Williams b 1 bn 1 Woodall n 2n 1 Primzahlfolgen Bell Fibonacci Lucas Motzkin Pell Perrineigenschaftsbasiert Elitar Fortunate Gut Glucklich Higgs Hochkototient Isoliert Pillai Ramanujan Regular Stark Stern Wall Sun Sun Wieferich Wilsonbasis abhangig Belphegor Champernowne Dihedral Einzigartig Frohlich Keith Lange Minimal Mirp Permutierbar Primeval Palindrom Repunit Primzahl 10n 1 9 Schwach Smarandache Wellin Strobogrammatisch Tetradisch Trunkierbar Zirkularbasierend 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 Grosse Titanisch 1 000 Stellen Gigantisch 10 000 Stellen Mega 1 000 000 Stellen Beva 1 000 000 000 Stellen Abgerufen von https de wikipedia org w index php title Cunningham Kette amp oldid 220011725