Cunningham-Kette
# Cunningham-Kette

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. 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 $(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.
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.

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

## Tabellen mit Cunningham-Ketten
### Cunningham-Ketten der ersten Art mit k Gliedern

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

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

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$^2$p+ab+b | a(a$^2$p+ab+b)+b = a$^3$p+a$^2$b+ab+b | a(a$^3$p+a$^2$b+ab+b)+b = a$^4$p+a$^3$b+a$^2$b+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 $k\in \mathbb {N}$ solche existieren, welche mindestens von der Länge $k+1$ sind.