An efficient simulated annealing algorithm for short addition sequences

Hazem M. Bahig; Mohamed A.G. Hazber; Hatem M. Bahig; Hazem M. Bahig; Mohamed A.G. Hazber; Hatem M. Bahig

doi:10.3934/math.2024540

AIMS Mathematics

2024, Volume 9, Issue 5: 11024-11038. doi: 10.3934/math.2024540

Previous Article Next Article

Research article Special Issues

An efficient simulated annealing algorithm for short addition sequences

1.
Department of Information and Computer Science, College of Computer Science and Engineering, University of Ha'il, Ha'il 81481, KSA
2.
Department of Mathematics, Faculty of Science, Ain Shams University, Cairo, Egypt

Received: 20 January 2024 Revised: 03 March 2024 Accepted: 11 March 2024 Published: 20 March 2024
MSC : 11Bxx, 90C59, 68T20

Let $ N = \left\{{n}_{1}, {n}_{2}, \;\dots , {n}_{k}\right\} $ be a finite set of positive numbers. The problem of finding the minimal number of additions required to compute all elements of N starting from 1 (called the addition sequence problem) is NP-complete. It is equivalent to finding the minimum number of multiplications needed to compute a group exponentiation $ {g}^{{n}_{1}}, {g}^{{n}_{2}}, \;\dots , {g}^{{n}_{k}} $, where g is an element in a group. This paper aims to propose a new metaheuristic algorithm using a simulated annealing strategy to generate a short addition sequence. The performance of the proposed algorithm is measured by considering two parameters: The size of N and the domain of $ {n}_{\mathrm{i}}, 1\le i\le k $. The proposed algorithm is a new trade-off between the length of the generated addition sequence and the average running time of generating addition sequences. It sometimes produces longer addition sequences than exact algorithms that are slower, and it is slower than suboptimal algorithms that produce longer addition sequences.
- addition sequence,
- addition chain,
- modular exponentiation,
- simulated annealing,
- heuristic algorithm,
- optimization
Citation: Hazem M. Bahig, Mohamed A.G. Hazber, Hatem M. Bahig. An efficient simulated annealing algorithm for short addition sequences[J]. AIMS Mathematics, 2024, 9(5): 11024-11038. doi: 10.3934/math.2024540

Related Papers:

Abstract

Let $ N = \left\{{n}_{1}, {n}_{2}, \;\dots , {n}_{k}\right\} $ be a finite set of positive numbers. The problem of finding the minimal number of additions required to compute all elements of N starting from 1 (called the addition sequence problem) is NP-complete. It is equivalent to finding the minimum number of multiplications needed to compute a group exponentiation $ {g}^{{n}_{1}}, {g}^{{n}_{2}}, \;\dots , {g}^{{n}_{k}} $, where g is an element in a group. This paper aims to propose a new metaheuristic algorithm using a simulated annealing strategy to generate a short addition sequence. The performance of the proposed algorithm is measured by considering two parameters: The size of N and the domain of $ {n}_{\mathrm{i}}, 1\le i\le k $. The proposed algorithm is a new trade-off between the length of the generated addition sequence and the average running time of generating addition sequences. It sometimes produces longer addition sequences than exact algorithms that are slower, and it is slower than suboptimal algorithms that produce longer addition sequences.

References

