Generation of Addition Chain using Bacteria Foraging Optimization Algorithm

  IJETT-book-cover  International Journal of Engineering Trends and Technology (IJETT)          
© 2021 by IJETT Journal
Volume-69 Issue-2
Year of Publication : 2021
Authors : Dr.K.Mani, A. Mullai
DOI :  10.14445/22315381/IJETT-V69I2P205


MLA Style: Dr.K.Mani, A. Mullai"Generation of Addition Chain using Bacteria Foraging Optimization Algorithm" International Journal of Engineering Trends and Technology 69.2(2021):32-38. 

APA Style:Dr.K.Mani, A. Mullai. Generation of Addition Chain using Bacteria Foraging Optimization Algorithm  International Journal of Engineering Trends and Technology, 69(2),32-38.

In many number-theoretic cryptographic algorithms, encryption and decryption are of the form xn mod p where x, n and p are integers. When exponentiation operation is involved in many cryptosystems, it takes more time than any normal arithmetic operations. The computation time can be reduced by using repeated multiplications rather than using exponential operation. This can also be further reduced by using addition chain. Modular exponentiation with addition chain is used to determine the correct sequence of multiplications. There exist several algorithms in the literature to generate the optimal addition chain for the given integer. A novel bacteria foraging optimization algorithm based addition chain has been proposed, and it is verified with the existing state of art of addition chain algorithms like genetic algorithm, evolutionary programming etc., in this paper.

