# Shortest Addition Chains

## Introduction

A finite sequence of positive integers a0, a1, ..., ar is called an addition chain iff for each element ai, but the first a0 which equals 1, there exist elements in the sequence with smaller indices j and k such that ai = aj + ak.
Preciser this is called an addition chain of length r for its last number ar. It can be interpreted like calculating n = ar starting from 1 by addition of only previous calculated numbers. Let us restrict the definition a bit more: addition chains should be strictly monotonic increasing. This can be achived by reordering and dropping multiple numbers. As a consequence a1=2 and a2=3 or 4 always (as long as r > 1). Now ask for the minimal length of an addition chain for a given number n and call this value l(n). If we demand that j or k equals i-1 for all positive indices i -- each ai in the chain requires the previous ai-1, we call such a chain a star-chain and denote its minimal length by l*(n).
I highly recommand Knuth's survey in section 4.6.3 of The Art of Computer Programming, Volume 2: Seminumerical Algorithmus (3. edition appeared 1997). To illustrate shortest addition chains for each n < 149 one may track the path from the root 1 to the corresponding node n in the following tree: Such a tree can't be extended gapless to larger n because in the triple 43, 77, 149 any two numbers exclude the third for a shortest addition chain representation in a common tree.

## Lower and Upper Bounds of l(n)

Write n in its binary representation and denote by v(n) the number of ones in this representation and by λ(n) the binary logarithm of n rounded to the next integer down in the case it is not already integer (floor-function). Then it is obvious through construction of an addition chain according by the russian multiplication, that l(n) <= λ(n) + v(n) - 1. An open conjecture states a lower limit of λ(n) + log2(v(n)).

## Notation

Notice: The definitions of v(n) and λ(n) are given in the previous paragraph.
s(n)
the number of small steps of n defined as the difference of the length of its shortest addition chain and the binary logarithm (rounded down).
s(n) = l(n)-λ(n)
Double step
ai = ai-1 + ai-1
Star step
ai = ai-1 + aj with j < i
Small step
λ(ai) = λ(ai-1)
Standard step
ai = aj + ak with i > j > k

L(r)
the set of numbers which have a shortest addition chain of length r
L(r) = { i: l(i)=r }
c(r)
the smallest number which has a shortest addition chain of length r
c(r) = min L(r)
2r
the largest number which has an addition chain of length r
2^r = max L(r) holds trivally
m(r)
the median of numbers which have a shortest addition chain of length r
m(r) = med L(r)
μ(r)
the arithemtic average of numbers which have a shortest addition chain of length r
μ(r) = 1/d(r) ∑i ∈ L(r) i
g(r)
the geometric average of numbers which have a shortest addition chain of length r
g(r) = exp( 1/d(r) ∑i ∈ L(r) ln i )
p(r)
the "most probable" number which has a shortest addition chain of length r
p(r) = i: fr(i) = maxh fr(h) with fr(i) = ∑k ∈ N |{ j ∈ L(r): |i-j|=k }|/4k
σ(r)
the standard deviation of the numbers which have a shortest addition chain of length r
σ2(r) = 1/d(r) ∑i ∈ L(r) i2 - μ(r)2
d(r)
the number of numbers which have a shortest addition chain of length r
d(r) = | L(r) |

## Table of Characterizing Values

r c(r) s(c(r))v(c(r)) μ(r) g(r) m(r)p(r)σ(r) d(r) L(r)
0 1 0 1 1.0 1.0 1= 10 1{1}
1 2 0 1 2.0 2.0 2= 20 1{2}
2 3 1 2 3.5 3.5 3+ 3+0.5 2{3,4}
3 5 1 2 6.3 6.2 6= 61.2 3{5,6,8}
4 7 2 3 10.8 10.4 10= 103.1 5{7,9,10,12,16}
5 11 2 3 18.2 17.3 17= 146.1 9{11,13,14,15,17,18,20,24,32}
6 19 2 3 31.7 30.1 28= 2611.4 15{19,21,22,23,25,26,27,28,30,33,34,36,40,48,64}
7 29 3 4 54.5 51.3 49+ 43 21.2 26
8 47 3 5 94.6 88.5 84+ 84 39.0 44
9 71 3 4 162.4 151.0 147+ 116 70.5 78
10 127 4 7 283.1 262.8 248+ 230 125.6 136
11 191 4 7 491.5 456.1 435+ 455 220.8 246
12 379 4 7 869.8 809.4 781+ 840 387.5 432
13 607 4 7 1535.4 1429.4 1372+ 1136 682.3 772
14 1087 4 7 2725.8 2540.0 2461+ 2028 1201.5 1382
15 1903 5 9 4855.4 4527.9 4379= 4047 2122.4 2481
16 3583 5 11 8672.1 8097.2 7813+ 6832 3748.3 4490
17 6271 5 9 15571.7 14570.0 14101+ 12048 6611.3 8170
18 11231 5 11 28094.6 26343.0 25641+ 24096 11694.2 14866
19 18287 5 10 50861.7 47784.4 46466+ 48156 20748.0 27128
20 34303 5 11 92379.2 86937.2 84764+ 89120 36960.6 49544
21 65131 6 12 168192.7 158468.7 154745= 146480 66224.1 90371
22 110591 6 15 306531.6 289025.3 282128+ 290858 119165.8 165432
23 196591 6 16 559476.7 527913.7 514285= 520240 215048.9 303475
24 357887 6 15 1023051.3 966288.1 942710= 1155126 388500.7 558275
25 685951 6 15 1874869.11772876.31732716+ 2310196 702737.4 1028508
26 1176431 6 14 3443135.03259501.83191985+ 2801503 1273563.8 1896704
27 2211837 6 16 6333417.26001516.05881151= 5612462 2313684.8 3501029
28 4169527 7 17 11667084.111064752.410848521+ 9412704 4214352.7 6465774
29 7624319 7 15 21516285.220418193.420044424+ 16905070 7697737.3 11947258
30 14143037 7 16 39714338.937704137.937013874= 41615456 14098404.4 22087489
31 25450463 7 15 73345796.769658962.368327129+ 83230816 25868797.8 40886910
32 46444543 7 18 135563778.8128804664.5126581547+ 132022368 47516034.6 75763102
33 89209343 7 18 250780403.3238406628.4234114742=28495063587306216.3140588339
34 155691199 7 16 464437430.0441801858.5434295820+397507456160480247.6261070184
35 298695487 7 19 861008497.3819556624.5806226456+680509066295231415.9485074788
36 550040063 7 17 1597540092.51521468390.11497772469+1511488768543803959.0901751654
37 994660991 8 18 1677060520
38 1886023151 8 19 3119775195
39 3502562143 8 18 5804404206
40 6490123999 8 21 10804952217
41 11889505663 8 21
42 22899028607 8 21
43 41866170239 8 25

