Opening the knapsack by DFTs
- 16 January 1987
- journal article
- Published by Institution of Engineering and Technology (IET) in Electronics Letters
- Vol. 23 (2) , 95-96
- https://doi.org/10.1049/el:19870068
Abstract
A new simple algorithm which uses discrete Fourier transforms for breaking the general knapsack problem (also known as the subset sum problem) is presented along with the number of operations required for solving the problem. The method is applicable when the elements belong to a Galois field as well as that of a set of integers and is most effective for high-density knapsacks.Keywords
This publication has 2 references indexed in Scilit:
- A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- Fast Fourier Transform and Convolution AlgorithmsPublished by Springer Nature ,1982