An efficient simulated annealing algorithm for short addition sequences

Abstract

Let $ N = \left\{{n}_{1}, {n}_{2}, \;\dots , {n}_{k}\right\} $ be a finite set of positive numbers. The problem of finding the minimal number of additions required to compute all elements of N starting from 1 (called the addition sequence problem) is NP-complete. It is equivalent to finding the minimum number of multiplications needed to compute a group exponentiation $ {g}^{{n}_{1}}, {g}^{{n}_{2}}, \;\dots , {g}^{{n}_{k}} $, where g is an element in a group. This paper aims to propose a new metaheuristic algorithm using a simulated annealing strategy to generate a short addition sequence. The performance of the proposed algorithm is measured by considering two parameters: The size of N and the domain of $ {n}_{\mathrm{i}}, 1\le i\le k $. The proposed algorithm is a new trade-off between the length of the generated addition sequence and the average running time of generating addition sequences. It sometimes produces longer addition sequences than exact algorithms that are slower, and it is slower than suboptimal algorithms that produce longer addition sequences.

Keywords

• addition sequence
• addition chain
• modular exponentiation
• simulated annealing
• heuristic algorithm
• optimization