No label defined (Q3345787)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3880121
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3880121 |
Statements
1983
0 references
density of a knapsack problem
0 references
knapsack based cryptosystems
0 references
0.8938044309616089
0 references
0.8830870985984802
0 references
0.872398316860199
0 references
0.8695288300514221
0 references
0.8564696311950684
0 references
[For the entire collection see Zbl 0523.00001.] Let \(a_ 1,...,a_ n\) be a set of positive integers. Let \(A=\max \{a_ 1,...,a_ n\}.\) The density of a knapsack problem with weights \(a_ 1,...,a_ n\) is defined to be \(n/\log_ 2A.\) In the paper it is shown how techniques similar to those developed for breaking knapsack based cryptosystems can be used to solve knapsacks of low density and that the given algorithm succeeds on most knapsacks of density \(\leq 1/3\).
0 references