Knapsack Problem

Given a Sum and a set of Weights, find the Weights which were used to generatethe Sum. The values of the weights are then encrypted in the sum. The system relies on the existence of a class ofknapsack problems which can be solved trivially (those in which the weights are separated such that they can be ``peeledoff'' one at a time using a Greedy-like algorithm), and transformations which convert thetrivial problem to a difficult one and vice versa. Modular multiplication is used as the Trapdoor Function. Thesimple knapsack system was broken by Shamir in 1982, the Graham-Shamir system by Adleman, and the iterated knapsack byErnie Brickell in 1984.

References

Coppersmith, D. ``Knapsack Used in Factoring.'' §4.6 in Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, pp. 117-119, 1987.

Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 163-166, 1985.

• Hyperboloid
• Hyperboloid Embedding
• Hypercomplex Number
• Hypercube
• Hyperdeterminant
• Hyperellipse
• Hyperelliptic Function
• Hyperelliptic Integral
• Hyperfactorial
• Hypergeometric Differential Equation
• Hypergeometric Distribution
• Hypergeometric Function
• Hypergeometric Identity
• Hypergeometric Polynomial
• Hypergeometric Series
• Hypergroup
• Hypermatrix
• Hyperparallel
• Hyperperfect Number
• Hyperplane
• Hyperreal Number
• Hyperspace
• Hypersphere
• Hypersphere Packing
• Hypervolume