TY  - JOUR
T1  - An Initial Solution for Addition Chain Optimization Problem
AU - Noma, Adamu Muhammad AU - Mohamed, Mohamad Afendee AU - Muhammed, Abdullah AU - Zulkarnain, Zuriati Ahmad 
JO  - Journal of Engineering and Applied Sciences
VL  - 11
IS  - 3
SP  - 640
EP  - 643
PY  - 2016
DA  - 2001/08/19
SN  - 1816-949x
DO  - jeasci.2016.640.643
UR  - https://makhillpublications.co/view-article.php?doi=jeasci.2016.640.643
KW  - Addition chain
KW  -metaheuristic
KW  -modular exponentiation
KW  -public key crypto systems
KW  -probabilistic method
AB  - Addition chain for an integer corresponds to the number of multiplications in modular exponentiation using the integer as the exponent. Modular exponentiation is the basis of public key crypto systems. Finding an optimal addition chain is an NP-complete problem. Therefore, metaheuristic have been favored in searching for the near optimal solution. In this study we proposed probabilistic method for generating an initial solution to the problem, suitable for optimization using metaheuristic. It is aimed at providing foundation for an efficient constructive metaheuristic algorithm that can find high quality solution to the problem. To ensure diversity, the proposed method generates both star and non-star steps. It generates valid addition chain with diverse steps that is not far from optimal. Test on the generated chains also shows that a suitable metaheuristic can efficiently turn them to nearest optimal ones.
ER  -