Addition chain

An addition chain for a positive integer is a finite, strictly monotonically increasing sequence of positive integers that begins with 1 and ends with and in which every number in the sequence except 1 is the sum of two not necessarily different preceding elements of the sequence. The length of an addition chain is the number of elements in the sequence, which is the sum of previous elements in the sequence - the 1 at the beginning is not counted. The minimum length of all addition chains for is denoted by. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle l(n)}$

Example:

• 1, 2, 4, 5, 9 is an addition chain of length 4 for 9, because 2 = 1 + 1, 4 = 2 + 2, 5 = 4 + 1 and 9 = 5 + 4.
• 1, 2, 4, 6, 9 is not an addition chain for 9, because 9 is not the sum of two preceding parts of the sequence.

${\displaystyle l(9)=4}$, because there is no shorter addition chain for 9. Other addition chains for 9 are the same length (two more) or longer.

Application and history

The first and to this day probably the most important application of addition chains is the optimization of the calculation of powers with large natural exponents . If you have an addition chain of length for a positive whole number , the power of a number can be calculated by multiplication. If, for a member of the addition chain, the sum of previous members and is, and has already been calculated, this results with only one multiplication . If you do this one after the other for all links in the addition chain, you have obtained the value of with multiplications . The base can be an element of any non-commutative semigroup ; it doesn't have to be a number in the usual sense. This is particularly useful for finite structures, e.g. B. the multiplication and exponentiation modulo an integer in remainder class rings . ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle a^{n}}$ ${\displaystyle r}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle a^{y}}$ ${\displaystyle a^{z}}$ ${\displaystyle a^{x}}$ ${\displaystyle a^{x}=a^{y+z}=a^{y}\cdot a^{z}}$ ${\displaystyle r}$ ${\displaystyle a^{n}}$ ${\displaystyle a}$

The question of how many multiplications one needs to raise to a natural exponent at least was asked by H. Dellac in L'intermédiaire des mathématiciens in 1894 and answered in the same year by Ernest de Jonquières , who gave the solution for some cases. ${\displaystyle n}$

The problem has taken on a new impetus through modern cryptography, where high powers of integers in modulo arithmetic are required for some methods . The calculation can be accelerated by suitable addition chains. The optimal compute solution, so to find a shortest Addtionskette for a number, has proven to be very difficult. In practice this plays a minor role, since almost optimal solutions also serve the purpose, but as a mathematical challenge it is still a difficult problem despite the simple question.

Shortest addition chains

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

For every natural number from 4 there are several addition chains that contain this as the last element. The shortest chains that reach a certain number are particularly interesting. The powers of two and the 3 - and only these, as can be shown - have only a shortest chain of addition. The 6 and all numbers except 9, which are 1 larger than a power of two from 4, have exactly two shortest addition chains, e.g. B. 1, 2, 4, 8, 16, (17 or 32), 33 .

Most numbers (ultimately almost all, based on the correct choice of density) can be described by means of an addition chain, the length of which is essentially dependent on the number . ${\displaystyle n}$ ${\displaystyle \log _{2}(n)+{\frac {\log _{2}(n)}{\log _{2}(\log _{2}(n))}}}$

A presumed and so far confirmed lower bound for is , where the number of ones in the binary representation of is. At the same time, at least for small ones, this is a useful estimate for : until is either or , and until is with only one exception . The exception is with , , . ${\displaystyle n=2^{64}}$ ${\displaystyle l(n)}$ ${\displaystyle g(n)=\lfloor \log _{2}(n)\rfloor +\lceil \log _{2}(\nu (n))\rceil }$ ${\displaystyle \nu (n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle l(n)}$ ${\displaystyle n=3690}$ ${\displaystyle l(n)}$ ${\displaystyle g(n)}$ ${\displaystyle g(n)+1}$ ${\displaystyle n=2^{31}}$ ${\displaystyle 0\leqq l(n)-g(n)\leqq 3}$ ${\displaystyle n=2135101487\approx 0.994\cdot 2^{31}}$ ${\displaystyle \nu (n)=16}$ ${\displaystyle g(n)=34}$ ${\displaystyle l(n)=38}$

An upper bound for is , because you can first build the chain of all powers of two and then add the remaining powers of two in the binary representation of contained powers of two. Some examples of values ​​for these functions are given in the table on the right, plus the number of shortest strings for . ${\displaystyle l(n)}$ ${\displaystyle b(n)=\lfloor \log _{2}(n)\rfloor +\nu (n)-1}$ ${\displaystyle \leqq n}$ ${\displaystyle \nu (n)-1}$ ${\displaystyle n}$ ${\displaystyle \Lambda (n)}$ ${\displaystyle n}$

For everyone with is known: ${\displaystyle n}$ ${\displaystyle \nu (n)<5}$ ${\displaystyle l(n)}$

• Is so is . ${\displaystyle \nu (n)<4}$ ${\displaystyle l(n)=b(n)=g(n)}$
• Is , d. H. with , that's how we define and . If then and there is a shortest addition chain for in which occurs, this results in an addition chain for the length . This is exactly the case when ${\displaystyle \nu (n)=4}$ ${\displaystyle n=2^{p}+2^{q}+2^{r}+2^{s}}$ ${\displaystyle p>q>r>s}$ ${\displaystyle c=2^{p-q}+1}$ ${\displaystyle d=2^{r-s}+1}$ ${\displaystyle c\geqq d}$ ${\displaystyle c}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle l(n)=p+2=g(n)=b(n)-1}$
  • ${\displaystyle c=d}$(Example :, chain 1, 2, 4, 5, 10, 20, 40, 45 of length 7) or ${\displaystyle n=45,c=d=5}$
  • ${\displaystyle c=2d-1}$(Example :, chain 1, 2, 3, 5, 10, 20, 23 of length 6) or ${\displaystyle n=23,c=5,d=3}$
  • ${\displaystyle c=9,d=3}$(Example :, chain 1, 2, 3, 6, 9, 18, 36, 72, 144, 147 of length 9). ${\displaystyle n=147}$
• If it has the form , then 1, 2,…, 45, 90, 135,… is a chain of length . ${\displaystyle n}$ ${\displaystyle 135\cdot 2^{k}}$ ${\displaystyle \nu (n)=4}$ ${\displaystyle {\boldsymbol {n}}}$ ${\displaystyle l(n)=k+9=g(n)=b(n)-1}$
• In all other cases with is . ${\displaystyle \nu (n)=4}$ ${\displaystyle l(n)=b(n)=g(n)+1}$

Web links

• Shortest Addition Chains Results and literature references compiled by Achim Flammenkamp
• Online Encyclopedia of Integer Sequences , especially episodes A003313 and A079300

Individual evidence

1. ↑ Question 49 and the answer to it in L'intermédiaire des mathématiciens , Volume 1 (1894), pp. 20 and 162–164; Digitalization online at SUB Goettingen
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, p. 449