Knapsack Problem Solution based on Knapsack Packing Tree Search

Abstract

A number of asymmetric cryptosystems (including one of the very first asymmetric cryptosystems – the Merkle–Hellman cryptosystem) are based on the knapsack problem. Many of these cryptosystems are proven either insecure or inapplicable due to extensive amounts of computation necessary. Never the less, presently the knapsack problem is considered to be of importance for cryptography. In this article, the knapsack problem solution algorithm based on knapsack packing tree search is described for the first time.

Keywords

• knapsack problem
• algorithm
• knapsack packing tree