imported>T. Wirbitzki: lk digizeitschriften.de (Ersatz), https

2026-03-21T18:02:14Z

lk digizeitschriften.de (Ersatz), https

Neue Seite

Eine '''Additionskette''' für eine positive ganze Zahl <math>n</math> ist eine endliche [[Folge (Mathematik)|Folge]] positiver ganzer Zahlen, die mit 1 beginnt und mit <math>n</math> endet und bei der jede Zahl der Folge außer der 1 die Summe zweier nicht notwendig verschiedener vorangegangener Folgenglieder ist. Für fast alle Fragestellungen genügt es, [[Monoton steigende Folge|streng monoton steigende]] Folgen zu betrachten, so dass die Monotonie oft mit gefordert wird (siehe [[#Varianten der Definition|Varianten der Definition]]).

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. Ist <math>r</math> die Länge der Additionskette <math>(a_i)_{i=0,\cdots,r}</math> für <math>n</math>, so ist <math>a_0=1, a_1=2,\cdots, a_r=n</math>. Die minimale Länge aller Additionsketten für <math>n</math> wird mit <math>l(n)</math> 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.

<math>l(9)=4</math>, 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 ==
Die erste und bis heute wohl wichtigste Anwendung von Additionsketten ist die Optimierung der Berechnung von [[Potenz (Mathematik)|Potenzen]] mit großen [[Potenz (Mathematik)#Natürliche Exponenten|natürlichen Exponenten]]. Hat man eine Additionskette der Länge <math>r</math> für eine positive ganze Zahl <math>n</math>, so lässt sich zu einer Zahl <math>a</math> die Potenz <math>a^n</math> durch <math>r</math> Multiplikationen berechnen. Sind nämlich für ein Glied <math>x</math> der Additionskette, das Summe vorangegangener Glieder <math>y</math> und <math>z</math> ist, <math>a^y</math> und <math>a^z</math> schon berechnet worden, so ergibt sich <math>a^x</math> daraus mit nur ''einer'' Multiplikation <math>a^x=a^{y+z}=a^y\cdot a^z</math>. Macht man das nacheinander für alle Glieder der Additionskette, so hat man mit <math>r</math> Multiplikationen den Wert von <math>a^n</math> erhalten. Dabei kann es sich bei der Basis <math>a</math> 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 [[Restklassenring]]en.

Die Frage, wie viele Multiplikationen man für eine Potenzierung mit einem natürlichen Exponenten <math>n</math> mindestens braucht, ist 1894 in ''L'intermédiaire des mathématiciens'' von H. Dellac gestellt und im selben Jahr von [[Ernest Jean Philippe Fauque de Jonquières|Ernest de Jonquières]] beantwortet worden, der für einige Fälle die Lösung angab.<ref name="jonquieres">Frage 49 und Antwort dazu in ''L'intermédiaire des mathématiciens'', Band 1 (1894), S. 20 und 162–164; [https://gdz.sub.uni-goettingen.de/id/PPN599473517_0001 Digitalisat online] bei der SUB Göttingen</ref>

Einen neuen Aufschwung hat das Problem durch die moderne Kryptographie genommen, wo bei einigen Verfahren hohe Potenzen ganzer Zahlen in [[Restklassenring|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.

In kryptographischen Verfahren wie [[RSA-Kryptosystem|RSA]] ist der Exponent Teil des privaten Schlüssels. Da die Anzahl der Rechenschritte von der Anzahl der Einsen in der Binärdarstellung des Exponenten abhängt, könnte ein Angreifer durch genaue Zeitmessung Rückschlüsse auf die Anzahl der binären Einsen und damit auf den Exponenten selbst ziehen. Um diesen [[Seitenkanalangriff]] zu vereiteln, wird das Potenzieren üblicherweise mit einem Algorithmus durchgeführt, dessen Laufzeit unabhängig von Exponenten ist.

== Aufbau von Additionsketten ==
=== Varianten der Definition ===
Die eingangs angegebene Definition einer Additionskette ist die ursprüngliche<ref>{{Literatur |Autor=[[Arnold Scholz]] |Sammelwerk=[[Jahresbericht der Deutschen Mathematiker-Vereinigung]] |Band=47 |Titel=(Aufgabe 253) |Datum=1937 |Seiten=41–42 |ISSN=0012-0456 |Online=https://gdz.sub.uni-goettingen.de/id/PPN37721857X_0047}}</ref><ref>{{Literatur | Autor=[[Alfred Brauer]] | Sammelwerk=[[Bulletin of the American Mathematical Society]] | Band=45 | Titel=On Addition Chains | Datum=1939 | Seiten=736–739 | ISSN=0273-0979 | Sprache=en | Online=https://www.ams.org/journals/bull/1939-45-10/S0002-9904-1939-07068-7/S0002-9904-1939-07068-7.pdf }}</ref> und wird daher meist zugrunde gelegt. Bei ihr treten die Zahlen nicht notwendig in aufsteigender Reihenfolge auf; so sind etwa (1, 2, 3, 4, 8, '''11'''), (1, 2, 4, 3, 8, '''11''') und (1, 2, 4, 8, 3, '''11''') drei ''verschiedene'' Additionsketten, die dieselben Summen derselben Glieder enthalten und sich nur in der Reihenfolge der Summenbildungen unterscheiden. In aller Regel interessiert man sich aber für die Reihenfolge nicht, sondern betrachtet die drei Ketten als Varianten derselben Kette, genauer: als [[Äquivalenzrelation #Repräsentantensysteme|Repräsentanten]] derselben Äquivalenzklasse von Ketten. Diese ist dann allein durch die (ungeordnete) Menge der Glieder gegeben: Genau dann, wenn eine endliche Menge <math>A</math> positiver ganzer Zahlen die Menge der Kettenglieder einer Additionskette (also die Bildmenge der Folge) ist, gilt <math>1\in A</math> und <math>A\setminus \{1\}\subset \{x+y:x, y\in A\}</math>. Dann aber ist insbesondere die eindeutig bestimmte streng monoton steigende, ab 0 indizierte Folge der Elemente von <math>A</math> eine Additionskette für <math>n=\max A</math>. Es kann weitere Additionsketten für dieses <math>n</math> geben, die aus derselben Menge von Gliedern in anderer Reihenfolge bestehen; diese lassen sich aber leicht aus <math>A</math> konstruieren. Oft werden deshalb nur die streng monoton steigenden Additionsketten genauer untersucht, z. B. bei Knuth:<ref>{{Literatur | Autor=Donald E. Knuth | Titel=Arithmetik | Originaltitel=The Art of Computer Programming | Originalsprache=en | Übersetzer=R. Loos | Verlag=Springer | Ort=Berlin, Heidelberg u. a. | Datum=2001 | ISBN=3-540-66745-8 | Seiten=298}}<br/>Komplettes Zitat: „Wir können ohne Beschränkung der Allgemeinheit annehmen, dass eine Additionskette ''aufsteigend'' ist, <math>1=a_0<a_1<\cdots<a_r=n</math>. Denn wenn irgend zwei <math>a</math> gleich sind, kann eines von ihnen weggelassen werden; und wir können auch die Folge (1) in aufsteigender Ordnung neu arrangieren und Terme <math>>n</math> wegnehmen, ohne die Additionsketteneigenschaft (2) zu zerstören. ''Von jetzt an werden wir nur aufsteigende Ketten betrachten'', ohne diese Annahme explizit zu erwähnen.“</ref> „Wir können [[ohne Beschränkung der Allgemeinheit]] annehmen, dass eine Additionskette ''aufsteigend'' ist, […] ''Von jetzt an werden wir nur aufsteigende Ketten betrachten'', ohne diese Annahme explizit zu erwähnen.“

=== Aufzählung von Additionsketten ===
{| class="wikitable" style="float: left; margin-right: 1.3em"
! 0 !! 1 !! 2 !! 3 !! 4 !! 5 (nur für 15) !! 5 (nur für 11)
|-
|rowspan="6"| '''1'''
|rowspan="6"| 1, '''2'''
|rowspan="3"| 1, 2, '''3'''
|rowspan="1"| 1, 2, 3, 4
|| …, 5 | 6 | '''7''' | 8
||
|| …, 7, '''11''' | 8, '''11'''
|-
|rowspan="1"| 1, 2, 3, '''5'''
|| …, 6 | '''7''' | 8 | '''10'''
|| …, 10 , '''15'''
|| …, 6, '''11''' | 8, '''11''' | 10, '''11'''
|-
|rowspan="1"| 1, 2, 3, '''6'''
|| …, '''7''' | 8 | '''9''' | '''12'''
|| …, 9, '''15''' | 12, '''15'''
|| …, 8, '''11''' | 9, '''11'''
|-
|rowspan="3"| 1, 2, '''4'''
|rowspan="1"| 1, 2, 4, '''5'''
|| …, 6 | '''7''' | 8 | '''9''' | '''10'''
|| …, 10, '''15'''
|| …, 6, '''11''' | 7, '''11''' | 9, '''11''' | 10, '''11'''
|-
|rowspan="1"| 1, 2, 4, '''6'''
|| …, '''7''' | 8 | '''10''' | '''12'''
||
|| …, 7, '''11''' | 10, '''11'''
|-
|rowspan="1"| 1, 2, 4, '''8'''
|| …, '''9''' | '''10''' | '''12''' | '''16'''
||
|| …, 9, '''11''' | 10, '''11'''
|}
In dieser Tabelle stehen alle Additionsketten der Länge bis 4 sowie eine Auswahl der insgesamt 135 Ketten der Länge 5, nämlich diejenigen, deren Endglied entweder 15 oder 11 ist. Der senkrechte Strich „|“ trennt alternative Teilketten. Das Auslassungszeichen „…“ bedeutet immer die Kette der Länge 3 in derselben Tabellenzeile. Die Endglieder sind fettgedruckt, wo sie in einer kürzesten Kette für diese Zahl erscheinen.

Auf diese Weise kann man im Prinzip alle Additionsketten aufzählen und erhält damit zu jeder Zahl eine kürzeste, alle kürzesten oder auch alle überhaupt. Ohne weiteres praktikabel ist dieses Verfahren aber nur für kleine Zahlen: Bereits mit der Länge 10 gibt es über 10 Millionen<ref>{{OEIS|A008933}}</ref> verschiedene Additionsketten, und ihre Zahl wächst rasch weiter.

Die Anfangsabschnitte einer kürzesten Kette sind nicht notwendig selbst kürzeste Ketten für ihr jeweiliges Endglied. So beginnen die Ketten für 7 und 11 in der obersten Tabellenzeile mit (1, 2, 3, 4), was keine kürzeste Kette ist. Es genügt also nicht, bei der Konstruktion von kürzesten Ketten für ein <math>n</math> nur die kürzesten Ketten für die Zahlen <math><n</math> heranzuziehen.

== Kürzeste Additionsketten ==
{| class="wikitable" style="float:right; text-align:right; margin-left:1.5em"
! <math>n</math> !! <math>\nu(n)</math> !! <math>l(n)</math> !! <math>g(n)</math> !! <math>b(n)</math> !! <math>\Lambda(n)</math>
|-
| 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ürliche Zahl|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 [[Zweierpotenz]]en und die 3 – und nur diese, wie sich zeigen lässt – haben nur ''eine'' kürzeste Additionskette. Die 6 sowie alle Zahlen außer 9, die um 1 größer sind als eine Zweierpotenz ab 4, haben genau zwei kürzeste Additionsketten, z. B. 1, 2, 4, 8, 16, (17 oder 32), '''33'''.

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 <math>n</math> im Wesentlichen <math>\log_2 (n) + \frac{\log_2 (n)}{\log_2(\log_2(n))}</math> ist.

Eine vermutete und bisher bis <math>n=2^{64}</math> bestätigte untere Schranke für <math>l(n)</math> ist
<math>g(n) = \lfloor\log_2(n)\rfloor + \lceil\log_2(\nu(n))\rceil</math>, wobei <math>\nu(n)</math> die Anzahl der Einsen in der [[Dualsystem|Binärdarstellung]] von <math>n</math> ist. Das ist zugleich mindestens für kleine <math>n</math> eine brauchbare Schätzung für <math>l(n)</math>: bis <math>n=3690</math> ist <math>l(n)</math> entweder <math>g(n)</math> oder <math>g(n)+1</math>, und bis <math>n=2^{31}</math> ist mit nur ''einer'' Ausnahme <math>0\leqq l(n)-g(n)\leqq 3</math>. Die Ausnahme ist <math>n=2135101487\approx 0.994\cdot 2^{31}</math> mit <math>\nu(n)=16</math>, <math>g(n)=34</math>, <math> l(n)=38</math>.

Eine obere Schranke für <math>l(n)</math> ist <math>b(n) = \lfloor\log_2(n)\rfloor + \nu(n) - 1</math>, denn man kann zunächst die Kette aller Zweierpotenzen <math>\leqq n</math> bilden und dann die übrigen <math>\nu(n)-1</math> in der Binärdarstellung von <math>n</math> enthaltenen Zweierpotenzen durch Addition hinzufügen. Einige Beispiele von Werten dieser Funktionen sind in der Tabelle rechts aufgeführt, dazu die Anzahl <math>\Lambda(n)</math> kürzester Ketten für <math>n</math>.

Für alle <math>n</math> mit <math>\nu(n)<5</math> ist <math>l(n)</math> bekannt<ref>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</ref>:
* Ist <math>\nu(n)<4</math>, so ist <math>l(n)=b(n)=g(n)</math>.
* Ist <math>\nu(n)=4</math>, d. h. <math>n=2^p+2^q+2^r+2^s</math> mit <math>p>q>r>s</math>, so definieren wir <math>c=2^{p-q}+1</math> und <math>d=2^{r-s}+1</math>. Ist dann <math>c\geqq d</math> und gibt es eine kürzeste Additionskette für <math>c</math>, in der <math>d</math> vorkommt, so ergibt sich daraus eine Additionskette für <math>n</math> der Länge <math>l(n)=p+2=g(n)=b(n)-1</math>. Das ist genau dann der Fall, wenn
** <math>c=d</math> (Beispiel: <math>n=45, c=d=5</math>, Kette 1, 2, 4, 5, 10, 20, 40, '''45''' der Länge 7) oder
** <math>c=2d-1</math> (Beispiel: <math>n=23, c=5, d=3</math>, Kette 1, 2, 3, 5, 10, 20, '''23''' der Länge 6) oder
** <math>c=9, d=3</math> (Beispiel: <math>n=147</math>, Kette 1, 2, 3, 6, 9, 18, 36, 72, 144, '''147''' der Länge 9).
* Hat <math>n</math> die Form <math>135\cdot 2^k</math>, mithin <math>\nu(n)=4</math>, so ist 1, 2, …, 45, 90, 135, …, <math>\boldsymbol{n}</math> eine Kette der Länge <math>l(n)=k+9=g(n)=b(n)-1</math>.
* In allen anderen Fällen mit <math>\nu(n)=4</math> ist <math>l(n)=b(n)=g(n)+1</math>.

== Weblinks ==
* [https://wwwhomes.uni-bielefeld.de/achim/addition_chain.html Shortest Addition Chains] Ergebnisse und Literaturverweise zusammengestellt von Achim Flammenkamp
* [https://oeis.org/ Online-Encyclopedia of Integer Sequences], insbesondere Folgen [https://oeis.org/A003313 A003313] und [https://oeis.org/A079300 A079300]

== Einzelnachweise ==
<references/>

{{Absatz}}
[[Kategorie:Theoretische Informatik]]

Additionskette - Versionsgeschichte

imported>T. Wirbitzki: lk digizeitschriften.de (Ersatz), https