Additionskette

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Eine Additionskette für eine positive ganze Zahl ist eine endliche, streng monoton steigende Folge positiver ganzer Zahlen, die mit 1 beginnt und mit endet und bei der jede Zahl der Folge außer der 1 die Summe zweier nicht notwendig verschiedener vorangegangener Folgenglieder ist. Unter der Länge einer Additionskette versteht man die Anzahl der Folgenglieder, die Summe vorangegangener Folgenglieder sind – die 1 am Anfang wird also nicht mitgezählt. Die minimale Länge aller Additionsketten für wird mit bezeichnet.

Beispiel:

  • 1, 2, 4, 5, 9 ist eine Additionskette der Länge 4 für 9, denn 2 = 1+1, 4 = 2+2, 5 = 4+1 und 9 = 5+4.
  • 1, 2, 4, 6, 9 ist keine Additionskette für 9, denn 9 ist nicht Summe zweier vorangegangener Folgenglieder.

, denn es gibt keine kürzere Additionskette für 9. Andere Additionsketten für 9 sind gleich lang (zwei weitere) oder länger.

Anwendung und Geschichte[Bearbeiten | Quelltext bearbeiten]

Die erste und bis heute wohl wichtigste Anwendung von Additionsketten ist die Optimierung der Berechnung von Potenzen mit großen natürlichen Exponenten. Hat man eine Additionskette der Länge für eine positive ganze Zahl , so lässt sich zu einer Zahl die Potenz durch Multiplikationen berechnen. Sind nämlich für ein Glied der Additionskette, das Summe vorangegangener Glieder und ist, und schon berechnet worden, so ergibt sich daraus mit nur einer Multiplikation . Macht man das nacheinander für alle Glieder der Additionskette, so hat man mit Multiplikationen den Wert von erhalten. Dabei kann es sich bei der Basis um ein Element einer beliebigen nicht notwendig kommutativen Halbgruppe handeln; es muss also keine Zahl im üblichen Sinne sein. Besonders für endliche Strukturen bietet sich das an, z. B. die Multiplikation und Potenzierung modulo einer ganzen Zahl in Restklassenringen.

Die Frage, wie viele Multiplikationen man für eine Potenzierung mit einem natürlichen Exponenten mindestens braucht, ist 1894 in L'intermédiaire des mathématiciens von H. Dellac gestellt und im selben Jahr von Ernest de Jonquières beantwortet worden, der für einige Fälle die Lösung angab.[1]

Einen neuen Aufschwung hat das Problem durch die moderne Kryptographie genommen, wo bei einigen Verfahren hohe Potenzen ganzer Zahlen in Modulo-Arithmetik gebraucht werden. Dabei kann die Berechnung durch geeignete Additionsketten beschleunigt werden. Die optimale Lösung zu berechnen, also eine kürzeste Addtionskette für eine Zahl zu finden, hat sich dabei als sehr schwierig erwiesen. Für die Praxis spielt das eine geringe Rolle, da auch fast optimale Lösungen den Zweck erfüllen, aber als mathematische Herausforderung ist es bis heute ein schwieriges Problem trotz der einfachen Fragestellung.

Kürzeste Additionsketten[Bearbeiten | Quelltext bearbeiten]

2 1 1 1 1 1
3 2 2 2 2 1
4 1 2 2 2 1
5 2 3 3 3 2
6 2 3 3 3 2
7 3 4 4 4 5
8 1 3 3 3 1
9 2 4 4 4 3
10 2 4 4 4 4
11 3 5 5 5 15
12 2 4 4 4 3
13 3 5 5 5 10
14 3 5 5 5 14
15 4 5 5 6 4
16 1 4 4 4 1
17 2 5 5 5 2
18 2 5 5 5 7
19 3 6 6 6 33
20 2 5 5 5 6
21 3 6 6 6 29
22 3 6 6 6 40
23 4 6 6 7 4
24 2 5 5 5 4
25 3 6 6 6 14
26 3 6 6 6 24
27 4 6 6 7 5
28 3 6 6 6 23
29 4 7 6 7 132
30 4 6 6 7 12
31 5 7 7 8 77
32 1 5 5 5 1
53 4 8 7 8 205
57 4 8 7 8 173
58 4 8 7 8 352
71 4 9 8 9 1258
89 4 9 8 9 471
127 7 10 9 12 2661
191 7 11 10 13 9787
382 7 11 11 14 4
465 5 12 11 12 6352
1018 8 13 12 16 2677
1019 9 13 13 17 129
1020 8 12 12 16 240
1021 9 13 13 17 934
1022 9 13 13 17 3960
1023 10 13 13 18 1072
1024 1 10 10 10 1

Zu jeder natürlichen Zahl ab 4 gibt es mehrere Additionsketten, die diese als letztes Element enthalten. Interessant sind besonders kürzeste Ketten, die eine bestimmte Zahl erreichen. Die Zweierpotenzen und die 3 – und nur diese, wie sich zeigen lässt – haben nur eine kürzeste Additionskette.

Die meisten Zahlen (letztlich sogar fast alle, bezogen auf die richtige Wahl einer Dichte) lassen sich mittels einer Additionskette beschreiben, deren Länge in Abhängigkeit von der Zahl im Wesentlichen ist.

Eine vermutete und bisher bis bestätigte untere Schranke für ist , wobei die Anzahl der Einsen in der Binärdarstellung von ist. Das ist zugleich mindestens für kleine eine brauchbare Schätzung für : bis ist entweder oder , und bis ist mit nur einer Ausnahme .

Eine obere Schranke für ist , denn man kann zunächst die Kette aller Zweierpotenzen bis bilden und dann die übrigen in der Binärdarstellung von enthaltenen Zweierpotenzen durch Addition hinzufügen. Einige Beispiele von Werten dieser Funktionen sind in der Tabelle rechts aufgeführt, dazu die Anzahl kürzester Ketten für .

Für alle mit ist bekannt[2]:

  • Ist , so ist .
  • Ist , d. h. mit , so definieren wir und . Ist dann und gibt es eine kürzeste Additionskette für , in der vorkommt, so ergibt sich daraus eine Additionskette für der Länge . Das ist genau dann der Fall, wenn
    • (Beispiel: , Kette 1, 2, 4, 5, 10, 20, 40, 45 der Länge 7) oder
    • (Beispiel: , Kette 1, 2, 3, 5, 10, 20, 23 der Länge 6) oder
    • (Beispiel: , Kette 1, 2, 3, 6, 9, 18, 36, 72, 144, 147 der Länge 9).
  • Hat die Form , mithin , so ist 1, 2, …, 45, 90, 135, …, eine Kette der Länge .
  • In allen anderen Fällen mit ist .

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Frage 49 und Antwort dazu in L'intermédiaire des mathématiciens, Band 1 (1894), S. 20 und 162–164; Digitalisat online bei der SUB Göttingen
  2. Donald E. Knuth: The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, 2nd Ed. 1981, Addison-Wesley, ISBN 0-201-03822-6, Theorem C, S. 449