Rechercher dans le site

Table des matières de ce fascicule | Article précédent | Article suivant
F. Bergeron; J. Berstel; S. Brlek
Journal de théorie des nombres de Bordeaux, 6 no. 1 (1994), p. 21-38, doi: 10.5802/jtnb.104
Article PDF | Analyses MR 1305286 | Zbl 0812.11072

Résumé - 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.

Bibliographie

[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