In the median column the sign = means the value is unique and the character + indicates it lies between the given index and the next index with this r-value because d(r) is even.
With bold font in the previous c(r)-column the sequence of smallest numbers ni is high-lighted which need at least i= s(c(r)) small steps in their addition chain: 1,3,7,29,127,1903,65131,4169527,994660991,....
Moreover here are the graphs of c(r) and d(r) together with an approximation function plotted. And the quotient of c(r) and d(r) with the asymptotic approximation function. Finally the distribution of the number of shortest addition chains with fixed small step number depending on the range of λ(n).

## Generally Solved Small Step Cases

0-small-step case
Trivial
• ```For each n >= 0 there is exactly 1 0-small-step number in the half-open interval [2^n,2^(n+1)[ .
```
• list of all 0-small-step numbers:
`2^n`
• shortest chains for 0-small-step numbers:
```   0(     )  1
1( 0, D)  @(A)

Here @(A)  means 2^A  with A a free nonnegative integer variable
```
1-small-step case
<= 1894 solved
2-small-step case
<= 1957 solved
3-small-step case
1991 solved

## History: What was calculated When and by Whom

• l(i) with i <= 50 or v(i) <=4 , and d(r) with r <=6
calculated March 1957 by W. Hansen
• l(i) with i <= 210 and d(r) with r <=11
reported December 1963 by D. E. Knuth
• l(i) with i < 2000 and d(r) with r <= 12
reported October 1968 by D. E. Knuth
• l(i) with i < 11232 and d(r) with r <= 15
calculated until May 1973 by D. E. Knuth
• l(i) with i < 120000 and c(r) with r <= 22
computed until August 1988 by Achim
• l(i) with i < 217 and d(r) with r <= 20
computed April 1991 by Achim
• l(i) with i < 218 and d(21) and c(23)
computed until October 1991 by Achim
• l(i) with i <= 500000 and c(24)
computed until November 1995 by D. Bleichensbacher
• l(i) with i <= 720000 including c(25)
computed until end of March 1997 by Achim.
• l(i) with i <= 222 including c(28) and d(r) with r <= 25
computed until August 1997 by Achim.
• l(i) with i <= 222 and d(25) and d(26)
computed until August 2004 by Neill Clift
• l(i) with i <= 223 and d(27) and c(29) and c(30)
computed until September 2004 by Neill Clift
• l(i) with i <= 224
computed until December 2004 by Neill Clift
• c(31)
computed December 2005 by Neill Clift
• l(i) with i <= 225
computed until April 2006 by Neill Clift
• d(29), d(30) and c(32)
computed until June 2007 by Neill Clift
• l(229-1) = 29 + l(29) - 1
proved in December 2007 by Neill Clift
• l(i) with i <= 226
computed until May 2008 by Neill Clift
• d(31), d(32) and c(33)
computed until May 2008 by Neill Clift
• l(i) with i <= 227 and l(i) with i <= 228 and l(i) with i <= 229
computed in May 2008 by Neill Clift
• d(33), c(34) and c(35)
computed in May 2008 by Neill Clift
• l(2n-1) = n + l(n) - 1, with n{31,33,...,46,48,49,50,51,52,54,56,60}
proved in May 2008 by Neill Clift
• c(36), d(34) and d(35)
computed June 2008 by Neill Clift
• c(37) and l(i) with i <= 230
computed until July 2008 by Neill Clift
• d(36)
computed in July 2008 by Neill Clift
• c(38)
computed in July 2008 by Neill Clift
• l(i) with i <= 231
computed until August 2008 by Neill Clift
• d(37)
computed in August 2008 by Neill Clift
• c(39)
computed in September 2008 by Neill Clift
• l(i) with i <= 232
computed until October 2008 by Neill Clift
• l(2n-1) = n + l(n) - 1 with n{64,47}
proved in October 2008 by Neill Clift
• d(36), d(37) and d(38)
computed in November 2008 by Neill Clift
• l(2n-1) = n + l(n) - 1 with n{53,55}
proved in November 2008 by Neill Clift
• l(2n-1) = n + l(n) - 1 with n{57}
proved in December 2008 by Neill Clift
• l(2n-1) = n + l(n) - 1 with n{58,59}
proved in January 2009 by Neill Clift
• l(2n-1) = n + l(n) - 1 with n{61}
proved in February 2009 by Neill Clift
• l(2n-1) = n + l(n) - 1 with n{62,63}
proved until May 2009 by Neill Clift
• c(40)
computed in September 2009 by Neill Clift
• l(i) with i <= 233
computed until October 2009 by Neill Clift
• c(41)
computed in November 2009 by Neill Clift
• l(i) with i <= 234
computed until December 2009 by Neill Clift
• c(42)
computed in May 2016 by Neill Clift
• l(2n-1) = n + l(n) - 1 with n{65,66,68,72,80,96}
proved in May 2016 by Neill Clift
• l(i) with i <= 235
computed until May 2016 by Neill Clift
• d(39)
computed in May 2016 by Neill Clift
• d(40)
computed in May 2016 by Neill Clift
• c(43)
computed in September 2016 by Neill Clift
• l(i) with i <= 236
computed until October 2016 by Neill Clift
• l(2n-1) = n + l(n) - 1, if l(n) <= 8
computed in July 2018 by Neill Clift
In July 2004 the data calculated 1997 by Flammenkamp was completely and independently checked. Hereby Neill Clift uncovered four l(n)-errors, which he attributed to a typo in Flammenkamp's program effecting only n-values > 2500000.
On 30th May 2008, Neill Clift discovered the first and smallest n such that l(n) > l(2n).

