Das Merkle-Hellman-Verfahren

Das Merkle-Hellman-Verfahren beruht auf dem ,,Untersummen-Problem``, auch als ,,Rucksack-Problem`` bekannt. Der Name stammt von einer sehr anschaulichen Aufgabenstellung: Es sind eine Reihe Gewichte bekannt, von denen sich einige in einem Rucksack befinden. Das Gesamtgewicht des Rucksacks ist bekannt und es soll nun bestimmt werden, welche Einzelgewichte (Elemente) sich in dem Rucksack befinden. Die Lösung dieses Problems ist nicht trivial, da weder gewährleistet ist, dass überhaupt eine Lösung existiert, noch dass eine gefundene Lösung eindeutig ist.

Sind die möglichen Gewichte beispielsweise $\{ 2, 3, 5, 9 \}$ und das Gesamtgewicht $6$, dann gibt es keine Lösung. Ist das Gesamtgewicht hingegen $5$, dann gibt es zwei Lösungen.