Addition-multiplication chains with one small step

S. Tarek; Hatem M. Bahig; M. Anwar; S. Tarek; Hatem M. Bahig; M. Anwar

doi:10.3934/Math.2026667

AIMS Mathematics

2026, Volume 11, Issue 6: 16235-16263. doi: 10.3934/Math.2026667

Previous Article Next Article

Research article Special Issues

Addition-multiplication chains with one small step

1.
Department of Mathematics, Faculty of Science, Ain Shams University, Cairo, Egypt
2.
College of Computer and Information Sciences, Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, Saudi Arabia

Received: 15 March 2026 Revised: 19 May 2026 Accepted: 29 May 2026 Published: 08 June 2026
MSC : 11Y55, 68Q25, 68R01

An addition-multiplication chain of length $ l $ for a positive integer $ n $ is a monotonic increasing sequence $ 1 = a_0 < a_1 < \ldots < a_l = n $ of positive integers, such that for each $ 1\leq i \leq l, $ we have $ a_i = {a_j} + {a_k} \ \text{or} \ a_i = {a_j} \times {a_k}, $ where $ 0 \leq k \leq j \leq i-1. $ In this paper, we establish upper bounds for each element in any AM-chain based on the number of squaring steps and the distribution of non-squaring steps preceding the given element. Moreover, we get additional upper bounds independent of the distribution of non-squaring steps. These bounds yield a new upper bound for the number of non-squaring steps in any AM-chain. Finally, we determine all AM-chains that include exactly one small step and, as a consequence, compute the shortest lengths $ \ell_{AM}(.) $ of certain integers.
- addition chains,
- addition-multiplication chains,
- shortest length,
- small step
Citation: S. Tarek, Hatem M. Bahig, M. Anwar. Addition-multiplication chains with one small step[J]. AIMS Mathematics, 2026, 11(6): 16235-16263. doi: 10.3934/Math.2026667

Related Papers:

Abstract

An addition-multiplication chain of length $ l $ for a positive integer $ n $ is a monotonic increasing sequence $ 1 = a_0 < a_1 < \ldots < a_l = n $ of positive integers, such that for each $ 1\leq i \leq l, $ we have $ a_i = {a_j} + {a_k} \ \text{or} \ a_i = {a_j} \times {a_k}, $ where $ 0 \leq k \leq j \leq i-1. $ In this paper, we establish upper bounds for each element in any AM-chain based on the number of squaring steps and the distribution of non-squaring steps preceding the given element. Moreover, we get additional upper bounds independent of the distribution of non-squaring steps. These bounds yield a new upper bound for the number of non-squaring steps in any AM-chain. Finally, we determine all AM-chains that include exactly one small step and, as a consequence, compute the shortest lengths $ \ell_{AM}(.) $ of certain integers.

References

