# Efficient computation of addition chains

F. Bergeron; J. Berstel; S. Brlek

Journal de théorie des nombres de Bordeaux (1994)

- Volume: 6, Issue: 1, page 21-38
- ISSN: 1246-7405

## Access Full Article

top## Abstract

top## How to cite

topBergeron, F., Berstel, J., and Brlek, S.. "Efficient computation of addition chains." Journal de théorie des nombres de Bordeaux 6.1 (1994): 21-38. <http://eudml.org/doc/247531>.

@article{Bergeron1994,

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.},

author = {Bergeron, F., Berstel, J., Brlek, S.},

journal = {Journal de théorie des nombres de Bordeaux},

keywords = {addition chain; multiplication schemes; minimal length; -chains; sub- optimal addition chains; contained fraction expansions; complexity},

language = {eng},

number = {1},

pages = {21-38},

publisher = {Université Bordeaux I},

title = {Efficient computation of addition chains},

url = {http://eudml.org/doc/247531},

volume = {6},

year = {1994},

}

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

PB - Université Bordeaux I

VL - 6

IS - 1

SP - 21

EP - 38

AB - 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.

LA - eng

KW - addition chain; multiplication schemes; minimal length; -chains; sub- optimal addition chains; contained fraction expansions; complexity

UR - http://eudml.org/doc/247531

ER -

## References

top- [1] A. Brauer, On addition chains, Bull. Amer. Math. Soc.45 (1939), 736-739. Zbl0022.11106MR245JFM65.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. Zbl0812.11072
- [3] F. Bergeron, J. Berstel, S. Brlek, C. Duboc, Addition chains using continued fractions, J. Algorithms10 (1989), 403-412. Zbl0682.68025MR1006993
- [4] F. Bergeron, J. Olivos, Vectorial addition chains using Euclid's algorithm, Research Report, Dpt. Math., UQAM105 (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. Computing3 (1974), 1-10. Zbl0288.68019MR343683
- [7] P. Downey, B. Leong, R. Sethi, Computing sequences with addition chains,SIAM J. Computing10 (1981), 638-646. Zbl0462.68021MR623072
- [8] A.A. Gioia, M.V. Subbarao, M. Sugunama, The Scholz-Brauer problem in addition chains, Duke Math. J.29 (1962), 481-487. Zbl0108.04701MR140478
- [9] D.E. Knuth, The art of computer programming, vol. 2, Addison-Wesley, 1981. Zbl0477.65002MR633878
- [10] A. Schönhage, A lower bound for the length of addition chains, Theoret. Comput. Sci.1 (1975), 1-12. Zbl0307.68032MR478756
- [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. Zbl0512.68033MR702924
- [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. Zbl0346.10032MR432583
- [13] E.G. Thurber, The Scholz-Brauer problem on addition chains, Pacific J. Math.49 (1973), 229-242. Zbl0277.10040MR342487
- [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. Zbl0275.10027
- [14] A.C.-C. Yao, On the evaluation of powers, SIAM J. Comp.9 (1976), 100-103. Zbl0326.68025MR395331

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.