International Journal of Mathematical Sciences and Computing (IJMSC)
IJMSC Vol. 3, No. 2, 8 Apr. 2017
Cover page and Table of Contents: PDF (size: 516KB)
A New Method of Generating Optimal Addition Chain Based on Graph
Full Text (PDF, 516KB), PP.37-54
Views: 0 Downloads: 0
Author(s)
K.Mani
1
M. Viswambari
1,*
Index Terms
Optimal Addition Chain, Graph, Conjectures, All Possible Addition Chain, Minimal Addition Chain
Abstract
In many number theoretic cryptographic algorithms, encryption and decryption is of the form xn mod p, where n and p are integers. Exponentiation normally takes more time than any arithmetic operations. It may be performed by repeated multiplication which will reduce the computational time. To reduce the time further fewer multiplications are performed in computing the same exponentiation operation using addition chain. The problem of determining correct sequence of multiplications requires in performing modular exponentiation can be elegantly formulated using the concept of addition chains. There are several methods available in literature in generating the optimal addition chain. But novel graph based methods have been proposed in this paper to generate the optimal addition chain where the vertices of the graph represent the numbers used in the addition chain and edges represent the move from one number to another number in the addition chain. Method 1 termed as GBAPAC which generates all possible optimum addition chains for the given integer n by considering the edge weight of all possible numbers generated from every number in addition chain. Method 2 termed as GBMAC which generates the minimum number of optimum addition chains by considering mutually exclusive edges starting from every number. Further, the optimal addition chain generated for an integer using the proposed methods are verified with the conjectures which already existed in the literature with respect to addition chains.
Cite This Paper
K. Mani, M. Viswambari,"A New Method of Generating Optimal Addition Chain Based on Graph", International Journal of Mathematical Sciences and Computing(IJMSC), Vol.3, No.2, pp.37-54, 2017.DOI: 10.5815/ijmsc.2017.02.04
Reference
[1]D. Knuth, Art of Computer Programming–Semi Numerical Algorithms, Vol. 2, Addison-Wesley, Third Edition, 1998.
[2]Edward G. Thurber, "Efficient Generation of Minimal Length Addition Chains", society for industrial and applied mathematics, SIAM J. Comput., Vol. 28, no. 4, pp. 1247-1263, March 1999.
[3]Noboru Kunihiro et al., "New Methods for Generating Short Addition Chains", IEICE TRANS. Fundamentals, Vol. E83- A, No.1, January 2000.
[4]Peter Tummeltshammer and James C. Hoe and Markus Puschel, "Multiple Constant Multiplication by Time Multiplexed Mapping of Addition Chains", DAC'04, June 2004.
[5]Nareli Cruz-Cortés, et al., "Finding Optimal Addition Chains Using a Genetic Algorithm Approach", Springer-Verlag, 2005, pp. 208-215.
[6]Daniel J. Bernstein, "Differential addition chains", available at: https://cr.yp.to/ecdh/diffchain-20060219.pdfhttps://cr.yp.to/ecdh/diffchain, February 2006.
[7]Younho Lee et al., "Expansion of Sliding Window Method for Finding Shorter Addition/Subtraction-Chains", International Journal of Network Security, Vol.2, No.1, PP.34–40, Jan. 2006.
[8]Nareli Cruz- Cortes et al., "An Artificial Immune System Heuristic for Generating Short Addition Chains", IEEE Transactions on Evolutionary Computation, 2007.
[9]Raveen R. Goundar et al., "New Strategy for Doubling-Free Short Addition-Subtraction Chain", Applied Mathematics & Information Sciences, 2(2) (2008), 123–133.
[10]Raveen R. Goundar et al., "SPA Resistant Scalar Multiplication using Golden Ratio Addition Chain Method", IAENG International Journal of Applied Mathematics, 38:2, IJAM, June 2008.
[11]Fabien Herbaut et al., "Random Euclidean Addition Chain Generation and Its Application to Point Multiplication", INDOCRYPT 2010, Springer-Verlag Berlin Heidelberg 2010.
[12]Maurice MIGNOTTE and Amadou TALL, "A Note on Addition Chains", International Journal of Algebra, Vol. 5, 2011, no. 6, 269 – 274.
[13]Dominguez- Isidro and E. Mezura-Montes, "An Evolutionary Programming Algorithm to Find Minimal Addition Chains", I Congreso Internacional de Ingenieria Electronica, Intrumentacion Y Computacion, 22 al 24 de Junio del, July 2011.
[14]Neill Michael Clift, "Calculating optimal addition chains", available at: Springerlink.com, September 2011.
[15]Amadou TALL, "A generalization of the Lucas addition chains", available at: https://eprint.iacr.org/2011/378.pdf, 2011.
[16]M. A. Mohamed and K. A. Mohd Atan, "Rule Based Representation of Integer for a New Addition Chain Method, Applied Mathematical Sciences, Vol. 6, 2012, no. 30, 1497 – 1503.
[17]Amadou Tall and Ali Yassin Sanghare, "Efficient computation of addition-subtraction chains using generalized continued Fractions, International Journal of Applied Mathematical Research, IJAMR, 2013.
[18]Mr. K. Mani, "Generation of Addition Chain using Deterministic Division Based Method", International Journal of Computer Science & Engineering Technology (IJCSET), ISSN: 2229-3345 Vol. 4 No. 05 May 2013.
[19]Yara Elias and Pierre McKenzie, "On Generalized Addition Chains", Integers 14, available at: https://www.emis.de/journals/Integers/papers/o16/o16.pdf, March 2014.
[20]MA Mohamed and MR MD SAID, "A Hybrid Addition Chain Method for Faster Scalar Multiplication", WSEAS Transactions on Communications, E-ISSN: 2224-2864, Volume 14, 2015.
[21]Sajal Chakroborty, M. Babul Hasan,"A Proposed Technique for Solving Scenario Based Multi-Period Stochastic Optimization Problems with Computer Application", International Journal of Mathematical Sciences and Computing (IJMSC), Vol.2, No.4, pp.12-23, 2016.