## Data Access

Thanks to Neill Clift's computations you can download the lengths of all shortest additions chains for n up to n=231 as bziped2 binary data of 210 MB size. The uncompressed values are coded as l(n)-λ(n)-ceil(log2(v(n))) into 2 bits each which the exception of l(2135101487) #. To decipher this you can download ddt.c compile it and run it as ddt inputfile linelength. You will get all values starting from 1 and broken into lines each containing linelength values onto your stdout from the base-36 alphabet (0,1,2,..,9,a,b,c,..,z) or as a 1 or 2 digit decimal value. A second helper l.c outputs l(n), λ(n), s(n) and v(n) for each given input n which data is in the datafile.
Now you can download all l(n) with n <= 233 as bziped2 binary data of 820 MB size. To display these you must also download ddt4l.c, compile it and run it as ddt4l datafile [first n [total number [linelength] ] ]. You will get all or total number-many values starting from 1 or first n and broken into lines each containing linelength values onto your stdout from the base-42 alphabet (0,1,2,..,9,a,b,c,..,z,A,B,C,..,F).
Now you can download all l(n) with n <= 235 as bziped2 binary data of 3197 MB size. To display these you must also download ddt4ln.c, compile it and run it as ddt4ln datafile [-O?] [first n [total number [linelength] ] ]. You will get all or total number-many values starting from 1 or first n and broken into lines (or pages) each containing linelength values onto your stdout. This ? after the -O controls the output format and must take values ∈ {0,1,2,3,4}. The default is 0 and means no output, but data integrity check only. Thus in generally you will need this output-option. The options -O1 and -O2 are the old formats known from ddt and ddtl4.The parameter -O4 produces a format very similar to this of the above old helper-program l.
Now you can download all l(n) with n <= 236 as bziped2 binary data of 6397 MB size. To display these you must also use ddt4ln.c like in the case of the 235-many values.

Look up in the database of the first 231 many l(n) values

starting from index the following values
Table Raw

The effort to compute these values up to n=220 is here visible. The number of cases checked to get l(n) is plotted in red against λ(n) for each number 28 <= n < 220. In blue the number of cases are marked to compute n=c(r) and finally in dark green the average number of cases is drawn which is needed to calculate l(n) for all numbers from 1 up to n (the last gives a good estimate of the average run time of the algorithm).

Generate a Shortest Addition Chain for any given number < 227

n= fast difficult

# The smallest n such that l(n)-λ(n)-ceil(log2(v(n))) equals 0,1,2,3,4,... are 1, 29, 3691, 919627, 2135101487, ... . For every n with l(n) <=22 the number of shortest addition chains as a gziped ASCII-file of 1.8 MB size, as a sorted by n list which consists of three columns. In each row of this list are given the values for the corresponding n, l(n) and number of shortest addition chains for this n.

## Conjectures

l(2n-1) <= n + l(n) - 1
The outstanding Scholz-Brauer-Conjecture of 1937. If l(n) is achievable by a star chain then it holds. Therefore only values of n need to be considered with l(n) < l*(n). But the smallest of these numbers is 12509. In August 2005 Clift reported to have confirmed the Scholz-Brauer inequality for all n < 5784689. +
l(2n-1) = n + l(n) - 1
This narrow related equation is proved to hold at least for all n with l(n) <= 8  *.
l(n) >= λ(n)+log2(v(n))
This famous lower bound was formulated first a bit differently by Stolarsky 1969 (p. 680, Lemma 10) and nearly proved 1974 by Schönhage who showed that l(n) >= log2(n)+log2(v(n))-2.123164629... holds for each n. Thurber showed 1973 that it holds for all n with v(n) <= 16. In October 2008 Clift confirmed the conjecture for all n <= 264.
log2(c(r)) ~ r - r/log2r
That is the 1997 stated conjecture by Flammenkamp for the asymptotic growth of c(r) outdating the 1991 given assertation that log2(c(r)) ~ r - 2log2r.
Computing l(n) for given n is NP-hard.
Downey, Leony and Sethi didn't prove anything about this statement in their 1981 SIAM article. They proved a similar one, if a set of numbers is given! Many people (and even experts) overlooked this important difference!
d(r) <= d(r+1) <= 2d(r)
Already 1981 D. Knuth stated "there is no evident way to prove that d(r) is an increasing function in r".
+This number 5784689 = 222+97*214+65*24+97 is also the smallest Non-Hansen number (also identified by Neill Clift in 2005 as such).
*In August 2005 Neill Clift reported to have proved equality without any further assumption for all n <= 28 and n = 30. Furthermore in December 2007 he showed equality without any further assumption even for n = 29. Moreover until May 2009 he proved it for all n <= 64 and in May 2016 for n ∈ {65,66,68,72,80,96}. Lastly in July 2018 he proved the equality with a new ground-breaking algorithm to hold for all n with l(n) <= 8.

## Unsorted new stuff

• An equivalent definition of addition chains based only on the set-theoretic definition of natural numbers: additive complexity
• K. Stolarsky uses infinite addition chains in his 1969 appeared paper. Here are some basic remarks about minimal infinite addition chains.
• Is there a hiden connection between finite topologic spaces and addition chains? Look here.