[1] N Koblitz, Elliptic Curve Cryptosystems, Mathematics of Computation, 48(1982) 203-209.
[2] I Blake, G Seroussi and NP Smart, Elliptic Curves in Cryptography, Ser. London Math. Soc. Lecture Note Series, Cambridge Univ. Press,1999.
[3] Hugo Volger, Some Results on Addition/Subtraction Chains, Information Processing Letter, Elsevier, 1985.
[4] Y H Tsai andY H Chin, “A Study of Some Addition Chain Problems”, International Journal of Computer Mathematics, 22(02) (1987) 117-134.
[5] R Begeron, J Berstel, S Brlek, and C Duboc, Addition Chains Using Continued Fractions, Journal of Algorithms, Elsevier, 10(1989) 403-412.
[6] Bergeron,J Bersteland SBrlek, Efficient Computation Of Addition Chains”, Journalde Théorie des Nombresde Bordeaux, 6(1)(1994) 21-38.
[7] Donald E Knuth, The Art of Computer Programming, Seminumerical Algorithms, 2(3), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA,1997.
[8] Gordon DM, A Survey of Fast Exponentiation Methods, Journal of Algorithms, 27 (1998).
[9] H Zantema, Minimizing Sums of Addition Chains, Journal of Algorithms, Elsevier, 12(2) (1999) 281-307.
[10] Noboru Kunihiro and Hirosuke Yamamoto, New Methods for Generation of Short Addition Chains, IEICE Transactions Fundamental, 83(1)(2000).
[11] Nareli Cruz-Cortés, Francisco Rodriguez-Henriquez, RaúlJuárez-Morales and Carlos A Coello- Coello, Finding Optimal Addition Chains Using a Genetic Algorithm Approach, Springer- Verlag, (2005) 208-215.
[12] N Cruz-Cortes, F Rodriguez-Henriquez, and C A Coello-Coello, An Artificial Immune System Heuristic for Generating Short Addition Chains, IEEE Transactions on Evolutionary Computation, 6(2005) 252–280.
[13] Raveen R Goundar, Ken-ichiShiota, M Toyonaga, New Strategy for Doubling - Free Short Addition-Subtraction Chain, Mathematics,2008.
[14] AlejandroLe´on-Javier,NareliCruz-Cort´es,MarcoAMoreno-Armend´ariz,and SandraOrantes- Jim´ enez, Finding Minimal Addition Chains with a Particle Swarm Optimization Algorithm, Advances in Artificial Intelligence, Springer, (2009) 680-691.
[15] Swagatam Das, ArijitBiswas, Sambarta Das gupta, and Ajith Abraham, “Bacterial Foraging Optimization Algorithm: Theoretical Foundations, Analysis, and Applications”, Foundations of Computational Intelligence,, Springer-Verlag Berlin Heidelberg, 3 SCI 203(2009) 23–55.
[16] Mohamed M Abd- Eldayem, EhabT Alnfrawy, and AlyA Fahmya, Addition-Subtraction Chain for 160-bit Integers by using 2’s Complex N Cruz-Cortés, F Rodríguez-Henríquez, and C A Coello-Coello, Addition Chain Length Minimization With Evolutionary Programming, Proceedings of Genetic and Evolutionary Computation Conference (GECCO) ACM digital Library, (2011).
[17] S Domínguez-Isidro and E Mezura-Montes, An Evolutionary Programming Algorithm to Find Minimal AdditionChains, I Congreso Internacional deIngeniería Electrónica, Instrumentación y Computación, de Juniodel, Minatitlán Veracruz, México,2011.
[18] Maurice Mignotte, A Note on Addition Chains, International Journal of Algebra, 5(6)( 2011).
[19] Neill Michael Clift, Calculating Optimal Addition Chains”, Journal of Computing, Springer, 91 (2011) 265–284.
[20] Arturo Rodriguez-Cristerna and Jose Torres-Jimenez, A Genetic Algorithm for the Problem of Minimal Brauer Chains for Large Exponents, Soft Computing Applications in Optimization, Control, and Recognition, Springer, (2013) 27-5.
[21] K. Mani, Generation of Addition Chain using Deterministic Division Based Method, International Journal of Computer Science & Engineering Technology, 4(05) (2013) 553- 560.
[22] Om Prakash Verma, Rashmi Jain, and Vindhya Chhabra, Solution of Travelling Salesman Problem Using Bacteria Foraging Optimization Algorithm, International Journal of Swarm Intelligence, Inder science publisher, 1(2) (2014).
[23] Brian Koziel, Reza Azarderakhsh, David Jaoand Mehran Mozaari-Kermani, On Fast Calculation of Addition Chains for Isogeny - Based Cryptography, Inscrypt 2016, IACR Cryptology,2016.
[24] Adamu Muhammad Noma, Abdullah Muhammed, Mohamad Afendee Mohamed, and ZuriatiAhmad Zulkarnain. A Review on Heuristics for Addition Chain Problem: Towards Efficient Public-Key Cryptosystem, Journal of Computer Science, 13(2017) 275-289.
[25] K Mani, M Viswambari, A New Method of Generating Optimal Addition Chain Based on Graph, International Journal of Mathematical Sciences and Computing, 2(2017) 37-54.
[26] P Anuradha Kameswari and B Ravitheja, Addition Chain For Lucas Sequences With Fast Computation Method, International Journal of Applied Engineering Research, 13(11) (2018) 9413–9419.
[27] Stjepan Picek, Carlos A Coello Coello, Domagoj Jakobovic and NeleMentens, Finding Short And Implementation - Friendly Addition Chains With Evolutionary Algorithms, Journal of Heuristics, 24 (2018) 457-481.
[28] Aaron Hutchinson and Koray Karabina, Constructing Multidimensional Differential Addition Chains and Their Applications, Springer,Journal of Cryptographic Engineering, 9(2019) 1- 19.
[29] Dustin Moody and Amadou Tall, On Addition-Subtraction Chains of Numbers With Low Hamming Weight”, Number Theory Mathematics, 25(2019) 155-168.
[30] Hazem M. Bahig, and Yasser Kotb, An Efficient Multicore Algorithm for Minimal Length Addition Chains, Computers, MDBI, 8(2019).
[31] A Mullai and K Mani, Enhancing The Security In RSA and Elliptic Curve Cryptography Based on Addition Chain Using Simplified Swarm Optimization and Particle Swarm Optimization For Mobile Devices, International Journal of Information Technology, Springer, (2020).
[32] Narendra Mohan Lifetime Enhancement of Sensor Nodes Based On Optimized Sink Node Placement Approach, International Journal of Engineering Trends and Technology 68.10(2020):10-23.

Addition Chain, RSA, ECC, PSO, SSO, BFOA, Optimization.