[1]	D. E. Knuth, The art of computer programming: Seminumerical algorithms, 2, 3Ed. Addison-Wesley, Reading, 461–485, (1997).
[2]	A. Menezes, P. van Oorschot, S, Vanstone. Handbook of applied cryptography, CRC Press, Boca Raton, 1996 (Chapter 14).
[3]	A. Yao, On the evaluation of powers, SIAM J. Comput., 5 (1976) 100–103. https://doi.org/10.1137/0205008 doi: 10.1137/0205008
[4]	D. Bleichenbacher, Efficiency and security of cryptosystems based on number theory, chapter 4. A Docotor Thesis, Swiss Federal Institue of Technology Zurich, Zurich, 1996. https://www.research-collection.ethz.ch/handle/20.500.11850/142613
[5]	R. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM, 21 (1978), 120–126. https://doi.org/10.1145/359340.359342 doi: 10.1145/359340.359342
[6]	H. Bahig, D. I. Nassr, Generating a shortest B-chain using multi-gpus, Inf. Sci. Lett., 11 (2022), 745–750. https://doi.org/10.18576/isl/110307 doi: 10.18576/isl/110307
[7]	E. J. Guzmán-Trampe, N. Cruz-Cortés, L. J. Dominguez Perez, D. Ortiz-Arroyo, Francisco Rodríguez-Henríquez, Low-cost addition–subtraction sequences for the final exponentiation in pairings, Finite Fields Th. App., 29 (2014), 1–17, https://doi.org/10.1016/j.ffa.2014.02.009 doi: 10.1016/j.ffa.2014.02.009
[8]	E. Thurber, N. Clift, Addition chains, vector chains, and efficient computation, Discret. Math., 344 (2021), 112200. https://doi.org/10.18576/isl/110307 doi: 10.18576/isl/110307
[9]	P. Downey, B. Leong, B. R. Sethi, Computing sequences with addition chains, SIAM J. Comput., 10 (1981), 638–646. https://doi.org/10.18576/isl/110307 doi: 10.18576/isl/110307
[10]	C. Laih, S. Yen, L. Harn, Two efficient server-aided secret computation protocols based on the addition sequence, In: Advances in cryptology-ASIACRYPT'91, 450–459, 1991. https://doi.org/10.18576/isl/110307
[11]	C. Laih, S. Yen, Secure addition sequence and its applications on the server-aided secret computation protocols, In: Advances in cryptology-AUSCRYPT'92, Lecture Notes in Computer Science, 718 (1992), 219–229. https://doi.org/10.1007/3-540-57220-1_64
[12]	P. Nguyen, I. E. Shparlinski, On the insecurity of a server-aided RSA protocol. In: Boyd, C. (eds) Advances in Cryptology—ASIACRYPT 2001. ASIACRYPT 2001. Lecture Notes in Computer Science, vol 2248, Springer, Berlin, Heidelberg. (2001). https://doi.org/10.1007/3-540-45682-1_2
[13]	X. Chen, J. Li, J. Ma, Q. Tang, W. Lou, New algorithms for secure outsourcing of modular exponentiations, IEEE T. Parallel Distr., 25 (2014), 2386–2396, https://doi.org/10.1109/TPDS.2013.180 doi: 10.1109/TPDS.2013.180
[14]	C. Bouillaguet, F. Martinez, D. Vergnaud, Cryptanalysis of modular exponentiation outsourcing protocols, Comput. J., 65 (2022), 2299–2314. https://doi.org/10.1093/comjnl/bxab066 doi: 10.1093/comjnl/bxab066
[15]	C. Chevalier, F. Laguillaumie, D. Vergnaud, Privately outsourcing exponentiation to a single server: Cryptanalysis and optimal constructions, Computer Security–ESORICS 2016,261–278. https://doi.org/10.1007/978-3-319-45744-4_13
[16]	G. Di Crescenzo, M. Khodjaeva, D. Kahrobaei, V. Shpilrain, Delegating a product of group exponentiations with application to signature schemes, J. Math. Cryptol., 14 (2020), 438–459. https://doi.org/10.1515/jmc-2019-0036 doi: 10.1515/jmc-2019-0036
[17]	S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671–680. https://doi.org/10.1515/jmc-2019-0036 doi: 10.1515/jmc-2019-0036
[18]	H. Bahig, H. Bahig, A new strategy for generating shortest addition sequences, Computing, 91 (2011), 285–306. https://doi.org/10.1515/jmc-2019-0036 doi: 10.1515/jmc-2019-0036
[19]	F. Bergeron, J. Berstel, S. Brlek, Efficient computation of addition chains, J. Theor. Nombres Bord., 6 (1994), 21–38. https://doi.org/10.5802/jtnb.104 doi: 10.5802/jtnb.104
[20]	H. 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
[21]	K. Fathy, H. Bahig, M. Farag, Speeding up multi-exponentiation algorithm on a multicore system, J. Egypt. Math. Society, 26 (2018), 235–244. https://doi.org/10.21608/joems.2018.2540.1008 doi: 10.21608/joems.2018.2540.1008
[22]	J. Bos, M. Coster, Addition chain heuristics. In: Brassard, G. (eds) Advances in Cryptology—CRYPTO' 89 Proceedings. CRYPTO 1989, Lecture Notes in Computer Science, 435. Springer, New York, NY. https://doi.org/10.1007/0-387-34805-0_37
[23]	A. Enge, W. Hart, F. Johansson, Short addition sequences for theta functions, J. Integer Seq., 2 (2018), 1–34.
[24]	N. Nedjah, L. de Macedo Mourelle, Efficient pre-processing for large window-based modular exponentiation using ant colony, In: Khosla, R., Howlett, R. J., Jain, L. C. (eds) Knowledge-Based Intelligent Information and Engineering Systems. KES 2005. Lecture Notes in Computer Science, vol. 3684. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11554028_89
[25]	M. Abbas, O. Gustafsson, Integer linear programming modeling of addition sequences with additional constraints for evaluation of power terms, 2023. https://doi.org/10.48550/arXiv.2306.15002
[26]	H. M. Bahig, K. A. Alutaibi, M. A. Mahdi, A. AlGhadhban, H. M. Bahig, An evolutionary algorithm for short addition chains, Int. J. Adv. Comput. Sci. Appl., 11 (2020), 340–352. http://dx.doi.org/10.14569/IJACSA.2020.0111258 doi: 10.14569/IJACSA.2020.0111258
[27]	K. Gao, F. Yang, M. Zhou, Q. Pan, P. N. Suganthan, Flexible job-shop rescheduling for new job insertion by using discrete jaya algorithm, IEEE T. Cybernetics, 49 (2019), 1944–1955. https://doi.org/10.1109/TCYB.2018.2817240 doi: 10.1109/TCYB.2018.2817240

Reader Comments

Your name:*

Email:*
© 2024 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)