## References

• # H. Dellac
"Question 49",
L'Intermédiaire des Mathématiciens, V. 1

1894 p. 20.
• # E. de Jonquiéres
"Question 49 (H. Dellac)",
L'Intermédiaire des Mathématiciens V. 1

1894 20, pp 162-164.
• # A. Goulard
"Question 393",
L'Intermédiaire des Mathématiciens V. 1

1894 p. 234.
• # E. de Jonquiéres
"Question 393 (A. Goulard)",
L'Intermédiaire des Mathématiciens V. 2

1895 pp 125-126.
• # B. Datta and A.N. Singh
History of Hindu Mathematics V. 1
Bombay 1935, p. 76.
• # A. Scholz
"Aufgabe 253",
Jahresbericht der deutschen Mathematiker-Vereingung V. 47, 2. Abteil.

1937 pp 41-42.
• # A.T. Brauer
"On addition chains",
Bulletin of the American Mathematical Society V. 45

1939 pp 736-739.
• # W.R. Utz
"A note on the Scholz-Brauer problem in addition chains",
Proceedings of the American Mathematical Society, V. 4(3)

1953 pp 462-463.
• # S.M. Hendley
"The theory and construction of addition chains",
Masters Thesis, University of South Carolina, 1954.
• # W. Hansen
"Untersuchungen über die Scholz-Brauerschen Additionsketten und deren Verallgemeinerung",
Göttingen, Wiss. Prüfungsamt, Schriftl. Hausarbeit zum Staatsexamen 1957.
• # W. Hansen
"Zum Scholz-Brauerschen Problem",
Journal für reine und angewandte Mathematik, V. 202

1959 pp 129-136.
• # P.E. Valskii
"On the Lower Bounds of Multiplications in Evaluation of Powers",
Problems of Cybernetics, V. 2

1959 pp 73-74.
• # P. Erdös
"Remarks on number theory. III: On addition chains",
Acta Arith. V. 6(1)

1960 pp 77-81.
• # P.E. Valskii,
"The Smallest Number of Multiplications Necessary to Raise a Number to a Given Power",
Problems of Cybernetics V. 2

1961 pp 395-397.
• # A.A. Gioia, M.V. Subbarao and M. Sugunamma
"The Scholz-Brauer Problem in Addition Chains",
Duke Mathematical Journal, V. 29

1962 pp 481-487.
• # R.E. Bellman
"Advanced problem 5125",
Amer. Math. Monthly, V. 70 1963 p. 765.
• # D.E. Knuth
"Addition chains and the evaluation of n-th powers",
Notices of the American Mathematical Society, V. 11

1964 pp 230-231.
• # E.G. Strauss
"Solution to Problem 5125",
Am. Math. Monthly, V. 71

1964 pp. 806-808.
• # C.T. Whyburn
"A Note on Addition Chains",
Proceedings of the Am. Math. Society V. 16(5)

1965 p. 1134.
• # A.M. Il'in
"On Additive Number Chains",
Problemy Kibernet, V. 13

1965 pp 245-248.
• # C.A. Demetriou
"Concerning minimal addition chains",
Thesis (Master Science),
University of Mississippi, 1967.
• # E. Wattel, G.A. Jensen
"Efficient calculation of powers in a semigroup",
Stichting Mathematisch Centrum. Zuivere Wiskunde, Report ZW1968-001 Mathematical Centre Amsterdam, V. 1 pp 1-18.
• # D.E. Knuth
The Art of Computer Programming V. 2 Seminumerical Algorithms, 1. edition,
Addison-Wesly 1969 pp 449-450.
• # D.E. Knuth
"Calculations on Addition chains",
Stanford University, California 1969.
• # K. B. Stolarsky
"A lower bound for the Scholz-Brauer problem",
Canadian Journal of Mathematics, V. 21

1969 pp 675-683.
• # H. Kato
"On Addition Chains",
Ph. D. Thesis,
University of Southern California, 1970.
• # E.G. Thurber
"The Scholz-Brauer Problem for Addition Chains",
Ph.D. Thesis,
University of Southern California, 1971.
• # E. G. Thurber
"The Scholz-Brauer Problem on Addition Chains",
Notices of the American Mathematical Society, Abstract 71T-A274, V. 18

1971 p. 1100.
• # R.P. Giese
"A Sequence of Counterexamples of Knuth's Modification of Utz's Conjecture",
Notices of the American Mathematical Society, Abstract 72T-A257, V. 19

1972 p. A-688.
• # A. Cottrell
"A Lower Bound for the Scholz-Brauer Problem",
Notices of the American Mathematical Society, V. 20(5)

1973 p. A-476.
• # E.G. Thurber
"The Scholz-Brauer Problem on Addition-Chains",
Pacific Journal of Mathematics, V. 49(1)

1973 p. 229-242.
• # E.G. Thurber
"On addition chains l(mn) <= l(n)-b And lower bounds for c(r)",
Duke Mathematical Journal, V. 40(4)

1973 p. 907-913.
• # E. G. Thurber
"The Scholz-Brauer Problem on Addition Chains",
Notices of the American Mathematical Society, Abstract 73T-A112, V. 20

1973 p. A-318.
• # A. Cottrell
"A Lower Bound for the Scholz-Brauer Problem",
Ph.D. Thesis,
University of California, Berkeley, 1974.
• # R.P. Giese
"Selected Topics in Addition Chains",
Ph.D. Thesis,
University of Houston, 1974.
• # K. R. Hebb
"Some Problems on Addition Chains",
Master Thesis,
University of Alberta, 1974.
• # K. R. Hebb
"Some results on addition chains",
Notices of the American Mathematical Society, V. 21(2)

