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
4 July 1999
0 references
knapsack problems
0 references
0.8048250079154968
0 references
0.7859269976615906
0 references
0.7751161456108093
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