An Algorithm Using Modular Arithmetic for the Subset Sum Problem
Toshiro Tachibana, Hideo Nakano, Yoshiro Nakanishi, Mitsuru Nakao · Systems and Computers in Japan · 1990
Abstract In this paper, an algorithm is developed for the subset sum problem in connection with public key cryptosystems. It is known that the subset sum problem based on a super‐increasing sequence of numbers can be solved simply and in a polynomial time. It is known also that the subset sum problem based on general sequences of numbers is NP‐hard, and the difficulty of the problem varies especially depending on the density. Thus, this paper proposes an algorithm using modular arithmetic for the subset sum problem based on general sequences of numbers. The basic idea of this algorithm is that “the largest number in a sequence of numbers A= (a1, …, an) is transformed to a super‐increasing number by modular arithmetic.” The advantages of the algorithm are investigated by experiment, and it is shown that by the properties of problems used, this algorithm is an effective method for the subset sum problem based on general sequences of numbers, especially “the case where the density is close to 1,” where the existing method is weak.