1974 p. A-294.
• # T.H. Southard
"Addition chains for the first n squares",
Report CNA-84, Center for Numerical Analysis, University of Texas at Austin,
May 1974.
• # T.H. Southard
"Addition chains for the first n triangular numbers",
Report CNA-85, Center for Numerical Analysis, University of Texas at Austin,
May 1974.
• # E. Vegh
"A Note on Addition Chains",
J. Comb. Theory, Ser. A, V. 19(1)

1975 pp 117-118.
• # E. Vegh
"Addition Chains",
Notices of the American Mathematical Society, V. 22(1)

1975 pp A2-A3.
• # A. Schönhage
"A Lower Bound for the Length of Addition Chains",
Theoretical Computer Science, V. 1(1)

1975 p. 1-12.
• # A.A. Gioia, M.V. Subbarao
"The Scholz-Brauer Problem in Addition Chains",
Notices of the American Mathematical Society V. 22

1975 p. A63-A64.
• # A.S. Saidan
The Arithmetic of al-Uqlîdisî
, Dordrecht 1975 pp 341-342
• # N. Pippenger
"On the Evaluation of Powers and Related Problems",
Proceedings, 19th Anual IEEE Symposium on the foundations of computer science,
Houston TX. 1976 pp 258-263.
• # E.G. Thurber
"Addition chains and solutions of l(2n)=l(n) and l(2^n-1)=n+l(n)-1",
Discrete Mathematics, V. 16(3)

1976 pp 279-289.
• # A.C-C. Yao
"On the Evaluation of Powers",
SIAM J. Comput. V. 5(1)

1976 pp 100-103.
• # E.G. Belaga
"The additive complexity of a natural number",
Soviet Mathematics Doklady V. 17(1)

1976 pp 5-9.
• # J. van Leeuwen
"An extension of {Hansen's} theorem for star chains",
J. Reine Angew. Math., V. 295

1977 pp 203-207.
• # D.P. McCarthy
"The optimal algorithm to evaluate x^n using elementary multiplication methods",
Mathematics of Computation V. 31(137)

1977 pp 251-256.
• # Rolf Sonntag
"Theorie der Additionsketten",
Diplomarbeit Technische Universität Hannover, 1978.
• # A.A. Gioia, M.V. Subbarao and M. Sugunamma
"The Scholz-Brauer Problem in Addition Chains II",
Proc. Eighth Manitoba Conference on Numerical Math. and Computing, XXII V. 22
1978 pp 251-274.
• # R.L. Graham and A.C.-C. Yao and F.-F. Yao
"Addition chains with multiplicative cost",
Discrete Mathematics, V. 23

1978 pp 115-119
• # D. Dobkin, R. Lipton
"Additive chain methods for the evaluation of specific polynomials",
Proceedings of a Conference on Theoretical Computer Science (Univ.Waterloo, Waterloo, Ont., 1977), Comput. Sci. Dept., Univ.Waterloo, Waterloo, Ont., V 148
1978 pp 146-148.
• # N. Pippenger
"On the Evaluation of Powers and Monomials",
SIAM J. Computing, V. 9

1980 pp 230-250.
• # D.E. Knuth
The Art of Computer Programming V. 2 Seminumerical Algorithms, 2. edition
Addison-Wesly 1981 pp 441-466.
• # D. Dobkin and R.J. Lipton
"Addition chain methods for the evaluation of specific polynomials",
SIAM Journal on Computing V. 9(1)

1980 pp 121-125.
• # N. Pippenger
"On the evaluation of powers and monomials",
SIAM Journal on Computing V. 9(2)

1980 pp 230-250.
• # P. Downey, B. Leony and R. Sethi
"Computing Sequences with Addition Chains",
SIAM Journal of Computing, V. 10(3)

1981 pp 638-646.
• # J. Olivos
"On Vectorial Addition Chains",
Journal of Algorithms, V. 2(1)

1981 pp 13-21.
• # D.E. Knuth, C.H. Papadimitriou
"Duality in addition chains",
Bulletin of the European Association for Theoretical Computer Science, V. 13

1981 pp 2-4.
• # I. Semba
"Systematic Method for Determining the Number of Multiplications Required to Compute x^m, where m is a Positive Integer",
Journal of Information Processing V. 6(1)

1983 pp 31-33.
• # Y.H. Tsai
"A study on some addition chain problems",
Master Thesis, National Tsing-Hua University, Hsinchu, Taiwan (6), 1985.
• # Y. H. Chin and Y. H. Tsai
"Algorithms for Finding the Shortest Addition Chain¨,
Proceedings of National Computer Symposium
Kaoshiung, Taiwan, December 20-22, 1985 pp 1398-1414.
• # H. Volger
"Some Results on Addition/Subtraction Chains",
Inf. Process. Lett. V. 20(3)

1985 pp. 155-160.
• # D.P. McCarthy
"Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains",
Mathematics of Computation, V. 46(174)

1986 pp 603-608.
• # T. Lickteig and H. Volger
"Some Results on the Complexity of Powers",
Computation Theory and Logic
, Editor Egon Börger
Springer-Verlag, 1987 pp 249-255.
• # Y. H. Tsai, Y. H. Chin
"A study of some addition chain problems",
International Journal of Computer Mathematics, V. 22(2)

1987 pp 117-134.
• # W. Orb
"Additionsketten",
Diploma Thesis, Mainz, University, 1987.
• # M. V. Subbarao
"Addition Chains --- Some Results and Problems",
Number Theory and Applications, Editor R. A. Mollin,
NATO Advanced Science Institutes Series: Series C, V. 265

Kluwer Academic Publisher Group 1989 pp 555-574.
• # F. Bergeron, J. Olivos
"Vectorial addition chains using Euclid's algorithm",
Research Report, Dept. Math., UQAM 105 (1989).
• # F. Bergeron, J. Berstel, S. Brlek, and C. Duboc
"Addition chains using continued fractions",
Journal Algorithms V. 10(3)

