imported>Aka: https, Kleinkram

2022-02-08T19:51:56Z

https, Kleinkram

Neue Seite

Eine '''Cunningham-Kette''' (nach [[Allan Joseph Champneys Cunningham]], {{enS|Cunningham chain}}, abgekürzt als CC) ist eine [[monotone Folge|streng monoton wachsende]] [[endliche Folge]] <math>(a_0,a_1,\dotsc,a_k)</math> von [[Primzahl]]en mit speziellen Eigenschaften. Dabei gibt solche der '''ersten Art''' und solche der '''zweiten Art'''.

Eine '''Cunningham-Kette der ersten Art''' ist eine Folge <math>(a_0,a_1,\dotsc,a_k)</math> von Primzahlen, welche für einen [[Indexmenge|Index]] <math>k \in \N</math> und eine Primzahl <math>p \in \N</math> die folgende [[Rekursive Definition|Rekursionsvorschrift]] erfüllen:
:<math>a_0=p \; , \quad a_{n+1}=2 \! \cdot \! a_n + 1 \quad ( n=0,1,\dotsc,k-1 )</math>.

Es handelt sich also um eine Folge, die mit <math>a_0=p \; , a_1=2p+1, \; , a_2=4p+3, \; \dotsc</math> beginnt. Die ersten <math>k</math> dieser Primzahlen einer Cunningham-Kette der ersten Art sind also [[Sophie-Germain-Primzahl]]en.<ref group="A">Die Frage, ob auch die Primzahl <math>a_k</math> eine Sophie-Germain-Primzahl ist, wird offen gelassen.</ref> Ein einfaches Beispiel hierfür ist etwa 2, 5, 11, 23, 47.<ref group="A">Sie ergibt sich für <math>a_0 = 2</math> und lässt sich explizit wie folgt darstellen: an = 3 · 2n - 1 für n = 0, 1, 2, 3, 4.</ref>

In ähnlicher Weise wird unter einer '''Cunningham-Kette der zweiten Art''' eine endliche Folge <math>(a_0,a_1,\dotsc,a_k)</math> von Primzahlen verstanden, welche die Rekursionsvorschrift
:<math>a_0=p \; , \quad a_{n+1}=2 \! \cdot \! a_n - 1 \quad ( n=0,1,\dotsc,k-1 )</math>.

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 <math>k+1</math> bezeichnet man bei beiden Arten von Cunningham-Ketten als die ''Länge'' ({{enS|length}}) dieser (jeweiligen) Cunningham-Kette.

Die längste bislang bekannte Cunningham-Kette erster Art hat die Länge 17 und startet mit der Primzahl <math>a_0 = 2759832934171386593519 </math>. Sie wurde von [[Jaroslaw Wróblewski]] im Mai 2008 gefunden.<ref group="A">Siehe Weblinks!</ref>

Die erste Cunningham-Kette der zweiten Art der Länge 16 wurde im Dezember 1997 von Tony Forbes gefunden. Sie beginnt mit der Primzahl <math>a_0 = 3203000719597029781</math>. Im März 2014 fanden Raanan Chermoni und Jaroslaw Wróblewski sogar Cunningham-Ketten zweiter Art mit den Längen 18 und 19.<ref group="A">Siehe Weblinks!</ref>

== 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.<ref>Joe Buhler, ''Algorithmic Number Theory: Third International Symposium, ANTS-III''. New York: Springer (1998): 290</ref>

== Tabellen mit Cunningham-Ketten ==

=== Cunningham-Ketten der ersten Art mit ''k'' Gliedern ===

{| class="wikitable"
|colspan=2 style="text-align:center"|Kleinste Cunningham-Kette mit ''k'' Kettengliedern
|-
|'''k''' ||align=right| '''p'''
|-
|1 ||align=right| 13
|-
|2 ||align=right| 3
|-
|3 ||align=right| 41
|-
|4 ||align=right| 509
|-
|5 ||align=right| 2
|-
|6 ||align=right| 89
|-
|7 ||align=right| 1.122.659
|-
|8 ||align=right| 19.099.919
|-
|9 ||align=right| 85.864.769
|-
|10 ||align=right| 26.089.808.579
|-
|11 ||align=right| 665.043.081.119
|-
|12 ||align=right| 554.688.278.429
|-
|13 ||align=right| 4.090.932.431.513.069
|-
|14 ||align=right|95.405.042.230.542.329
|}

'''k=5:'''

{| class="wikitable" style="text-align:right"
! 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:'''

{| class="wikitable" style="text-align:right"
! 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 ===

{| class="wikitable"
|colspan=2 style="text-align:center"|Kleinste Cunningham-Kette mit ''k'' Kettengliedern
|-
|'''k''' ||align=right| '''p'''
|-
|1 ||align=right| 11
|-
|2 ||align=right| 7
|-
|3 ||align=right| 2
|-
|4 ||align=right| 2131
|-
|5 ||align=right| 1531
|}

'''k=5:'''

{| class="wikitable" style="text-align:right"
! 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:'''

{| class="wikitable" style="text-align:right"
! 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, ''a''p+''b'', ''a''(''a''p+''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:'''

{| class="wikitable" style="text-align:right"
! 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 <math>k \in \N</math> solche existieren, welche mindestens von der Länge <math>k+1</math> sind.<ref name="PR">Paulo Ribenboim: ''The New Book of Prime Number Records.'' 1996, S. 333</ref>

== Literatur ==
* David Darling: [https://books.google.de/books?id=nnpChqstvg0C&pg=PA84&lpg=PA84&dq=cunningham+chain&source=bl&ots=lfFKevEuXu&sig=pOxfHSJ_4wl7Gj176KyCc4Nvqqg&hl=en&ei=mRClSbaAM4HG-Aa-6ciXBQ&sa=X&oi=book_result&ct=result&redir_esc=y 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.
* {{Literatur
|Autor= [[Paulo Ribenboim]]
|Titel=The New Book of Prime Number Records
|Verlag=[[Springer Science+Business Media]]
|Ort=New York
|Datum=1996
|ISBN=978-1-4612-6892-5
|Seiten=333}}

== Weblinks ==
* [https://primes.utm.edu/top20/page.php?id=19 längste CC (der ersten Art) und andere Rekorde] (englisch)
* [https://primes.utm.edu/top20/page.php?id=20 längste CC (der zweiten Art) und andere Rekorde] (englisch)

== Anmerkungen ==
<references group="A" />

== Einzelnachweise ==
<references />

{{Navigationsleiste Primzahlklassen}}

[[Kategorie:Ganzzahlmenge]]
[[Kategorie:Primzahl]]
[[Kategorie:Zahlentheorie]]

Cunningham-Kette - Versionsgeschichte

imported>Aka: https, Kleinkram