
Table of contents for this issue  Previous article  Next article Bergeron, F.; Berstel, J.; Brlek, S.
Efficient computation of addition chains. Journal de théorie des nombres de Bordeaux, 6 no. 1 (1994), p. 2138
Full text djvu  pdf  Reviews MR 1305286  Zbl 0812.11072  1 citation in Numdam
stable URL: http://www.numdam.org/item?id=JTNB_1994__6_1_21_0
Lookup this article on the publisher's site
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(n \log^2 n \gamma_n)$, where $\gamma_n$ is the complexity of computing the set of choices corresponding to the strategy. We also prove an analog of the ScholzBrauer conjecture.
[1] A. Brauer, On addition chains, Bull. Amer. Math. Soc. 45 (1939), 736739.
Article  MR 245  Zbl 0022.11106  JFM 65.0154.02 [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 1014 (1989), 2938. [3] F. Bergeron, J. Berstel, S. Brlek, C. Duboc, Addition chains using continued fractions, J. Algorithms 10 (1989), 403412. MR 1006993  Zbl 0682.68025 [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), 110. MR 343683  Zbl 0288.68019 [7] P. Downey, B. Leong, R. Sethi, Computing sequences with addition chains,SIAM J. Computing 10 (1981), 638646. MR 623072  Zbl 0462.68021 [8] A.A. Gioia, M.V. Subbarao, M. Sugunama, The ScholzBrauer problem in addition chains, Duke Math. J. 29 (1962), 481487.
Article  MR 140478  Zbl 0108.04701 [9] D.E. Knuth, The art of computer programming, vol. 2, AddisonWesley, 1981. MR 633878  Zbl 0477.65002 [10] A. Schönhage, A lower bound for the length of addition chains, Theoret. Comput. Sci. 1 (1975), 112. MR 478756  Zbl 0307.68032 [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), 3133. MR 702924  Zbl 0512.68033 [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), 279289. MR 432583  Zbl 0346.10032 [13] E.G. Thurber, The ScholzBrauer problem on addition chains, Pacific J. Math. 49 (1973), 229242.
Article  MR 342487  Zbl 0277.10040 [14] E.G. Thurber, On addition chains l(mn) ≤ l(n)  b and lower bounds for c(r), Duke Math. J. 40 (1973), 907913.
Article  Zbl 0275.10027 [14] A.C.C. Yao, On the evaluation of powers, SIAM J. Comp. 9 (1976), 100103. MR 395331  Zbl 0326.68025 
Copyright Cellule MathDoc 2015  Credit  Site Map