Sep. 1989 pp 403-412.
• # F. Bergeron, J. Berstel, S. Brlek
"A unifying Approach to the generation of Addition Chains",
Proceedings of the XV Latino-American Conference on Informatics, 1989 pp 10-14.
• # J. Bos, M. Coster
"Addition Chain Heuristics",
Advances in Cryptolog, CRYPTO' 89 Springer-Verlag 1989 pp 400-407.
• # M. Elias and F. Neri
"A Note on Addition Chains and Some Related Conjectures", Sequences, Editor R. M. Capocelli,
Springer-Verlag 1990 pp 166-181.
• # Y. Yacobi
"Exponentiating faster with addition chains",
Advances in Cryptology
EUROCRYPT '90, Springer-Verlag 1990 pp 222-229.
• # F. Morain, J. Olivos
"Speeding up the computations on an elliptic curve using addition-subtraction chains",
ITA V. 24(6)

1990 pp 531-544.
• # M.J. Coster
"Some algorithms on Addition Chains and their Complexity",
Tech. Report CS-R9024,
Centrum voor Wiskunde en Informatica, Amsterdam, 1990 pp 1-69.
• # A. Flammenkamp
"Drei Beiträge zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers",
Diplomarbeit an der Fakultät für Mathematik, Universität Bielefeld 1991.
• # H. Zantema
"Minimizing Sums of Addition Chains",
Journal of Algorithms", V. 12(2)

1991 pp 281-307.
• # S. Brlek, P. Castéran, R. Strandh
"On Addition Schemes",
TAPSOFT, V. 2

1991 pp 379-393.
• # S. Brlek, P. Castéran, R. Strandh
"Chaînes d'addition et structures de contrôle",
Journées JFLA91 (28-29 Janvier 1991, Gresse-en-Vercors, France) Bigre 72

1991 pp 54-63.
• # Y.H. Chin, Y.H. Tsai
"On Addition Chains",
International Journal Computer Math, V. 45(3-4)

1992 pp 145-160.
• # Y. H. Tsai and Y. H. Chin
"A Study of Addition Chain¨,
Proceedings of the National Science Council - Part A: Physical Science and Engineering, V 16(6)

1992 pp. 506-514.
• # J.N.E. Bos
"Practical Privacy",
PhD thesis, Eindhoven, University of Technology,
1992, ISBN 9061964059.
• # E.F. Brickell, D.M. Gordon, K.S. McCurley, D.B. Wilson
"Fast Exponentiation with Precomputation (Extended Abstract)",
EUROCRYPT 1992 pp 200-207.
• # O.K. Gupta
"On Evaluation of Powers",
Journal of Information & Optimization Sciences, V. 13(2)

1992 pp 331-336.
• # S. Brlek, R. Mallette
"Sur le calcul des chaînes d'additions optimales",
dans J. Labelle et J.G. Penaud, éditeurs,
Atelier de combinatoire franco-québecois (6-7 Mai 1991, Bordeaux, France)
Publ. du LACIM 10, 1992 ISBN 2-89276-101-8 pp 71-85.
• # J. Sauerbrey and A. Dietel
"Resource requirements for the application of addition chains in modulo exponentiation",
Workshop on the Theory and Application of of Cryptographic Techniques

1992 pp 174-182.
• # E. G. Thurber
"Addition chains --- an eratic sequence",
Discrete Mathematics, V. 122

1993 pp 287-305.
• # W. Aiello and M. V. Subbarao
"A conjecture in addition chains related to Scholz's conjecture",
Mathematics of Computation, V. 61(203)

1993 pp 17-23.
• # M.J. Coster
"An algorithm on addition chains with restricted memory",
Research memorandum 603

Tilburg University, Department of Economics, 1993.
• # A.G. Dempster, M.D. Macleod
"Constant integer multiplication using minimum adders",
IEE Proceedings - Circuits, Devices & Systems, V. 141(5)

1994 pp 407-413.
• # F. Bergeron, J. Berstel and S. Brlek
"Efficient Computation of Addition Chains",
Journal de Theorie des Nombres de Bordeaux, V. 6(1)

1994 pp 21-38.
• # Y.J. Chen, C.C Chang, and W.P. Yang
"Some Properties of Vectorial Addition Chains",
International Journal of Computer Mathematics, V. 54(3-4)
br> 1994 pp 185-196.
• # Y.J. Chen
"Some Properties on Vectorial Addition Chains¨,
Ph.D. dissertation, Institute of Computer Science and Information Engineering, National Chiao Tung University, Hsinchu, Taiwan, R.O.C., December 1994
• # P.J.N de Rooij
"Efficient exponentiation using precomputation and vector addition chains",
Workshop on the Theory and Application of of Cryptographic Techniques

EuroCrypt '94, 1994 pp 389-399.
• # S.B. Gashkov and V.V. Kochergin
"On addition chains of vectors, gate circuits and the complexity of computations of powers",
Syberian Advances in Mathematics V. 4(4)

1994 pp 1-16.
• # V.V. Kochergin
"On the computation of powers sets",
Discrete Mathematics and Applications V. 4(2)

1994 pp 119-128.
• # O. Kochergin
"The Evaluation of Powers",
Math. Problems of Cybernetics, V. 26

1995 pp 76-82.
• # Y.J. Chen, C.C Chang, and W.P. Yang
"The Shortest Weighted Length Addition Chains",
Journal of Information Science and Engineering, V. 11(2)

1995 pp 295-305.
• # S. Brlek, P. Castéran, L. Habsieger, R. Mallette
"On-line evaluation of powers using Euclid's algorithm",
RAIRO, Inform. Theor. Appl. V. 29(5)

1995 pp 431-450.
• # I.E. Bocharova, B.D. Kudryashov
"Fast exponentiation in cryptography",
Proceeding of AAECC-11,
Lecture Notes in Computer Science, V. 948

