We live in an online world: we date online, we do business online and we communicate online. To make sure this happens securely, almost all transferred data is encrypted by cryptosystems. This paper focuses on one of these: the knapsack cryptosystem of Merkle and Hellman, which relies on the hardness of solving the knapsack problem (1978). In general it works as follows.
Bob, who wants to communicate with Alice, encrypts his message with a public key and sends this to her. If a third party now intercepts it, he must solve an instance of the knapsack problem, which is NP-hard in general. However, this becomes computationally infeasible if the number of items is large, and therefore Bob’s message is safe. Alice has access to a private key, which she uses to transform the hard knapsack problem into an easier one: one where the vector of weights is superincreasing. That is, each component of the vector is larger than the sum of all previous components. In this case she can solve the problem efficiently and read what Bob sent her.
This method seems to be reliable at first sight. However, a few years after it was published, cryptographer Shamir proposed an algorithm that breaks the system (1984). The algorithm finds a pair of numbers by solving two systems of inequalities. Then a third party can use this pair to transform the hard knapsack problem into one he can solve, which may be different from the one Alice finds. However, he will find the same solution, and therefore he can also read Bob’s message.
This algorithm can be implemented as a computer program and in this paper we used Python. The first system of inequalities is written as a optimization problem and since there is fixed number of unknowns, we can solve it in polynomial time using Lenstra’s integer programming algorithm (1983). In this paper we used the Gurobi optimizer to solve it, as Lenstra’s algorithm is hard to use in practice. The second system of inequalities is solved by comparing lower and upper bound, which can also be carried out in polynomial time. Nevertheless, the total algorithm finishes in polynomial time only with a certain high probability since we made some probabilistic assumptions. This implies that there is a small probability of failure. However, if it finds a solution, then the algorithm is fast, and therefore it is still valuable to use in real life.

We have tried to create a bin-packing algorithm that assigns items from a customer-order to totes such that the amount of totes is minimized. Analyzing the bin-packing algorithm that was used before this thesis had been written, taught us that xxx.xx% of the customer-orders was packed non optimal. In this thesis four algorithms are applied to Picnic data. The order in which the algorithms assign items to a tote has major consequences for the solutions. Eight different ways to order the items are combined with each algorithm, resulting in 32 different tote-calculations. Out of those 32 tote-calculations, the Best Fit Algorithm with items ordered in decreasing normalized values generates the best results. Remarkably, ordering items randomly also gives good solutions. This brought us to introducing a new method, where each customer-order is calculated at most eight times, each time shuffling the items before rerunning the algorithm and remembering the better solution. This heuristic is optimal for xxx.xx% of the customer-orders.