Breadcrumbs Section. Click here to navigate to respective pages.

Chapter

Chapter

# The Knapsack Problem

DOI link for The Knapsack Problem

The Knapsack Problem book

# The Knapsack Problem

DOI link for The Knapsack Problem

The Knapsack Problem book

## ABSTRACT

In this chapter we present our first application of lattice basis reduction to cryptography: we use the LLL algorithm to break a knapsack cryptosystem.

Definition 7.1. Suppose that we are given a set of n distinct positive integers

A = { a1, a2, . . . , an },

together with another positive integer s. The subset-sum problem (also called the knapsack problem) asks whether there exists a subset

I ⊆ { 1, 2, . . . , n },

for which the sum of the corresponding elements of A is exactly s:∑ i∈I

ai = s. (7.1)

We think of s as the size of a knapsack, and the numbers ai as the sizes of items to be placed in the knapsack; the question is then whether the knapsack can be filled exactly by some subset of the items.