Springer Verlag, 1995 pp 146-157.
• # V. Dimitrov and T. Cooklev
"Two algorithms for modular exponentiation using nonstandard arithmetics",
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences V. 78(1)

The Institute of Electronics, Information and Communication Engineers 1995 pp 82-87.
• # C. Ko`c
"Analysis of sliding window techniques for exponentiation",
Computers & Mathematics with Applications V. 30(10)

1995 pp 17-24.
• # Y. Wu
"Strength reduction of multiplications by integer constants",
ACM SIGPLAN Notices V. 30(2)

1995 pp 42-48.
• # C.Y. Chen, C.C. Chang, and W.P. Yang
"Hybrid Method for Modular Exponentiation with Precomputation",
Electronics Letters, V. 32(6)

1996 pp 540-541.
• # D.C. Lou, and C.C. Chang
"Fast Exponentiation Method Obtained by Folding the Exponent in Half",
Electronics Letters, V. 32(11)

1996 pp 984-985.
• # D. Bleichenbacher
"Efficiency and Security of Cryptosystems based on Number Theory",
Dissertation to Swiss Federal Institute of Technology Zürich, ETH Zürich 1996.
• # V.V. Kochergin
"On the complexity of computation of monomials and tuples of powers",
Siberian Advances in Math V. 6(1)

1996 pp 71-86.
• # D. Bleichenbacher and A. Flammenkamp
"An Efficient Algorithm for Computing Shortest Addition Chains",
submitted 1997 to SIAM Journal of Discrete Mathematics

The same paper as gziped Postscript included all figures.
• # N. Kunihiro and H. Yamamoto
"Optimal addition chain classified by Hamming weight",
IEICE Technical Report, ISEC96-74, 1997.
• # Bahig, H.M.,
"On the algorithms of computational number theory and their applications",
Master Thesis, Dept. of Math., Faculty of Science, Ain Shams University, Cairo, Egypt 1998.
• # G.D. Cohen, A. Lobstein, D. Naccache, G. Zémor
"How to Improve an Exponentiation Black-Box",
EUROCRYPT 1998 pp 211-220.
• # D.M. Gordon
"A survey of fast exponentiation methods",
Journal of algorithms V. 27(1)

1998 pp 129-146.
• # D.E> Knuth
"The Art of Computer Programming", V. 2
Seminumerical Algorithms, 3. edition,
Addision Wesley, Reading, MA 1998 pp 461-485.
• # N. Kunihiro and H. Yamamoto
"Windows and Extended Window Methods for Addition Chain and Addition-Subtraction Chain",
IEICE Trans. on Fundamentals of Electronics, Comm. , V. 81(1) E83-A

1998 pp 72-81.
• # C.D. Walter
"Exponentiation Using Division Chains",
IEEE Trans. on Computers V. 47(7)

1998 pp 757-765.
• # D. Lou, C. Chang
"An adaptive exponentiation method",
Journal Systems Software V 42(1)

1998 pp 59-69.
• # Y. Yacobi
"Fast Exponentiation Using Data Compression",
SIAM J. Comput. V. 28(2)

1998 pp 700-703.
• # A. Flammenkamp
"Integers with a Small Number of Minimal Addition Chains",
Discrete Mathematics V. 205(1)

1999 pp 221-227.
• # E. G. Thurber
"Efficient Generation of Minimal Length Addition Chains",
SIAM Journal of Computing, V. 28(4)

1999 pp 1247-1263.
• # J. Abrahams
"Addition Chains as Test Trees and a Sequential Variant as the Huffman Problem",
DIMACS Technical Report 99-15, February 1999.
• # D. Bleichenbacher
"Addition chains for large sets",
Unpublished manuscript 1999.
• # J. von Zur Gathen, M. Nöcker
"Computing special powers in finite fields",
In Proceedings of the 1999 international Symposium on Symbolic and Algebraic Computation (Vancouver, British Columbia, Canada, July 28 - 31, 1999). S. Dooley, Ed. ISSAC. ACM Press,New York, pp 83-90.
• # H. Park, K. Park, Y. Cho
"Analysis of the variable length nonzero window method for exponentiation",
Computers & Mathematics with Applications V. 37(7)

1999 pp 21-29.
• # N. Kunihiro and H. Yamamoto
"New Methods for Generating Short Addition Chains",
IEICE Transactions. Fundamentals, E83-A, V. 83(1)

2000 pp 60-67.
• # M.J. Coster
"The Brun algorithm for Addition Chains",
Unpublished manuscript 2000.
• # V.S. Dimitrov, G.A. Jullien, W.C. Miller
"Complexity and Fast Algorithms for Multiexponentiations",
IEEE Trans. on Computers V. 49(2)

2000, pp 141-147.
• # X. Wang
"An algorithm for generating the shortest addition chains",
Mini-Micro Systems Shenyang, V. 22(10)

2001 pp 1250-1253.
• # M. Otto
"Brauer Addition-Subtraction Chains",
Diplomarbeit, Universität-Gesamthochschule Paderborn, 2001.
• # H.M. Bahig, M.H. El-Zahar, K. Nakamula
"Some Results for Some Conjectures in Addition Chains",
Combinatorics, Computability and Logic Proceedings of the 3rd international conference vol DMTCS '01
2001 pp 47-54.
• # C. Clavier and M. Joye
"Universal Exponentiation Algorithm",
In Proceedings of the Third international Workshop on Cryptographic Hardware and Embedded Systems (May 14 - 16, 2001). Lecture Notes In Computer Science, V. 2162

London, 2001 pp 300-308.
• # H.M. Bahig, K. Nakamula
"Some Properties of Nonstar Steps in Addition Chains and New Cases Where the Scholz Conjecture Is True",
Journal. Algorithms V. 42(2)

