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

      0 references
      1983
      0 references
      density of a knapsack problem
      0 references
      knapsack based cryptosystems
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references