[1]	D. E. Knuth, The art of computer programming: Sorting and searching, Volume 3, 1998.
[2]	A. J. Menezes, P. C. Van Oorschot, S. A. Vanstone, Handbook of applied cryptography, Boca Raton: CRC Press, 2018. https://doi.org/10.1201/9780429466335
[3]	P. J. Downey, B. L. Leong, R. Sethi, Computing sequences with addition chains, SIAM J. Comput., 10 (1981), 638–646. https://doi.org/10.1137/0210047 doi: 10.1137/0210047
[4]	D. M. Gordon, A survey of fast exponentiation methods, J. Algorithms, 27 (1998), 129–146. https://doi.org/10.1006/jagm.1997.0913 doi: 10.1006/jagm.1997.0913
[5]	J. von zur Gathen, M. Nöcker, Computing special powers in finite fields, Math. Comp., 73 (2004), 1499–1523. https://doi.org/10.1090/S0025-5718-03-01599-0 doi: 10.1090/S0025-5718-03-01599-0
[6]	K. Järvinen, V. Dimitrov, R. Azarderakhsh, A generalization of addition chains and fast inversions in binary fields, IEEE T. Comput., 64 (2014), 2421–2432. https://doi.org/10.1109/TC.2014.2375182 doi: 10.1109/TC.2014.2375182
[7]	H. M. Bahig, H. M. Bahig, A new strategy for generating shortest addition sequences, Computing, 91 (2011), 285–306. https://doi.org/10.1007/s00607-010-0119-7 doi: 10.1007/s00607-010-0119-7
[8]	H. M. Bahig, M. Hazber, H. M. Bahig, An efficient simulated annealing algorithm for short addition sequences, AIMS Math., 9 (2024), 11024–11038. https://doi.org/10.3934/math.2024540 doi: 10.3934/math.2024540
[9]	R. J. Lipton, D. Dobkin, Complexity measures and hierarchies for the evaluation of integers and polynomials, Theor. Comput. Sci., 3 (1976), 349–357. https://doi.org/10.1016/0304-3975(76)90051-7 doi: 10.1016/0304-3975(76)90051-7
[10]	F. Morain, J. Olivos, Speeding up the computations on an elliptic curve using addition–subtraction chains, RAIRO Theor. Inf. Appl., 24 (1990), 531–543. https://doi.org/10.1051/ita/1990240605311 doi: 10.1051/ita/1990240605311
[11]	H. Volger, Some results on addition/subtraction chains, Inform. Process. Lett., 20 (1985), 155–160. https://doi.org/10.1016/0020-0190(85)90085-7 doi: 10.1016/0020-0190(85)90085-7
[12]	H. M. Bahig, On a generalization of addition chains: Addition-multiplication chains, Discrete Math., 308 (2008), 611–616. https://doi.org/10.1016/j.disc.2007.04.015 doi: 10.1016/j.disc.2007.04.015
[13]	H. Bahig, A. Mahran, Efficient generation of shortest addition-multiplication chains, J. Egypt. Math. Soc., 26 (2018), 3. https://doi.org/10.21608/joems.2018.2691.1052 doi: 10.21608/joems.2018.2691.1052
[14]	H. M. Bahig, Star reduction among minimal length addition chains, Computing, 91 (2011), 335–352. https://doi.org/10.1007/s00607-010-0122-z doi: 10.1007/s00607-010-0122-z
[15]	H. M. Bahig, Y. Kotb, An efficient multicore algorithm for minimal length addition chains, Computers, 8 (2019), 23. https://doi.org/10.3390/computers8010023 doi: 10.3390/computers8010023
[16]	F. Bergeron, J. Berstel, S. Brlek, Efficient computation of addition chains, J. Theor. Nombr. Bordx., 6 (1994), 21–38. https://doi.org/10.5802/jtnb.104 doi: 10.5802/jtnb.104
[17]	E. G. Thurber, N. M. Clift, Addition chains, vector chains, and efficient computation, Discrete Math., 344 (2021), 112200. https://doi.org/10.1016/j.disc.2020.112200 doi: 10.1016/j.disc.2020.112200
[18]	E. G. Thurber, Efficient generation of minimal length addition chains, SIAM J. Comput., 28 (1999), 1247–1263. https://doi.org/10.1137/S0097539795295663 doi: 10.1137/S0097539795295663
[19]	F. Bergeron, J. Berstel, S. Brlek, C. Duboc, Addition chains using continued fractions, J. Algorithms, 10 (1989), 403–412. https://doi.org/10.1016/0196-6774(89)90036-9 doi: 10.1016/0196-6774(89)90036-9
[20]	H. M. Bahig, Y. Kotb, A multicore exact algorithm for addition sequence, J. Comput., 14 (2019), 79–87. https://doi.org/10.17706/jcp.14.1.79-87 doi: 10.17706/jcp.14.1.79-87
[21]	N. Nedjah, L. de Macedo Mourelle, Minimal addition chain for efficient modular exponentiation using genetic algorithms, In: Developments in Applied Artificial Intelligence, Berlin: Springer, 2002. https://doi.org/10.1007/3-540-48035-8_10
[22]	H. Altman, Internal structure of addition chains: Well-ordering, Theor. Comput. Sci., 721 (2018), 54–69. https://doi.org/10.1016/j.tcs.2017.12.002, doi: 10.1016/j.tcs.2017.12.002

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)