Cunningham-Kette

Eine Cunningham-Kette (nach Allan Joseph Champneys Cunningham) der ersten Art ist eine Folge von Primzahlen der Form:

$a_0=p \quad a_{n+1}=2 \! \cdot \! a_n + 1,$

also p, 2p+1, 2(2p+1)+1, 2(2(2p+1)+1)+1, …

Alle Primzahlen einer solchen Folge, mit Ausnahme der letzten Primzahl, sind Sophie-Germain-Primzahlen.

Die erste Cunningham-Kette ist die Folge: 2, 5, 11, 23, 47. Sie ergibt sich für a₀ = 2 und lässt sich explizit wie folgt darstellen: a_n = 3 · 2ⁿ - 1, für n = 0, 1, 2, 3, 4.

Eine Cunningham-Kette der zweiten Art ist eine Folge von Primzahlen der Form:

$a_0=p \quad a_{n+1}=2 \! \cdot \! a_n - 1$

Zwei Beispiele für Cunningham-Ketten der zweiten Art sind die Folge 2, 3, 5 und die Folge 1531, 3061, 6121, 12241, 24481.

Die längste bekannte Cunningham Kette beliebiger Art ist von der ersten Art, hat die Länge 17 und startet mit 2759832934171386593519.^[1] Gefunden wurde sie im März 2008. Die erste Kette der Länge 16 wurde 1997 gefunden.

Kryptographie

Cunningham-Ketten werden in der Kryptographie untersucht, da sie den Rahmen für eine Implementierung des Elgamal-Kryptosystems bieten.^[2]

Tabellen mit Cunningham-Ketten

Cunningham-Ketten der ersten Art mit k Gliedern

Kleinste Cunningham-Kette mit k Kettengliedern
k	p
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

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  ap+b
---------------------------------------
 3  2  1129  3389  10169  30509   91529
 5  2   373  1867   9337  46687  233437 

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 (engl.)
• längste CC (der zweiten Art) und andere Rekorde (engl.)

Einzelnachweise

1. ↑ J. Wroblewski: 1st known CC17
2. ↑ Joe Buhler, Algorithmic Number Theory: Third International Symposium, ANTS-III. New York: Springer (1998): 290