Search and download archives of mathematical journals

 
 
  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. 21-38
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

Abstract

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 Scholz-Brauer conjecture.

Bibliography

[1] A. Brauer, On addition chains, Bull. Amer. Math. Soc. 45 (1939), 736-739.
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 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 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), 1-10.  MR 343683 |  Zbl 0288.68019
[7] P. Downey, B. Leong, R. Sethi, Computing sequences with addition chains,SIAM J. Computing 10 (1981), 638-646.  MR 623072 |  Zbl 0462.68021
[8] A.A. Gioia, M.V. Subbarao, M. Sugunama, The Scholz-Brauer problem in addition chains, Duke Math. J. 29 (1962), 481-487.
Article |  MR 140478 |  Zbl 0108.04701
[9] D.E. Knuth, The art of computer programming, vol. 2, Addison-Wesley, 1981.  MR 633878 |  Zbl 0477.65002
[10] A. Schönhage, A lower bound for the length of addition chains, Theoret. Comput. Sci. 1 (1975), 1-12.  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), 31-33.  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), 279-289.  MR 432583 |  Zbl 0346.10032
[13] E.G. Thurber, The Scholz-Brauer problem on addition chains, Pacific J. Math. 49 (1973), 229-242.
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), 907-913.
Article |  Zbl 0275.10027
[14] A.C.-C. Yao, On the evaluation of powers, SIAM J. Comp. 9 (1976), 100-103.  MR 395331 |  Zbl 0326.68025
Copyright Cellule MathDoc 2014 | Credit | Site Map