We often want to raise some value (not necessarily a real value) to an integer power (exponentiation). This is a pretty common operation in cryptography. The product rule of exponents tells us that \(x^a\times x^b=x^{a+b}\). So, let's try and see how we would calculate \(x^{29}\). I pick 29 as this number shows up many strange properties that make the subject worth studying.
\(x^{29}=x^{20}\times x^9\)
\(x^{20}=x^{11}\times x^9\)
\(x^{11}=x^9\times x^2\)
\(x^9=x^8\times x^1\)
\(x^8=x^4\times x^4\)
\(x^4=x^2\times x^2\)
\(x^2=x^1\times x^1=x\times x\)
Now we can dispense with all the \(x^a\) type terms and just record the \(a\) (exponent) values. 1 2 4 8 9 11 20 29. Under the assumption that all the multiplies have the same cost (often true but not true for example with integers as the bigger they get the more expensive they are to multiply) and that squaring \(x^a\times x^a\) is the same cost as a general multiply \(x^a\times x^b, a\ne b\) we want to keep the list of exponents small in number. It turns out that the way I calculated \(x^{29}\) above is an example of a shortest chain. You can't do better than 7 steps (8 exponent values). There are 132 different ways of getting to 29 in 7 steps if we ignore how each exponent value is constructed and just focus on the exponent value. The number of ways of getting to 29 explode as we increase the length. So, for example, in 8, 9, 10 and 11 steps we have 1781, 12619, 58875 and 205368 ways to get to 29 respectively.
We will put what we saw here into more exact mathematical language next. That will make it easier to describe just how strange this simple problem is. Things that seem obvious are in fact not true and we don't really know very much about the subject.
My primary interest is in trying to find ways that computers can find shortest chains more efficiently. I am a bit of a treasure hunter looking for numbers with strange properties. Few people actually study this area and so this website is here to find people who want to exchange ideas, talk about the area or write programs. Beware it's highly addictive trying to improve addition chain programs.
Send me mail Neill Clift if you're interested.
Start with a list of numbers containing initially 1. Perform a number of steps where we add two (not necessarily different) existing numbers together and add the new number to the list. If we eventually arrive at the number n we call this an addition chain (or more rarely an additive chain) for n.
So, for example, we could create the following list 1,2,3,6,9,9,12,24,18 and call this an addition chain for n=18. We will call the individual values in an addition chain elements and n the target.
We should note some things about this addition chain for 18.
We will assume from now on that addition chains are ordered and duplicate or values exceeding the target are removed.
Formally then an addition chain is:
\(1=a_{0}<a_{1}<\cdots<a_{r}=n,\,a_{i} =a_{j} +a_{k}\) with \(i>j\ge k\ge0\)
We say this addition chain has length \(r\). The chain with the shortest length we call the optimal chain. We denote its length by \(l(n)\). Many interesting questions arise when we consider optimal chains. Lots of stuff that might seem obvious is in fact wrong. For example, it seems reasonable to assume that each step in an addition chain uses the largest element created so far or that the best way to reach \(2n\) is by doubling the last element of a chain for \(n\). Both of these assumptions turn out to be false.
We define:
\(\lambda(n)=\left\lfloor log_{2}(n)\right\rfloor \)
\(v(n)=\begin{cases}
0 & n=0\\
v(\left\lfloor \frac{n}{2}\right\rfloor )+n\mod2 & n>0
\end{cases}\) So, it's the number of 1s in the binary representation of n.
\(s(n) = l(n) - \lambda(n)\)
For step \(i\) of an addition chain we have two possibilities:
We can see from this that \(s(n)\) and \(\lambda(n)\) count the number of small and large steps respectively in an optimal addition chain for \(n\).
Additionally for step \(i\) we say that:
We define \(NMC(n)\) as the number of optimal addition chains for \(n\).
The smallest target requiring \(r\) steps in its optimal chain \(c(r) = \min \{n | l(n) = r\}\).
The number of targets requiring exactly \(r\) steps in their optimal chains \(d(r) = |\{n | l(n) = r\}|\).
We will often want to remove the ambiguity of how an addition chain element is constructed. We do this by tracking how each element is formed. I will use a hash notation to show this. For example, in this non-optimal addition chain for 4
1 2 3 4
I will use:
1 2 3 4#1,1 to show the element 4 is made from 2+2 or:
1 2 3 4#0,2 to show the element 4 is made from 1+3.
Here the hash is followed by two zero base indices into the addition chain.
It seems remarkable that \(v(n)\) appears to be bounded by the small step count of the chain:
\(v(n)\le2^{s(n)}\)
This conjecture is normally stated differently:
\(l(n)\ge\lambda(n)+\left\lceil log_{2}(v(n))\right\rceil \)
Cases \(s(n)=0,1\) can be determined with simple bounds. If \(s(n)=0\) then \(n=2^A\) and with \(s(n)=1\) then \(n=2^A+2^B\) is the best we can do bit count wise. Knuth outlines the case for \(s(n)=2\) yielding \(n=2^A+2^B+2^C\) or four cases were \(n=2^A+2^B+2^C+2^D\) (for example \(A-B=C-D\)).
The three-bit case was proved in [8] and the four-bit case by Knuth himself. Ed Thurber in his PhD thesis [9] proved the \(s(n)=3\) case. Achim Flammenkamp in his diploma thesis [10] wrote a computer program to enumerate all numbers reachable via 3 small steps and likewise found \(v(n)\le8\). I wrote a program to mimic the proof technique of Ed Thurber's thesis and verified the result but could not get it to work for the case \(s(n)=4\).
Using the derivative chains of Hanson transformed to graphs and making heavy use of symmetry to reduce problem size I was able to enumerate all numbers reachable with 4 and 5 small steps. I was also able to enumerate all the numbers reachable by 6 small steps restricted to those that might violate the conjecture.
So overall we know that \(v(n)\le2^{s(n)}\) for \(s(n)\le6\). So, for example, any number with \(v(n)\ge65\) must have \(s(n)\ge7\).
If this conjecture is true, it has some interesting consequences. Let's consider the number \(n = 223696213\) or in binary \(1101010101010101010101010101_2\). We have \(v(n) = 15\) so we expect \(s(n) \ge 4\).
We can easily see though that \(s(n) \ne 4\) since if \(s(n) = 4\) we could take an addition chain for \(n\) and extend it to form \(3n = 100111111111111111111111111111_2\):
1, 2, ..., 223696213, 447392426, 671088639
We have added only large steps but \(v(671088639) = 28\) so we expect \(5 \le s(3n) = s(n) = 4\) which is a contradiction. So, we must have \(s(n) \ge 5\).
Computer searches show \(s(671088639) = s(223696213) = 6\) achieved with the following chain:
1, 2, 3, 5, 10, 13, 23, 46, 92, 105, 210, 420, 840, 1680, 3360, 6720, 6825, 13650, 27300, 54600, 109200, 218400, 436800, 873600, 1747200, 3494400, 6988800, 13977600, 27955200, 55910400, 111820800, 223641600, 223696200, 223696213
I outline enumeration of small step chains here:
This conjecture asserts that:
\(l(2^n-1)\le l(n) + n - 1\)
I like the following alternate bound:
\(s(2^n-1)\le l(n)\)
To see why we might think this conjecture is true let's look at an optimal chain for \(2^8-1=255\) in binary:
1 10 11 110 1100 1111 11110 111100 1111000 11110000 11111111
We construct the target using only doublings and small steps that have no carries (in red). So, the bit counts of the small step elements and 1 form an addition chain for 8:
1 2 4 8
Obviously, we could take a chain for some other n and try to generate an addition chain for \(2^n-1\) using this technique. This only works though if the addition chain for n has all-star steps. Such a chain is called a star chain or a Brauer chain.
Brauer in [1] outlined the procedure to convert a Brauer chain for n into a chain for \(2^n-1\). Hansen in [2,3] generalized this for chains with a bit more flexibility (\(l^0\) or Hansen chains). Knuth [4] describes the Hansen algorithm via underlined elements.
Let's see this with the smallest number that has no optimal star chains (12509):
Each step must use the largest underlined entry in the chain. The last entry is underlined unconditionally. So, you must choose to underline in a way that achieves this. There can be more than one way to do it.
1, 2, 4, 8, 16, 17, 32, 64, 128, 256, 512, 1024, 1041, 2082, 4164, 8328, 12492, 12509
The red elements are forced as the next step is a doubling. One element of the two consumed by a step must be underlined. Using the same element in a doubling, forces the issue.
The blue elements are underlined because a step that consumes it also uses an underlined element that is not the largest in the list so far.
The green elements are underlined because they are consumed by a step that uses another element before the largest underlined one.
We could choose to underline or not underline the orange element as we wish.
In code checking that a chain is \(l^0\) I could not manage to come up with a better method than recursively trying the underlining cases for each step pruning out the invalid ones. When I discovered the first non-\(l^0\) (non-Hansen) number I did so with buggy detection code. I had somehow convinced myself I didn't need to backtrack ever in the underlining assignment. So, I had to run the search again to make sure I had found the first one.
The first non-Hansen number is 5784689 and its 16 optimal addition chains are:
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 16385 16401 32768 49169 81937 98322 180259 360518 721036 1442072 2884144 2900545 5784689
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 16385 16401 32768 49169 81937 98322 180259 360518 721036 1442072 2884144 5768288 5784689
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 16385 16401 32768 49169 81937 163874 180259 360518 721036 1442072 2884144 2900545 5784689
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 16385 16401 32768 49169 81937 163874 180259 360518 721036 1442072 2884144 5768288 5784689
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 16385 16401 32768 65536 81937 98322 180259 360518 721036 1442072 2884144 2900545 5784689
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 16385 16401 32768 65536 81937 98322 180259 360518 721036 1442072 2884144 5768288 5784689
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 16385 16401 32768 65536 81937 163874 180259 360518 721036 1442072 2884144 2900545 5784689
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 16385 16401 32768 65536 81937 163874 180259 360518 721036 1442072 2884144 5768288 5784689
1 2 4 8 16 32 64 65 97 128 225 353 706 1412 2824 5648 11296 22592 45184 90368 180736 180801 361537 723074 1446148 2892296 2892393 5784689
1 2 4 8 16 32 64 65 97 128 225 353 706 1412 2824 5648 11296 22592 45184 90368 180736 180801 361537 723074 1446148 2892296 5784592 5784689
1 2 4 8 16 32 64 65 97 128 225 353 706 1412 2824 5648 11296 22592 45184 90368 180736 361472 361537 723074 1446148 2892296 2892393 5784689
1 2 4 8 16 32 64 65 97 128 225 353 706 1412 2824 5648 11296 22592 45184 90368 180736 361472 361537 723074 1446148 2892296 5784592 5784689
1 2 4 8 16 32 64 65 97 128 256 353 706 1412 2824 5648 11296 22592 45184 90368 180736 180801 361537 723074 1446148 2892296 2892393 5784689
1 2 4 8 16 32 64 65 97 128 256 353 706 1412 2824 5648 11296 22592 45184 90368 180736 180801 361537 723074 1446148 2892296 5784592 5784689
1 2 4 8 16 32 64 65 97 128 256 353 706 1412 2824 5648 11296 22592 45184 90368 180736 361472 361537 723074 1446148 2892296 2892393 5784689
1 2 4 8 16 32 64 65 97 128 256 353 706 1412 2824 5648 11296 22592 45184 90368 180736 361472 361537 723074 1446148 2892296 5784592 5784689
We can see these are non-Hansen chains by noting that the red element must be underlined because it is doubled in the production of the green element. This forces the two elements between the red and green element to not be underlined. The blue element though uses the previous element (which cannot be underlined) and an element before the red element. So, it fails to use the largest underlined element.
So, from the first non-Hansen we know the Scholz-Brauer conjecture is true for all \(n < 5784689\) (assuming no programming errors). The mechanics of creating an addition chain for \(2^n-1\) from an \(l^0\) chain for n is best seen graphically and for this we need derivative chains.
Hansen [3] introduced derivative chains in his PhD thesis. A derivative chain represents and infinite number of addition chains with similar structure. They represent the non-doubling steps only and allow you to represent all addition chains with the same non-doubling steps with different numbers and placement of doubling steps.
So, take a couple of addition chains. Make them formal addition chains by selecting how each element is constructed (sometime and element may be made in more than one way):
1 2 4 8 16 17 33 66 99
We marked in red those elements that are doubling steps. Now for each non-doubling step we follow the chain of doublings for what it consumes till we get to non-doubled elements and form the sum from that.
So, 17 = 16 + 1 => 1 + 1 = 2. We also adjust any other element that consumes the changes elements. So, 33 = 17 + 16 => 2 + 1 = 3. then we delete the doubled elements as nothing should be using them. Programmatically I find it easier to replace the doubled elements with the undoubled values and recompute all the sums:
1 2 4 8 16 17 33 66 99
1 1 1 1 1 2 3 3 6
Yielding after deletion a derivative of 1 2 3 6.
A larger case that has non-star steps:
1 2 4 5 7 8#4,0 15 23 28 51 58 109
1 1 1 2 3 4 7 11 13 24 27 51
Yielding after deletion a derivative of 1 2 3 4 7 11 13 24 27 51.
Here are all the chains for 99 with their derivatives in curly brackets:
{1 2 4} 1 2 3 6 12 24 48 96 99
{1 2 4} 1 2 4 8 16 32 33 66 99
{1 2 3 6} 1 2 4 8 16 17 33 66 99
{1 2 4 6} 1 2 3 6 12 24 48 51 99
Derivative chains do not have to be monotonically increasing. Here this optimal addition chain for 11 has two derivatives depending on how we form 6 = 5 + 1 or 6 = 4 + 2 and one of the derivatives contains the value 2 twice. Note also that we need the derivatives to be formal and record how they are constructed. The last 4 in the first derivative is formed by the sum of the two different 2's:
{1 2 2 4#2,1} {1 2 3 5} 1 2 4 5 6 11
Derivatives may also have their values decrease as we can see in this optimal chain for 29:
{1 2 3 2 5} 1 2 4 8 9 13 16 29
If we take the values in a derivative chain and have those as vertices in a graph. We have directed edges representing the two elements consumed starting at the sum source vertices and ending at the vertices representing the sum.
Each vertex then represents a set of numbers that are powers of two of a base number. These are all the numbers that would have been removed when we created the derivative. Since all but the last element in a derivative chain have associated vertices that are the source of an edge, we can encode what element is selected in an edge label. So, if the base number is \(b\) then the vertex for b represents the values \(b,2b,4b,..., 2^{e}b\). An edge with the label \(e_1\) selects the value \(2^{e_1}\). So, if we have a derivative chain for \(n\) it has \(n\) directed paths from the vertex representing 1 to the vertex for \(n\). Each path has an edge sum that represents a single bit in a potential target the derivative can generate.
Here is an example derivative graph for an optimal chain for 99. The edge labels match the algorithm for generating an addition chain for \(2^{99}-1\) of Brauer.
There are 99 paths from vertex 1 to vertex 99. Each path has a distinct edge label sum from 0-98. So, you can think of the single bit in the value 1 traveling all these paths to generate the value \(2^{99}-1\). You get the doubling count for a vertex by taking the maximal edge count for edges leaving the vertex. You use the doubling count once you know the base value to generate the appropriate number of doublings. Edge numbers tell you what element to select from the list of doublings in the addition to form a new element.
The rules for the labeling for a Brauer chain are to take the two inputs for each vertex (apart from 1). For the largest vertex input edge give it a value equal to the difference between the input and output vertex. If the input edges come from the same source, you can choose either edge from the pair. All other edges get the value zero. Let's build the addition chain for \(2^{99}-1\) from this graph:
1 2 3 6 7 14 28 56 63 ... 4032 4095 ... 16773120 16777215 ... 281474959933440 281474976710655 ... 2251799813685240 2251799813685247 ... 633825300114114419273374892032 633825300114114700748351602687
It is easy to prove by induction that for the vertex representing the value \(v\) has a base value of \(2^v-1\). We must also prove that this chain has \(n - 1 = 98\) doublings. It's easy to see this by summing the vertex doubling counts. There must be one critical path that passes through the maximal doubling of each vertex. The critical path must go through an edge with a label that is the largest for all the edges leaving a vertex. Its edge sum must be \(n-1\). It's this property that can fail if we try to label a non-Brauer chain in this way.
Let's take the following \(l^0\) chain:
1 2 4 8 9 12 17 29
If we create the graph and label it like we did a Brauer chain, we get the following:
We can see this graph has no critical path. The largest edge leaving 8 is 4 but no path going through this edge can capture the largest non-zero (and only edge) leaving 9. As a result, this addition chain has 1+2+4+4+8+0+12 = 31 doublings. For an addition chain for 229-1 using this derivative graph we need 28 doublings.
We can resolve this by changing the labeling rules to work with \(l^0\) chains. We label the edge to the largest underlined vertex with a label equal to the other edges vertex. If both edges, go to the same place, we can select between the two as we like. The other edge gets the label 0. This algorithm generates the following labeling:
This will generate an addition chain with 1+2+4+9+0+0+12 = 28 which is the correct number. We can see again that each vertex for v will have a base value of \(2^v-1\). The critical path will be a path through the underlined vertices.
The next thought then is if we can label a non-Hansen derivative graph in such a way that we generate all the path edge sums from 0 to \(n-1\) and have a critical path. The idea here is to try and find another labeling algorithm that would bridge the gap created by the non-Hansen number 5784689. Let's take the following non-Hansen chain:
1 2 4 8 9 13 16 29
With this chain the first 5 values are forced to be underlined. the construction of 16 though cannot satisfy the underlining requirement and we have a non-Hansen chain. Computationally labeling the edges of a graph to satisfy the requirements seems to be very expensive. So, we need to keep the total number of paths small. Here is one such labelling:
This critical path contains vertices 1 2 4 8 16 29 with edge labels of 1+2+4+8+13 = 28. This generates the following addition chain:
1 2 3 6 12 15 30 60 120 240 255 510 1020 2040 4080 8160 8161 8191 16320 32640 65280 65535 ... 536862720 536870911
The two numbers placed inside the purple run are for vertices 9 and 13. We no longer have the property that vertex v has a base value of \(2^v-1\).
I spent quite a bit of time labeling larger and larger graphs getting the feeling you could always seem to do it unless the graph had some structures, I thought too strange to appear in optimal addition chains.
I made a smaller graph from the non-Hansen number by deleting some doubling steps. The idea being to try and keep some structure that might be important. I ended up with this graph:
It's not possible to label this graph under the constraints that all paths must have label sums that are unique from 0-108 and have a critical path. This floored me as I didn't expect this.
I was unable to come up with a way of proving this in a simple way.
So, I searched for numbers that have structures I can prove can't be labeled. I found the monster:
1 2 4 6 12 24 48 96 192 384 396 397 768 793 1536 3072 3865 7730 15460 30920 61840 123680 247360 494720 989440 1978880 3957760 3958553 7917106 15834212 31668424 63336848 126673696 253347392 506694784 1013389568 2026779136 4053558272 8107116544 16214233088 32428466176 32428466573
It's easy to prove the problematic red numbers can prevent the graph for this addition chain having a critical path. All the addition chains for this number appear to have a similar structure. This can be seen from the partial graph:
Here the parallel edges through vertices 384, 768, 1536, 3072 mean the critical path must go through those vertices. There are two paths from 396 to 793 so to prevent a single bit that follow these paths carrying we need one of the edges in this loop to be non-zero. That edge though can't be in a path with say the vertex for 1536. So, this graph can't be labeled.
What this means is that the derivative chains for the optimal addition chains for \(2^{32428466573}-1\) can never be for the target 32428466573. So, it's harder to see a relationship between \(l(2^{32428466573}-1)\) and \(l(32428466573)\).
Calculating Optimal Addition Chains
I have tried to build a list of all publications on addition chains. This is not simple because it can be difficult to draw the line between a paper on addition chains and one that uses them.
I do not include addition-subtraction chains but do include addition sequences and vector addition chains as recent work shows they are tied together.
I have tried to obtain all of these publications and only have a few missing. I would welcome any additional references or access to the stuff I do not have. The articles in red I do not have copies of.
[1] Brauer A (1939), "On addition chains", Bulletin of the American Mathematical Society. Vol. 45(10), pp. 736-739.
[2] Hansen W (1957), "Untersuchungen über die Scholz-Brauerschen Additionsketten und deren Verallgemeinerung". Thesis at: Göttingen.
[3] Hansen W (1959), "Zum Scholz-Brauerschen Problem.", Journal für die reine und angewandte Mathematik. Vol. 202, pp. 129-136.
[4] Knuth DE (1969), "The art of computer programming, 2: seminumerical algorithms, Addison Wesley", Reading, MA., §4.6.3, pp. 398-422.
[5] Knuth DE (1998), "The art of computer programming, 2: seminumerical algorithms, Addison Wesley", Reading, MA., §4.6.3, pp. 461-485.
[6] Thurber EG (1999), "Efficient Generation of Minimal Length Addition Chains", SIAM Journal on Computing. Vol. 28(4), pp. 1247-1263.
[7] Thurber EG and Clift NM, "Addition chains, vector chains, and efficient computation", Discrete Mathematics, Volume 344, Issue 2, 2021,
[8] Gioia A, Subbarao M and Sugunama M (1962), "The Scholz-Brauer problem in addition chains", Duke Math. J. Vol. 29, pp. 481-487.
[9] Thurber, E. "The Scholz-Brauer Problem on Addition Chains", University of Southern California, University of Southern California, 1971.
[10] Flammenkamp A (1991), "Drei Beiträge zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers". Thesis at: Diplomarbeit an der Fakultät für Mathematik, Universität Bielefeld.
Kim DK and Lee M-K (2006), "A COMPUTATION MODEL FOR MODULAR EXPONENTIATION USING GRAPH REPRESENTATION", MITA 2006. , pp. 487-490.
Aiello W and Subbarao M (1993), "A conjecture in addition chains related to Scholz’s conjecture", mathematics of computation. Vol. 61(203), pp. 17-23.
Walter CD (2012), "A duality in space usage between left-to-right and right-to-left exponentiation", In Cryptographers’ Track at the RSA Conference. , pp. 84-97.
Bahig HM and AbdElbari KA (2018), "A fast GPU-based hybrid algorithm for addition chains", Cluster Computing., aug, 2018. Springer Nature America, Inc.
Rodriguez-Cristerna A and Torres-Jimenez J (2013), "A genetic algorithm for the problem of minimal brauer chains", In Recent Advances on Hybrid Intelligent Systems. , pp. 481-500. Springer.
Rodriguez-Cristerna A and Torres-Jimenez J (2013), "A genetic algorithm for the problem of minimal brauer chains for large exponents", In Soft Computing Applications in Optimization, Control, and Recognition. , pp. 27-51. Springer.
Vázquez-Fernández E, Cadena C and Reyes-Gómez DA (2016), "A genetic algorithm with a mutation mechanism based on a Gaussian and uniform distribution to minimize addition chains for small exponents", In Evolutionary Computation (CEC), 2016 IEEE Congress on. , pp. 935-940.
Osorio-Hernández LG, Mezura-Montes E, Cruz-Cortés N and Rodriguez-Henriquez F (2009), "A genetic algorithm with repair and local search mechanisms able to find minimal length addition chains for small exponents", In 2009 IEEE Congress on Evolutionary Computation. , pp. 1422-1429.
Mohamed MA, Said M and Rushdan M (2015), "A hybrid addition chain method for faster scalar multiplication", WSEAS Transactions on Communications. Vol. 14, pp. 144-152. World Scientific and Engineering Academy and Society.
Schönhage A (1975), "A lower bound for the length of addition chains", Theoretical Computer Science. Vol. 1(1), pp. 1-12. Elsevier.
Stolarsky KB (1969), "A lower bound for the Scholz-Brauer problem", Canad. J. Math. Vol. 21, pp. 675-683.
Cottrell A (1973), "A lower bound for the Scholz-Brauer problem. preliminary report", In Notices of the American Mathematical Society. Vol. 20(5), pp. A476.
Rodriguez-Cristerna A, Torres-Jiménez J, Rivera-Islas I, Hernandez-Morales CG, Romero-Monsivais H and Jose-Garcia A (2011), "A mutation-selection algorithm for the problem of minimum brauer chains", In Mexican International Conference on Artificial Intelligence. , pp. 107-118.
Mani K and Viswambari M (2017), "A New Method of Generating Optimal Addition Chain Based on Graph", International Journal of Mathematical Sciences and Computing. Vol. 3(2), pp. 37-54.
Bahig HM and Bahig HM (2011), "A new strategy for generating shortest addition sequences", Computing. Vol. 91(3), pp. 285-306. Springer.
Mignotte M and Tall A (2011), "A note on addition chains", International Journal of Algebra. Vol. 5(6), pp. 269-274.
Vegh E (1975), "A note on addition chains", Journal of Combinatorial Theory, Series A. Vol. 19(1), pp. 117-118. Elsevier.
Whyburn C (1965), "A note on addition chains", Proceedings of the American Mathematical Society. Vol. 16(5), pp. 1134.
Elia M and Neri F (1990), "A note on addition chains and some related conjectures", In Sequences. , pp. 166-181.
Utz W (1953), "A note on the Scholz-Brauer problem in addition chains", Proceedings of the American Mathematical Society. Vol. 4(3), pp. 462-463.
Avanzi RM (2004), "A note on the signed sliding window integer recoding and a left-to-right analogue", In International Workshop on Selected Areas in Cryptography. , pp. 130-143.
Goundar RR (2007), "A Novel Multi Exponentiation Method", International Journal of Applied Mathematics. Vol. 37(2) Citeseer.
Fu-guo D and Yu-rong L (2008), "A novel shortest addition chains algorithm based on Euclid algorithm", Proceeding of WiCom (2008 4th International Conference on Wireless Communications, Networking and Mobile Computing). , pp. 4757-4761.
Herbaut F and Véron P (2010), "A public key cryptosystem based upon euclidean addition chains", In International Conference on Sequences and Their Applications. , pp. 284-297.
Giese R (1972), "A Sequence of Counterexamples of Knuth's Modification of Utz's Conjecture", In NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY. Vol. 19, pp. A688.
Jose-Garcia A, Romero-Monsivais H, Hernandez-Morales CG, Rodriguez-Cristerna A, Rivera-Islas I and Torres-Jimenez J (2011), "A simulated annealing algorithm for the problem of minimal addition chains", In Portuguese Conference on Artificial Intelligence. , pp. 311-325.
Tsai Y and Chin Y (1992), "A Study of Addition Chain", In Proceedings of the National Science Council - Part A: Physical Science and Engineering. Vol. 16(6), pp. 506-514.
Tsai Y and Chin Y (1987), "A study of some addition chain problems", International Journal of Computer Mathematics. Vol. 22(2), pp. 117-134. Taylor & Francis.
Tsai Y (1985), "A study on some addition chain problems". Thesis at: National Tsing-Hua University, Hsinchu, Taiwan.
Gordon DM (1998), "A survey of fast exponentiation methods", Journal of algorithms. Vol. 27(1), pp. 129-146. Elsevier.
Bergeron F, Berstel J and Brlek S (1989), "A unifying approach to the generation of addition chains", In Proc. XV Latin American Conf. on Informatics, Santiago, Chile July. , pp. 10-14.
Bos J and Coster M (1989), "Addition chain heuristics", In Conference on the Theory and Application of Cryptology. , pp. 400-407.
Dominguez-Isidro S, Mezura-Montes E and Osorio-Hernández LG (2011), "Addition chain length minimization with evolutionary programming", In Proceedings of the 13th annual conference companion on Genetic and evolutionary computation. , pp. 59-60.
Dobkin D and Lipton RJ (1980), "Addition chain methods for the evaluation of specific polynomials", SIAM Journal on Computing. Vol. 9(1), pp. 121-125. SIAM.
Dobkin D and Lipton RJ (1978), "Addition chain methods for the evaluation of specific polynomials", In Proceedings of a Conference on Theoretical Computer Science (Univ.Waterloo, Waterloo, Ont., 1977). , pp. 146–-148.
E VEGH (1975), "Addition chains", In Notices of the American Mathematical Society. Vol. 22(1), pp. A2-A3.
Fuguo D, Pingqin W and Lei F (2011), "Addition Chains Algorithm Based on Fast Fourier Transform", JDCTA: International Journal of Digital Content Technology and its Applications. Vol. 5(2), pp. 149-157.
Thurber EG (1976), "Addition chains and solutions of l(2n)=l(n) and l(2^n-1)=n + l(n) - 1", Discrete Mathematics. Vol. 16(3), pp. 279-289. Elsevier.
Knuth D (1964), "Addition chains and the evaluation of n-th powers", Notices Am Math Soc. Vol. 11, pp. 230-231.
Abrahams J (1999), "Addition Chains as Test Trees and a Sequential Variant as the Huffman Problem". Thesis at: The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS). Citeseer.
Bleichenbacher D (1999), "Addition chains for large sets", Unpublished manuscript.
Southard TH (1974), "Addition Chains for the first n squares" Center for Numerical Analysis, University of Texas at Austin.
Southard TH (1974), "Addition chains for the first n triangular numbers" Center for Numerical Analysis, University of Texas at Austin.
Kohonen J and Corander J (2014), "Addition chains meet postage stamps: Reducing the number of multiplications", Journal of Integer Sequences. Vol. 17(2), pp. 3.
Bergeron F, Berstel J, Brlek S and Duboc C (1989), "Addition chains using continued fractions", Journal of Algorithms. Vol. 10(3), pp. 403-412. Elsevier.
Parker R and Plater A (2004), "Addition chains with a bounded number of registers", Information processing letters. Vol. 90(5), pp. 247-252. Elsevier.
Van-Der Kruijssen S (2007), "Addition Chains, efficient computing of powers", Bachelor Proyect.. Thesis at: Amsterdam. Vol. 1, pp. 13-50.
Thurber EG (1993), "Addition chains—an erratic sequence", Discrete mathematics. Vol. 122(1), pp. 287-305. Elsevier.
Subbarao M (1989), "Addition chains-some results and problems", Number theory and applications. , pp. 555-574. Kluwer Academic Publishers, Dordrecht.
Orb W (1987), "Additionsketten". Thesis at: Mainz University.
Gaal P (1971), "Additionsketten in einer endlich erzeugten abelschen Gruppe". Thesis at: Zurich.
Bellman R (1963), "Advanced problem 5125", Amer. Math. Monthly. Vol. 70, pp. 765.
Chin Y and Tsai Y (1985), "Algorithms for finding the shortest addition chain", In Proceedings of national computer symposium, Kaoshiung, Taiwan, December. , pp. 1398-1414.
Lou D-C and Chang C-C (1998), "An adaptive exponentiation method", Journal of Systems and Software. Vol. 42(1), pp. 59-69. Elsevier.
Wang X-d (2001), "An Algorithm for Generating the Shortest Addition Chains", MINIMICRO SYSTEMS-SHENYANG-. Vol. 22(10), pp. 1250-1253. GAI-KAN BIAJIBU.
Coster MJ and others (1993), "An algorithm on addition chains with restricted memory"
Gashkov SB and Sergeev IS (2006), "An application of the method of additive chains to inversion in finite fields", Discrete Mathematics and Applications dma. Vol. 16(6), pp. 601-618.
Cruz-Cortés N, Rodriguez-Henriquez F and Coello CAC (2008), "An artificial immune system heuristic for generating short addition chains", IEEE Transactions on Evolutionary Computation. Vol. 12(1), pp. 1-24. IEEE.
Flammenkamp DBA (1997), "An Efficient Algorithm for Computing Shortest Addition Chains"
Wang X (2013), "An Efficient Algorithm for Finding Optimal Addition Chains", Indonesian Journal of Electrical Engineering and Computer Science. Vol. 11(11), pp. 6447-6453.
Dominguez-Isidro S and Mezura-Montes E (2011), "An Evolutionary Programming Algorithm to Find Minimal Addition Chains", In I Congreso Internacional de Ingeniería Electrónica, Instrumentación y Computación, de Junio del, Minatitlán Veracruz, México.
van Leeuwen J (1977), "An extension of Hansen's theorem for star chains", J. Reine Angew. Math. Vol. 295, pp. 203-207.
Adamu Muhammad Noma Mohamad Afendee Mohamed AM and Zulkarnain ZA (2016), "An Initial Solution for Addition Chain Optimization Problem", Journal of Engineering and Applied Sciences. (11), pp. 640-643.
Koç CK (1995), "Analysis of sliding window techniques for exponentiation", Computers & Mathematics with Applications. Vol. 30(10), pp. 17-24. Elsevier.
Park H, Park K and Cho Y (1999), "Analysis of the variable length nonzero window method for exponentiation", Computers & Mathematics with applications. Vol. 37(7), pp. 21-29. Elsevier.
Nedjah N and de Macedo Mourelle L (2006), "Ant colony optimisation for fast modular exponentiation using the sliding window method", In Swarm Intelligent Systems. , pp. 133-147. Springer.
Arpe J and Manthey B (2006), "Approximability of minimum and-circuits", In Scandinavian Workshop on Algorithm Theory. , pp. 292-303.
Arpe J and Manthey B (2009), "Approximability of minimum AND-circuits", Algorithmica. Vol. 53(3), pp. 337-357. Springer.
Scholz A (1937), "Aufgabe 253 (Problem 253)", Jahresbericht der deutschen Mathematiker-Vereinigung. Vol. 47(2), pp. 41-42.
Otto M (2001), "Brauer addition--subtraction chains". Thesis at: Diplomarbeit, Universität--Gesamthochschule Paderborn.
Clift NM (2011), "Calculating Optimal Addition Chains", Computing. New York, NY, USA, March, 2011. Vol. 91(3), pp. 265-284. Springer-Verlag New York, Inc..
Knuth DE (1969), "Calculations on Addition Chains"
Brlek A, Castéran P and Strandh R (1991), "Chaînes d'additions et structures de contrôle", In Journées JFLA91 (Gresse-en-Vercors, France).
Dimitrov VS, Jullien GA and Miller WC (2000), "Complexity and fast algorithms for multiexponentiations", IEEE Transactions on Computers. Vol. 49(2), pp. 141-147. Citeseer.
Downey P, Leong B and Sethi R (1981), "Computing sequences with addition chains", SIAM Journal on Computing. Vol. 10(3), pp. 638-646. SIAM.
von Zur Gathen J and Nöcker M (2004), "Computing special powers in finite fields", Mathematics of computation. Vol. 73(247), pp. 1499-1523.
Demetriou CA (1967), "Concerning minimal addition chains". Thesis at: University of Mississippi.
Dempster AG and Macleod M (1994), "Constant integer multiplication using minimum adders", IEE Proceedings-Circuits, Devices and Systems. Vol. 141(5), pp. 407-413. IET.
Li Y and Ma Q (2010), "Design and Implementation of Layer Extended Shortest Addition Chains Database for Fast Modular Exponentiation in RSA", In Web Information Systems and Mining (WISM), 2010 International Conference on. Vol. 1, pp. 136-139.
Bernstein DJ (2006), "Differential addition chains", URL: http://cr. yp. to/ecdh/diffchain-20060219. pdf.
Knuth DE and Papadimitriou CH (1981), "Duality in addition chains", Bulletin of the European Association for Theoretical Computer Science. Vol. 13, pp. 2-4.
McCarthy DP (1986), "Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains", Mathematics of computation. Vol. 46(174), pp. 603-608.
Bleichenbacher D (1996), "Efficiency and security of cryptosystems based on number theory" Citeseer.
Wattel E and Jensen G (1968), "Efficient calculation of powers in a semigroup", Stichting Mathematisch Centrum. Zuivere Wiskunde. (ZW 1/68), pp. 1-18. Stichting Mathematisch Centrum.
Bergeron F, Berstel J and Brlek S (1994), "Efficient computation of addition chains", Journal de théorie des nombres de Bordeaux. Vol. 6(1), pp. 21-38.
De Rooij P (1994), "Efficient exponentiation using precomputation and vector addition chains", In Workshop on the Theory and Application of of Cryptographic Techniques. , pp. 389-399.
Nedjah N and de Macedo Mourelle L (2005), "Efficient pre-processing for large window-based modular exponentiation using ant colony", In International Conference on Knowledge-Based and Intelligent Information and Engineering Systems. , pp. 640-646.
Bahig HM and Nakamula K (2003), "erratum to Some properties of nonstar steps in addition chains and new cases where the Scholz conjecture is true [J. algorithms 42 (2002) 304-316]", Journal of Algorithms. Vol. 47(1), pp. 60-61. Academic Press, Inc..
Picek S, Coello CAC, Jakobovic D and Mentens N (2016), "Evolutionary Algorithms for Finding Short Addition Chains: Going the Distance", In European Conference on Evolutionary Computation in Combinatorial Optimization. , pp. 121-137.
Dominguez-Isidro S, Mezura-Montes E and Osorio-Hernández L-G (2015), "Evolutionary programming for the length minimization of addition chains", Engineering Applications of Artificial Intelligence. Vol. 37, pp. 125-134. Elsevier.
Yacobi Y (1990), "Exponentiating faster with addition chains", In Workshop on the Theory and Application of of Cryptographic Techniques. , pp. 222-229.
Walter CD (1998), "Exponentiation using division chains", IEEE Transactions on Computers. Vol. 47(7), pp. 757-765. IEEE.
Johansen MM (2009), "Exponentiation with addition chains".
I. Bocharova BK (1995), "Fast Exponentiation in cryptography", Lecture Notes in C. Vol. 948, pp. 146-157.
Lou D-C and Chang C-C (1996), "Fast exponentiation method obtained by folding the exponent in half", Electronics Letters. Vol. 32(11), pp. 984-985. IET.
Yacobi Y (1998), "Fast exponentiation using data compression", SIAM Journal on Computing. Vol. 28(2), pp. 700-703. SIAM.
Nedjah N and de Macedo Mourelle L (2004), "Finding minimal addition chains using ant colony", In International Conference on Intelligent Data Engineering and Automated Learning. , pp. 642-647.
León-Javier A, Cruz-Cortés N, Moreno-Armendáriz MA and Orantes-Jiménez S (2009), "Finding minimal addition chains with a particle swarm optimization algorithm", In Mexican International Conference on Artificial Intelligence. , pp. 680-691.
Cruz-Cortés N, Rodriguez-Henriquez F, Juárez-Morales R and Coello CAC (2005), "Finding optimal addition chains using a genetic algorithm approach", In International Conference on Computational and Information Science. , pp. 208-215.
Picek S, Coello CAC, Jakobovic D and Mentens N (2018), "Finding short and implementation-friendly addition chains with evolutionary algorithms", Journal of Heuristics., jun, 2018. Vol. 24, pp. 457-481. Springer Nature.
Mani MK (2013), "Generation of Addition Chain using Deterministic Division Based Method", International Journal of Computer Science & Engineering Technology. Vol. 1(4), pp. 553-560.
Gelgi F and Onus M (2006), "Heuristics for minimum brauer chain problem", In International Symposium on Computer and Information Sciences. , pp. 47-54.
Datta B and Singh A (1935), "History of Hindu Mathematics" Bombay , pp. 76.
Cohen G, Naccache D, Lobstein A and Zémor G (1998), "How to improve an exponentiation black-box", In International Conference on the Theory and Applications of Cryptographic Techniques. , pp. 211-220.
Bahig HM (2006), "Improved generation of minimal addition chains", Computing. Vol. 78(2), pp. 161-172. Springer.
Möller B (2002), "Improved techniques for fast exponentiation", In International Conference on Information Security and Cryptology. , pp. 298-312.
Kochergin V (2015), "Improvement of the estimates of the computational complexity for monomials and sets of powers in Bellman’s and Knuth’s problems", Journal of Applied and Industrial Mathematics. Vol. 9(1), pp. 68-82. Springer.
Kochergin VV and Kochergin DV (2017), "IMPROVEMENT OF THE LOWER BOUND FOR THE COMPLEXITY OF EXPONENTIATION", Prikladnaya diskretnaya matematika., dec, 2017. (38), pp. 119-132. Tomsk State University.
Altman HJ (2014), "Integer complexity, addition chains, and well-ordering". Thesis at: University of Michigan.
Abbas M and Gustafsson O (2012), "Integer Linear Programming Modeling of Addition Sequences With Additional Constraints for Evaluation of Power Terms"
Flammenkamp A (1999), "Integers with a small number of minimal addition chains", Discrete mathematics. Vol. 205(1), pp. 221-227. Elsevier.
Altman H (2014), "Internal Structure of Addition Chains: Well-Ordering", arXiv preprint arXiv:1409.1627.
Nedjah N and de Macedo Mourelle L (2002), "Minimal addition chain for efficient modular exponentiation using genetic algorithms", In International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems. , pp. 88-98.
Zantema H (1991), "Minimizing sums of addition chains", Journal of Algorithms. Vol. 12(2), pp. 281-307. Elsevier.
Olguín-Carbajal, M., Herrera-Lozada, J. C., Rivera-Zárate, I., Serrano-Talamantes, J. F., Cadena-Martínez, R., & Vásquez-Gómez, J. I. (2018), "Minimum Addition Chains Generation Using Evolutionary Strategies", Computación y Sistemas. Vol. 22(4)
Tummeltshammer P, Hoe JC and Püschel M (2004), "Multiple constant multiplication by time-multiplexed mapping of addition chains", In Proceedings of the 41st annual Design Automation Conference. , pp. 826-829.
Park CS, Lee M-K and Kim DK (2005), "New computation paradigm for modular exponentiation using a graph model", In International Symposium on Stochastic Algorithms. , pp. 170-179.
Kunihiro N and Yamamoto H (2000), "New methods for generating short addition chains", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. Vol. 83(1), pp. 60-67. The Institute of Electronics, Information and Communication Engineers.
Ragnarsson K and Tenner BE (2010), "Obtainable sizes of topologies on finite sets", Journal of Combinatorial Theory, Series A. Vol. 117(2), pp. 138-151. Elsevier.
Bahig HM (2008), "On a generalization of addition chains: Addition--multiplication chains", Discrete Mathematics. Vol. 308(4), pp. 611-616. Elsevier.Tsai YH and Chin YH (1992), "On Addition Chains", International Journal of Computer Mathematics. Vol. 45(3-4), pp. 145-160.
Kato H (1970), "On Addition Chains". Thesis at: University of Southern California.
Sonntag R (1978), "On Addition Chains"
Thurber EG (1973), "On addition chains 1 (mn)leq 1 (n)-b and lower bounds for c (r) ", Duke Mathematical Journal. Vol. 40(4), pp. 907-913. Duke University Press.
Gashkov S and Kochergin V (1994), "On addition chains of vectors, gate circuits and the complexity of computations of powers", Syberian Advances in Mathematics. Vol. 4(4), pp. 1-16.
Brlek S, Castéran P and Strandh R (1991), "On addition schemes", In International Joint Conference on Theory and Practice of Software Development. , pp. 379-393.
Il'in A (1965), "On additive number chains", Problemy Kibernet. Vol. 13, pp. 245-248.
Gupta OK (1992), "On Evaluation of Powers", Journal of Information and Optimization Sciences. Vol. 13(2), pp. 331-336. Taylor & Francis.
Koziel B, Azarderakhsh R, Jao D and Mozaffari-Kermani M (2016), "On Fast Calculation of Addition Chains for Isogeny-Based Cryptography"
HAYATA T and WAGATUMA M (2006), "ON TERNARY ADDITION CHAINS"
Bahig H (1998), "On the algorithms of computational number theory and their applications". Thesis at: Master Thesis, Dept. of Math., Faculty of Science, Ain Shams University, Cairo, Egypt.
Kochergin VV (2005), "On the complexity of computation of a pair of monomials in two variables", Discrete Mathematics and Applications. Vol. 15(6), pp. 547. Springer.
Kochergin V (1996), "On the complexity of computation of monomials and tuples of powers", Siberian Advances in Mathematics. Vol. 6(1), pp. 71-86.
Kochergin V (1994), "On the computation of powers sets", Discrete Mathematics and Applications. Vol. 4(2), pp. 119-128.
Yao AC-C (1976), "On the evaluation of powers", SIAM Journal on computing. Vol. 5(1), pp. 100-103. SIAM.
Pippenger N (1980), "On the evaluation of powers and monomials", SIAM Journal on Computing. Vol. 9(2), pp. 230-250. SIAM.
Pippenger N (1976), "On the evaluation of powers and related problems", In Foundations of Computer Science, 1976., 17th Annual Symposium on. , pp. 258-263.
Abbas M (2012), "On the implementation of integer and non-integer sampling rate conversion". Thesis at: Linköping University. Linköping University Electronic Press.
Mohamed MA (2011), "On the Improvement of Addition Chain in Applications to Elliptic Curve Cryptosystem Status: Submitted". Thesis at: Universiti Putra Malaysia.
Val'skii R (1959), "On the Lower Bounds of Multiplications in Evaluation of Powers", Problemy Kibernet. Vol. 2, pp. 73-74.
Bahig HM (2006), "On the Number of Minimal Addition Chains.", In CSC. , pp. 202-208.
Olivos J (1981), "On Vectorial Addition Chains.", J. Algorithms. Vol. 2(1), pp. 13-21.
Brlek S, Castéran P, Habsieger L and Mallette R (1995), "On-line evaluation of powers using Euclid's algorithm", Informatique théorique et applications. Vol. 29(5), pp. 431-450.
Kunihiro N and Yamamoto H (1997), "Optimal addition chain classified by Hamming weight". Thesis at: IEICE Technical Report, ISEC96-74.
Aquino F and Leguizamón G (2017), "Optimization of addition chains", In Computer Science & Technology Series.
Kadir MFA, Mohamed MA, Mohamad R, Mamat M and Muhammed A (2018), "Performance Comparison of Some Addition Chain Methods Based on Integer Family", In Information Science and Applications 2018., jul, 2018. , pp. 211-218. Springer Singapore.
Bernstein DJ (2002), "Pippenger's exponentiation algorithm" Citeseer.
Henry R (2010), "Pippenger’s Multiproduct and Multiexponentiation Algorithms". Thesis at: Citeseer.
Bos JNE (1992), "Practical privacy". Thesis at: Eindhoven University of Technology. Citeseer.
Goulard A (1894), "Question 393", L'Intermédiaire des Mathématiciens. Vol. 1, pp. 234.
de Jonquiéres E (1894), "Question 393 (A. Goulard)", L'Intermédiaire des Mathématiciens. Vol. 2, pp. 125-126.
Dellac H (1894), "Question 49", L'Intermédiaire des Mathématiciens. Vol. 1, pp. 20.
de Jonquiéres E (1894), "Question 49 (H. Dellac)", L'Intermédiaire des Mathématiciens. Vol. 1, pp. 162-164.
Méloni N and Hasan MA (2016), "Random Digit Representation of Integers", In ARITH 23.
Herbaut F, Liardet P-Y, Méloni N, Teglia Y and Véron P (2010), "Random Euclidean addition chain generation and its application to point multiplication", In International Conference on Cryptology in India. , pp. 238-261.
Erdös P (1960), "Remarks on number theory III. On addition chains", Acta Arithmetica. Vol. 6(1), pp. 77-81. Institute of Mathematics Polish Academy of Sciences.
Elias Y (2011), "Représentation d'un polynôme par un circuit arithmétique et chaines additives". Thesis at: Université de Montréal.
Sauerbrey J and Dietel A (1992), "Resource requirements for the application of addition chains in modulo exponentiation", In Workshop on the Theory and Application of of Cryptographic Techniques. , pp. 174-182.
Mohamed M and Atan KM (2012), "Rule Based Representation of Integer for a New Addition Chain Method", Applied Mathematical Sciences. Vol. 6(30), pp. 1497-1503.
Sautto JM, Santiago A, Bouza CN and Campos V (2016), "Scholz’s First Conjecture: A Brief Demonstration", Applied Mathematics. Vol. 7(01), pp. 70. Scientific Research Publishing.
Vallejo JMS, Moreno AS, Herrera CNB and Guzmán VC (2013), "Scholz’s Third Conjecture: A Demonstration for Star Addition Chains", Applied Mathematics. Vol. 4(10), pp. 1. Scientific Research Publishing.
Giese RP (1974), "Selected topics in addition chains". Thesis at: University of Houston.
Enge A, Hart W and Johansson F (2016), "Short addition sequences for theta functions", arXiv preprint arXiv:1608.06810.
Mohamed M, Md Said M, Mohd Atan K and Ahmad Zulkarnain Z (2011), "Shorter addition chain for smooth integers using decomposition method", International Journal of Computer Mathematics. Vol. 88(11), pp. 2222-2232. Taylor & Francis.
Straus EG (1964), "Solution to Problem 5125", Amer. Math. Monthly. Vol. 71, pp. 806-808.
Coster MJ (1990), "Some algorithms on addition chains and their complexity", Department of Computer Science [CS].. Thesis at: Centrum voor Wiskunde en Informatica, Amsterdam. (R 9024), pp. 1-69. CWI.
Hebb KR (1974), "Some problems on addition chains". Thesis at: Thesis (M. Sc.)--University of Alberta.
Bahig HM and Nakamula K (2002), "Some properties of nonstar steps in addition chains and new cases where the Scholz conjecture is true", Journal of Algorithms. Vol. 42(2), pp. 304-316. Elsevier.
Chen Y-J, Chang C-C and Yang W-P (1994), "Some properties of vectorial addition chains", International Journal of Computer Mathematics. Vol. 54(3-4), pp. 185-196. Taylor & Francis.
Bahig HM, El-Zahar MH and Nakamula K (2001), "Some Results for Some Conjectures in Addition Chains", In Combinatorics, Computability and Logic. , pp. 47-54. Springer.
Hebb K (1974), "Some results on addition chains. Preliminary report.", In Notices of the American Mathematical Society. Vol. 21(2), pp. A294-A294.
Volger H (1985), "Some results on addition/subtraction chains", Information Processing Letters. Vol. 20(3), pp. 155-160. Elsevier.
Lickteig T and Volger H (1987), "Some results on the complexity of powers", In Computation theory and logic. , pp. 249-255. Springer.
Byrne A, Crowe F, Marnane WP, Meloni N, Tisserand A and Popovici E (2007), "SPA resistant elliptic curve cryptosystem using addition chains", International Journal of High Performance Systems Architecture. Vol. 1(2), pp. 133-142. Inderscience Publishers.
Goundar R, Shiota K-i and Toyonaga M (2008), "SPA resistant scalar multiplication using golden ratio addition chain method", International Journal of Applied Mathematics. Vol. 38(2), pp. 83-88.
Bahig HM and Bahig HM (2006), "Speeding Up Evaluation of Powers and Monomials.", In FCS. , pp. 149-153.
Stam M (2003), "Speeding up subgroup cryptosystems". Thesis at: Technische Universiteit Eindhoven.
Morain F and Olivos J (1990), "Speeding up the computations on an elliptic curve using addition-subtraction chains", Informatique théorique et Applications. Vol. 24(6), pp. 531-543.
Bahig HM (2011), "Star reduction among minimal length addition chains", Computing. Vol. 91(4), pp. 335-352. Springer.
Wu Y (1995), "Strength reduction of multiplications by integer constants", ACM SIGPLAN Notices. Vol. 30(2), pp. 42-48. ACM.
Brlek S and Mallette R (1992), "Sur le calcul des chaînes d'additions optimales", Atelier de combinatoire franco-québecois (6-7 Mai 1991, Bordeaux, France). , pp. 71-85.
Semba I (1983), "Systematic Method for Determining the Number of Multiplications Required to Compute xˆ m, Where m is a Positive Integer", Journal of information processing. Vol. 6(1), pp. 31-33. 一般社団法人情報処理学会.
Mityagin A, Mironov I and Kobliner YN (2010), "Systems and methods for generating random addition chains", February 2, 2010. Google Patents.
Belaga E (1976), "THE ADDITIVE COMPLEXITY OF A NATURAL NUMBER", Soviet Mathematics Doklady. Vol. 17(1), pp. 5. American Mathematical Society..
Coster M (2000), "The Algorithm of Brun and Addition Chains"
Coster M (2000), "The Brun Algorithm for Addition Chains"
Dong F-g, Li Y-r and Li J-j (2010), "The Consistency Analysis of Addition Chains for Several Fast Algorithm of Modular Exponentiation.", JDCTA. Vol. 4(5), pp. 82-88.
McCarthy DP (1977), "The optimal algorithm to evaluate x^n using elementary multiplication methods", Mathematics of Computation. Vol. 31(137), pp. 251-256.
Gioia A and Subbarao M (1975), "The Scholz-Brauer problem in addition chains", Notices of the American Mathematical Society. Vol. 22, pp. A63-A64.
Gioia A and Subbarao M (1978), "The Scholz-Brauer problem in addition chains II", In Proc. eighth Manitoba conference on numerical math. and computing. Vol. 22, pp. 251-274.
Thurber E (1971), "The Scholz-Brauer problem on addition chains", Notices of the american Mathematical Society.
Thurber E (1973), "The Scholz-Brauer problem on addition chains", Pacific Journal of Mathematics. Vol. 49(1), pp. 229-242. Mathematical Sciences Publishers.
Val'skii R (1961), "The Smallest Number of Multiplications Necessary to Raise a Number to a Given Power", Problems of Cybernetics. Vol. 2, pp. 395-397.
Hendley SM (1954), "The theory and construction of addition chains"
Bernstein DJ (2006), "The transposition principle"
Sonntag R (1978), "Theorie der Additionsketten". Thesis at: Technische Universität Hannover.
Tummeltshammer P, Hoe JC and Puschel M (2007), "Time-multiplexed multiple-constant multiplication", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. Vol. 26(9), pp. 1551-1563. IEEE.
Nedjah N and de Macedo Mourelle L (2006), "Towards minimal addition chains using ant colony optimisation", Journal of Mathematical Modelling and Algorithms. Vol. 5(4), pp. 525-543. Springer.
Dimitrov V and Cooklev T (1995), "Two algorithms for modular exponentiation using nonstandard arithmetics", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. Vol. 78(1), pp. 82-87. The Institute of Electronics, Information and Communication Engineers.
Guy R (2004), "Unsolved problems in number theory" Vol. 1, pp. 169-171. Springer Science & Business Media.
Bergeron F and Olivos J (1989), "Vectorial addition chains using Euclid's algorithm". Thesis at: Research Report, Dpt. Math., UQAM 105.
Kunihiro N and Yamamoto H (1998), "Window and extended window methods for addition chain and addition-subtraction chain", IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences. Vol. 81(1), pp. 72-81. The Institute of Electronics, Information and Communication Engineers.
Кочергин ВВ (2014), "Уточнение оценок сложности вычисления одночленов и наборов степеней в задачах Беллмана и Кнута", Дискретный анализ и исследование операций. Vol. 21(6), pp. 51-72. Институт математики им. СЛ Соболева Сибирского отделения РАН.
Bahig, H.M.; Kotb, Y. An Efficient Multicore Algorithm for Minimal Length Addition Chains. Computers 2019, 8, 23.
Užarević, Josip. Postupci konstrukcije i optimizacije adicijskih lanaca. Diss. University of Zagreb. Faculty of Electrical Engineering and Computing., 2018.
Mani, K. / Mullai, A. Generation of Addition Chain using Bacteria Foraging Optimization Algorithm 2021-02, International Journal of Engineering Trends and Technology , Vol. 69, No. 2 Seventh Sense Research Group Journals p. 32-38