DocumentCode
1029253
Title
Opening the knapsack by DFTs
Author
Maseng, T.
Author_Institution
ELAB, Trondheim, Norway
Volume
23
Issue
2
fYear
1987
Firstpage
95
Lastpage
96
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
cryptography; fast Fourier transforms; information theory; Galois field; algorithm; discrete Fourier transforms; general knapsack problem; high-density knapsacks; number of operations required; set of integers; subset sum problem;
fLanguage
English
Journal_Title
Electronics Letters
Publisher
iet
ISSN
0013-5194
Type
jour
DOI
10.1049/el:19870068
Filename
4257335
Link To Document