Efficient computation of addition chains
Journal de théorie des nombres de Bordeaux, Tome 6 (1994) no. 1, pp. 21-38.

The aim of this paper is to present a unifying approach to the computation of short addition chains. Our method is based upon continued fraction expansions. Most of the popular methods for the generation of addition chains, such as the binary method, the factor method, etc..., fit in our framework. However, we present new and better algorithms. We give a general upper bound for the complexity of continued fraction methods, as a function of a chosen strategy, thus the total number of operations required for the generation of an addition chain for all integers up to n is shown to be O(nlog 2 nγ n ), where γ n is the complexity of computing the set of choices corresponding to the strategy. We also prove an analog of the Scholz-Brauer conjecture.

@article{JTNB_1994__6_1_21_0,
     author = {Bergeron, F. and Berstel, J. and Brlek, S.},
     title = {Efficient computation of addition chains},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {21--38},
     publisher = {Universit\'e Bordeaux I},
     volume = {6},
     number = {1},
     year = {1994},
     mrnumber = {1305286},
     zbl = {0812.11072},
     language = {en},
     url = {http://archive.numdam.org/item/JTNB_1994__6_1_21_0/}
}
TY  - JOUR
AU  - Bergeron, F.
AU  - Berstel, J.
AU  - Brlek, S.
TI  - Efficient computation of addition chains
JO  - Journal de théorie des nombres de Bordeaux
PY  - 1994
SP  - 21
EP  - 38
VL  - 6
IS  - 1
PB  - Université Bordeaux I
UR  - http://archive.numdam.org/item/JTNB_1994__6_1_21_0/
LA  - en
ID  - JTNB_1994__6_1_21_0
ER  - 
%0 Journal Article
%A Bergeron, F.
%A Berstel, J.
%A Brlek, S.
%T Efficient computation of addition chains
%J Journal de théorie des nombres de Bordeaux
%D 1994
%P 21-38
%V 6
%N 1
%I Université Bordeaux I
%U http://archive.numdam.org/item/JTNB_1994__6_1_21_0/
%G en
%F JTNB_1994__6_1_21_0
Bergeron, F.; Berstel, J.; Brlek, S. Efficient computation of addition chains. Journal de théorie des nombres de Bordeaux, Tome 6 (1994) no. 1, pp. 21-38. http://archive.numdam.org/item/JTNB_1994__6_1_21_0/

[1] A. Brauer, On addition chains, Bull. Amer. Math. Soc. 45 (1939), 736-739. | JFM | MR | Zbl

[2] F. Bergeron, J. Berstel, S. Brlek, A unifying approach to the generation of addition chains, Proc. XV Latin American Conf. on Informatics, Santiago, Chile July 10-14 (1989), 29-38.

[3] F. Bergeron, J. Berstel, S. Brlek, C. Duboc, Addition chains using continued fractions, J. Algorithms 10 (1989), 403-412. | MR | Zbl

[4] F. Bergeron, J. Olivos, Vectorial addition chains using Euclid's algorithm, Research Report, Dpt. Math., UQAM 105 (1989).

[5] J. Bos, M. Coster, Addition chain heuristics, Proceedings of CRYPTO 89.

[6] G.E. Collins, The computing time of the Euclidian algorithm, SIAM J. Computing 3 (1974), 1-10. | MR | Zbl

[7] P. Downey, B. Leong, R. Sethi, Computing sequences with addition chains,SIAM J. Computing 10 (1981), 638-646. | MR | Zbl

[8] A.A. Gioia, M.V. Subbarao, M. Sugunama, The Scholz-Brauer problem in addition chains, Duke Math. J. 29 (1962), 481-487. | MR | Zbl

[9] D.E. Knuth, The art of computer programming, vol. 2, Addison-Wesley, 1981. | MR | Zbl

[10] A. Schönhage, A lower bound for the length of addition chains, Theoret. Comput. Sci. 1 (1975), 1-12. | MR | Zbl

[11] I. Semba, Systematic method for determining the number of multiplications required to compute xm, where m is a positive integer, J. Information Proc. 6 (1983), 31-33. | MR | Zbl

[12] E.G. Thurber, Addition chains and solutions of l(2n) = l(n) and l(2n - 1) = n + l(n) - 1, Discrete Math. 16 (1976), 279-289. | MR | Zbl

[13] E.G. Thurber, The Scholz-Brauer problem on addition chains, Pacific J. Math. 49 (1973), 229-242. | MR | Zbl

[14] E.G. Thurber, On addition chains l(mn) ≤ l(n) - b and lower bounds for c(r), Duke Math. J. 40 (1973), 907-913. | Zbl

[14] A.C.-C. Yao, On the evaluation of powers, SIAM J. Comp. 9 (1976), 100-103. | MR | Zbl