×

Efficient computation of addition chains. (English) Zbl 0812.11072

An addition chain for a positive integer \(n\) is a finite sequence of positive integers beginning with 1 and ending with \(n\), such that each term except the first is the sum of two of its predecessors. Addition chains for \(n\) generate multiplication schemes for the computation of \(x^ n\); the smallest number of multiplications required is the minimal length \(\ell(n)\) of an addition chain for \(n\).
The paper studies \(cf\)-chains as introduced by the authors and C. Duboc [J. Algorithms 10, 403-412 (1989; Zbl 0682.68025)]. These are a class of sub-optimal addition chains, obtained through continued fraction expansions for \(n/k\), where \(1<k<n\). The length of \(cf\)-chains is asymptotically equivalent to \(\log_ 2(n)\), as in \(\ell(n)\). Most of the popular effective strategies for computing addition chains are obtained as special cases of the \(cf\)-chain method. The total number of operations required for the generation of an addition chain for all positive integers up to \(n\) is \(O(n \log^ 2 n\gamma_ n)\), where \(\gamma_ n\) is the complexity of computing the set of choices corresponding to the strategy.

MSC:

11Y16 Number-theoretic algorithms; complexity
11Y65 Continued fraction calculations (number-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0682.68025
PDFBibTeX XMLCite
Full Text: DOI Numdam Numdam EuDML EMIS

References:

[1] Brauer, A., On addition chains, Bull. Amer. Math. Soc.45 (1939), 736-739. · JFM 65.0154.02
[2] Bergeron, F., Berstel, J., Brlek, S., A unifying approach to the generation of addition chains, Proc. XV Latin American Conf. on Informatics, Santiago, Chile July 10-14 (1989), 29-38. · Zbl 0812.11072
[3] F, Bergeron, J, Berstel, S, Brlek, C, Duboc, Addition chains using continued fractions, J. Algorithms10 (1989), 403-412. · Zbl 0682.68025
[4] Bergeron, F., Olivos, J., Vectorial addition chains using Euclid’s algorithm, Research Report, Dpt. Math., UQAM105 (1989).
[5] Bos, J., Coster, M., Addition chain heuristics, Proceedings of CRYPTO 89.
[6] Collins, G.E., The computing time of the Euclidian algorithm, SIAM J. Computing3 (1974), 1-10. · Zbl 0288.68019
[7] Downey, P., Leong, B., Sethi, R., Computing sequences with addition chains,SIAM J. Computing10 (1981), 638-646. · Zbl 0462.68021
[8] Gioia, A.A., Subbarao, M.V., Sugunama, M., The Scholz-Brauer problem in addition chains, Duke Math. J.29 (1962), 481-487. · Zbl 0108.04701
[9] Knuth, D.E., The art of computer programming, vol. 2, Addison-Wesley, 1981. · Zbl 0477.65002
[10] Schönhage, A., A lower bound for the length of addition chains, Theoret. Comput. Sci.1 (1975), 1-12. · Zbl 0307.68032
[11] Semba, I., 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. · Zbl 0512.68033
[12] Thurber, E.G., Addition chains and solutions of l(2n) = l(n) and l(2n - 1) = n + l(n) - 1, Discrete Math.16 (1976), 279-289. · Zbl 0346.10032
[13] Thurber, E.G., The Scholz-Brauer problem on addition chains, Pacific J. Math.49 (1973), 229-242. · Zbl 0277.10040
[14] Thurber, E.G., On addition chains l(mn) ≤ l(n) - b and lower bounds for c(r), Duke Math. J.40 (1973), 907-913. · Zbl 0275.10027
[15] Yao, A.C.-C., On the evaluation of powers, SIAM J. Comp.9 (1976), 100-103. · Zbl 0326.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.