Cunningham-Kette

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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_0 = 2 und lässt sich explizit wie folgt darstellen: an = 3 · 2n - 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[Bearbeiten]

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

Tabellen mit Cunningham-Ketten[Bearbeiten]

Cunningham-Ketten der ersten Art mit k Gliedern[Bearbeiten]

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[Bearbeiten]

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

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

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