Gitterbasenreduktion für beliebige Normen
- Wir verallgemeinern die Reduktionstheorie von Gitterbasen für beliebige Normen. Dabei zeigen wir neue Eigenschaften reduzierter Basen für die verallgemeinerten Reduktionsbegriffe. Wir verallgemeinern den Gauß-Algorithmus zur Reduktion zweidimensionaler Gitterbasen für alle Normen und erhalten eine universelle scharfe obere Schranke für die Zahl seiner Iterationen. Wir entwickeln für spezielle lp-Normen eine Variante des Gauß-Algorithmus mit niedriger Bit-Komplexität. Hierzu wird Schönhages schneller Reduktionsalgorithmus für quadratische Formen auf die Reduktion von Gitterbasen im klassischen zentrierten Fall übertragen.
- We generalize the reduction theory of lattice bases to arbitrary norms and show new properties of reduced bases for the generalized reduction concepts. We generalize the Gaussian Algorithm for the reduction of two-dimensional lattice bases to arbitrary norms and obtain an universally sharp upper bound on the number of its iterations for all norms. We develop a new variant of the Gaussian Algorithm with low bit complexity for special lp-norms. Therefore we use the ideas of Schoenhage's fast reduction algorithm for quadratic forms to obtain the fast reduction algorithm for quadratic forms to obtain the firrst asymptotically fast centered reduction algorithm for two-dimensional lattice bases.
Deutsches Urheberrecht