2002 pp 304-316.
• # N. Nedjah and L.M. Mourelle
"Minimal Addition Chain for Efficient Modular Exponentiation Using Genetic Algorithms",
IEA/AIE '02: Proceedings of the 15th international conference on Industrial and engineering applications of artificial intelligence and expert systems,
2002 pp 88-98.
• # D.J. Bernstein
"Pippenger's Exponentiation Algorithm",
2002.
• # B. Möller
"Improved techniques for fast exponentiation",
International Conference on Information Security and Cryptology

2002 pp 298-312.
• # H.M. Bahig, K. Nakamula
"Erratum to Some properties of nonstar steps in addition chains and new cases where the Scholz conjecture is true",
Journal Algorithms V. 47(1)

2003 pp 60-61.
• # M. Stam
"Speeding up Subgroup Cryptosystems",
Ph.D. Technische Universiteit Eindhoven, 2003.
• # P. Tummeltshammer, J. C. Hoe, and M. Püschel
"Multiplexed Multiple Constant Multiplication",
In Proceedings of the 41st Annual Conference on Design Automation (San Diego, CA, USA, June 07 - 11, 2004). DAC '04
ACM Press, New York, NY, pp 826-829.
• # R. Parker, A. Plater
"Addition Chains with a Bounded Number of Registers",
Information Processing Letters, V. 90(5)

2004 pp 247-252.
• # R.M. Avanzi
"A note on the signed sliding window integer recoding and a left-to-right analogue",
Selected Areas in Cryptography, Lecture Notes in Computer Science, ISSUE 3357,
2004 pp 130-143.
• # R. Guy
"Unsolved problems in number theory",
V. 1

Springer Science & Business Media
2004 pp 169-171.
• # N. Nedjah and L. de Macedo Mourelle
"Finding minimal addition chains using ant colony",
International Conference on Intelligent Data Engineering and Automated Learning 2004 pp 642-647.
• # J. von Zur Gathen and M. Nöcher
"Computing special powers in finite fields",
Mathematics of computation V. 73(247)

2004 pp 1499-1523.
• # N.C. Cortés, F.Rodríguez-Henríquez, R.Morales and C.A.C. Coello
"Finding Optimal Addition Chains Using a Genetic Algorithm Approach",
in Yue Hao et al. (editors), International Conference on Computational Intelligence and Security 2005 (CIS'05) Part I,
December 15-19, 2005, Xi'an, China
Springer-Verlag, Lecture Notes in Computer Intelligence,
2005 pp 208-215.
• # N. Nedjah and L. de Macedo Mourelle
"Efficient pre-processing for large window-based modular exponentiation using ant colony",
International Conference on Knowledge-Based and Intelligent Information and Engineering Systems

2005 pp 640-646.
• # C.S. Park and M.K. Lee and D.K. Kim
"New computation paradigm for modular exponentiation using a graph model",
International Symposium on Stochastic Algorithms

2005 pp 170-179.
• # H.M. Bahig
"Improved Generation of Minimal Addition Chains",
Computing V. 78(2)

2006 pp 161-172
• # H.M. Bahig
"On the Number of Minimal Addition Chains",
Proceedings of the 2006 International Conference on Scientific Computing, CSC 2006, Las Vegas, Nevada, USA, June 26-29, 2006
CSREA Press 2006, ISBN 1-60132-007-8 pp 202-208
• # H.M. Bahig, Hazem M. Bahig
"Speeding Up Evaluation of Powers and Monomials",
Proceedings of the 2006 International Conference on Foundations of Computer Science, Las Vegas, Nevada, USA, June 26-29, 2006
CSREA Press 2006, ISBN 1-60132-015-9 pp 149-153
• # Nadia1 Nedjah, Macedo Mourelle, Luiza
"Towards Minimal Addition Chains Using Ant Colony Optimisation",
Journal of Mathematical Modelling and Algorithms, V. 5(4)

2006 pp 525-543
• # M.M. Johansen
"Exponentiation with Addition Chains",
undergraduate project paper, undated.
• # A. Mityagin, I. Mironov, Y.N. Kobliner
"Systems and methods for generating random addition chains",
U.S. Patent xxx.
• # Sander van der Kruijssen
"Addition Chains -- efficient computing of powers"
Bachelor Thesis, Amsterdam, 2007
• # R. Goundar
" A Novel Multi-Exponentiation Method",
IAENG International Journal of Applied Mathematics, V. 37 (2)

, 2007 pp 89-95
• # R. Goundar
"Addition Chains in Application to Elliptic Curve Cryptosystems",
PhD thesis, Kochi University, Japan, 2008
• # R.R. Goundar, K. Shiota, and M. Toyonaga
"SPA Resistant Scalar Multiplication using Golden Ratio Addition Chain Method",
IAENG International Journal of Applied Mathematics, V. 38 (2)

2008, pp 83-88
• # N.C. Cortés, F. Rodríguez-Henríquez and A. C.A.C. Coello
"An Artificial Immune System Heuristic for Generating Short Addition Chains",
IEEE Transactions on Evolutionary Computation, V. 12(1)

2008 pp 1-24
• # R. Goundar, K. Shiota, and M. Toyonaga,
"New Strategy for Doubling-free Short Addition-Subtraction Chain",
Applied Mathematics & Information Sciences -- An International Journal, V. 2

2008, pp 123-133
• # R. Goundar, K. Shiota, and M. Toyonaga,
"A Novel Method for Elliptic Curve Multi-Scalar Multiplication",
International Journal of Applied Mathematics and Computer Sciences, V. 4

2009, pp 1-5
• # N. M. Clift,
"Calculating optimal addition chains",
Computing V. 91

2011, pp 265-284
legend:
# reviewed journal article
# thesis
# report, memorandum, paper
# conference proceedings
# monography
# unclassified or other

I like to thank Neill Clift, Kirkland, Washington, U.S.A., for far the most references in the preceeding bibliography list.

Achim Flammenkamp
Last update: 2018-07-31 11:44:13 UTC+2