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

Abstract

top
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 γ 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.

How to cite

top

Bergeron, 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. [1] A. Brauer, On addition chains, Bull. Amer. Math. Soc.45 (1939), 736-739. Zbl0022.11106MR245JFM65.0154.02
  2. [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. [3] F. Bergeron, J. Berstel, S. Brlek, C. Duboc, Addition chains using continued fractions, J. Algorithms10 (1989), 403-412. Zbl0682.68025MR1006993
  4. [4] F. Bergeron, J. Olivos, Vectorial addition chains using Euclid's algorithm, Research Report, Dpt. Math., UQAM105 (1989). 
  5. [5] J. Bos, M. Coster, Addition chain heuristics, Proceedings of CRYPTO 89. 
  6. [6] G.E. Collins, The computing time of the Euclidian algorithm, SIAM J. Computing3 (1974), 1-10. Zbl0288.68019MR343683
  7. [7] P. Downey, B. Leong, R. Sethi, Computing sequences with addition chains,SIAM J. Computing10 (1981), 638-646. Zbl0462.68021MR623072
  8. [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. [9] D.E. Knuth, The art of computer programming, vol. 2, Addison-Wesley, 1981. Zbl0477.65002MR633878
  10. [10] A. Schönhage, A lower bound for the length of addition chains, Theoret. Comput. Sci.1 (1975), 1-12. Zbl0307.68032MR478756
  11. [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. [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. [13] E.G. Thurber, The Scholz-Brauer problem on addition chains, Pacific J. Math.49 (1973), 229-242. Zbl0277.10040MR342487
  14. [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
  15. [14] A.C.-C. Yao, On the evaluation of powers, SIAM J. Comp.9 (1976), 100-103. Zbl0326.68025MR395331

NotesEmbed ?

top

You must be logged in to post comments.