Cunningham-Kette

Eine Cunningham-Kette (nach Allan Joseph Champneys Cunningham, englisch Cunningham chain, abgekürzt als CC) ist eine streng monoton wachsende endliche Folge ${\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 ${\displaystyle (a_{0},a_{1},\dotsc ,a_{k})}$ von Primzahlen, welche für einen Index ${\displaystyle k\in \mathbb {N} }$ und eine Primzahl ${\displaystyle p\in \mathbb {N} }$ die folgende Rekursionsvorschrift erfüllen:

${\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 ${\displaystyle a_{0}=p\;,a_{1}=2p+1,\;,a_{2}=4p+3,\;\dotsc }$ beginnt. Die ersten ${\displaystyle k}$ 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 ${\displaystyle (a_{0},a_{1},\dotsc ,a_{k})}$ von Primzahlen verstanden, welche die Rekursionsvorschrift

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle a_{0}=2759832934171386593519}$. 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 ${\displaystyle 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.^{[A 4]}

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.^[1]

Tabellen mit Cunningham-Ketten

Cunningham-Ketten der ersten Art mit k Gliedern

k=5:

k=6:

Cunningham-Ketten der zweiten Art mit k Gliedern

k=5:

k=7:

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:

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 ${\displaystyle k\in \mathbb {N} }$ solche existieren, welche mindestens von der Länge ${\displaystyle k+1}$ sind.^[2]

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

• längste CC (der ersten Art) und andere Rekorde (englisch)
• längste CC (der zweiten Art) und andere Rekorde (englisch)

Anmerkungen

1. ↑ Die Frage, ob auch die Primzahl ${\displaystyle a_{k}}$ eine Sophie-Germain-Primzahl ist, wird offen gelassen.
2. ↑ Sie ergibt sich für ${\displaystyle a_{0}=2}$ und lässt sich explizit wie folgt darstellen: a_n = 3 · 2ⁿ - 1 für n = 0, 1, 2, 3, 4.
3. ↑ Siehe Weblinks!
4. ↑ Siehe Weblinks!

Einzelnachweise

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