A deterministic algorithm for modular knapsack problems (Q809609)

The knapsack problem is quite a well known NP-complete problem, and as a such it is considered hard to solve in general. Fortunately its use as a basis of one of the first public key cryptosystems initiated a series of attempts to solve efficiently at least some of its subcases. The article by A. Salomaa presents a deterministic algorithm to test whether a given knapsack vector is super-reachable, i.e. whether it may be calculated from a super-increasing vector by modular multiplication. In the positive case the algorithm produces such a super-increasing vector as well as a multiplier and a modulus. This is enough to efficiently calculate solution of the original knapsack problem. The complexity of the algorithm depends on the growth of the entries of the original knapsack vector with respect to n, the dimension of the vector. If the entries of the knapsack vector are assumed to grow linearly in n, then the complexity of the algorithm is \(0(n^ 3)\).