Evolutionary programming for the length minimization of addition chains

This paper presents the use of evolutionary programming to minimize the length of addition chains. Generating minimal addition chains is considered an NP-hard search problem. Addition chains are employed to reduce the number of multiplications in modular exponentiation for data encryption and decryption in public-key cryptosystems. The algorithm is based on a mutation operator able to generate a set of feasible addition chains from a single solution and a replacement mechanism with stochastic elements to favor diversity in the population. Furthermore, the proposed algorithm is coupled with a deterministic method with the aim to solve large exponents. Five experiments are carried out to test the approach in different types of exponents. The proposed algorithm is able to find competitive or even better results by requiring a lower number of evaluations with respect to those required by state-of-the-art nature-inspired algorithms.