No label defined (Q4254898)

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 1313325
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1313325

      Statements

      0 references
      4 July 1999
      0 references
      knapsack problems
      0 references
      Unter einem Gitter vestehen wir eine (durch eine Gitterbasis erzeugte) diskrete, additive Untergruppe des \(\mathbb{R}^n\). Wir entwickeln Aufzählungsverfahren zur Bestimmung eines (bezüglich einer beliebig vorgegebenen Norm) nachweislich kürzesten, von Null verschiedenen Gittervektors, die in möglichst hohen Dimensionen vertretbare Rechenzeiten besitzen. Wir lösen Rucksackprobleme durch Reduktion auf die Suche nach einem Gittervektor mit \(\ell_\infty\)-Norm 1. Mit unserem Aufzählungsverfahren bezüglich der \(\ell_\infty\)-Norm gelingt es, alle Rucksackprobleme bis Dimension 66 effizient zu lösen. Wir brechen mit diesem Verfahren Kryptosysteme, die auf dem Rucksackproblem basieren. Der Aufwand zur Bestimmung eines kürzesten, von Null verschiedenen Gittervektors hängt entscheidend von der Wahl der Basis des jeweiligen Gitters ab. Er wird umso geringer, je besser die Basisvektoren die kürzesten Gittervektoren approximieren. Wir untersuchen daher verschiedene Reduktionsbegriffe. Wir zeigen Schranken für die Güte der Approximation und entwickeln Algorithmen zur Bestimmung von reduzierten Gitterbasen. Für große Dimensionen reichen selbst ``gut vorreduzierte'' Gitterbasen nicht mehr aus, um einen kürzesten Gittervektor effizient zu bestimmen. Wir entwickeln ein probabilistisches Aufzählungsverfahren, das für zufällige Eingaben eine fest vorgegebene Erfolgswahrscheinlichkeit beweisbar nicht unterschreitet.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references