A Multicore Exact Algorithm for Addition Sequence

Abstract

This paper addresses one of the NP-complete problems that is used to reduce the number of computation for multi-exponentiation operation. The problem is the addition sequence for a set of n-positive integers X = {m1, m2, . . . , mn} such that 2≤ mi < mi+1, 1≤i<n and n≥2. We suggest a parallel hybrid algorithm that finds a minimal length addition sequence for X. The algorithm traverses the search tree using breadth-first and branch-and-bound strategies. We also measure the effectiveness of the suggested algorithm on a multicore system and by using C++ language with OpenMP. The experimental results on sets of different sizes and different number of cores show that the proposed parallel hybrid algorithm for minimal length addition sequences is faster than the fastest sequential algorithm with maximum speed up 2.7.