Addition chain length minimization with evolutionary programming
Saúl Domínguez-Isidro, Efrén Mezura‐Montes, Luis-Guillermo Osorio-Hernández · 2011
This paper presents the use of an evolutionary metaheuristic algorithm called evolutionary programming to minimize the length of addition chains, which is an NP-hard problem. Addition chains are used in modular exponentiation for data encryption and decryption public-key cryptosystems, such as RSA, DSA and others. The algorithm starts with a population of feasible addition chains. After that, the combination of a mutation operator, which allows each individual to generate a feasible offspring, and a replacement process based on stochastic encounters provides a simple approach which is tested on exponents with different features. The proposed algorithm is able to find competitive results with respect to other nature-inspired metaheuristic approaches but with a lower number of evaluations per run.