M / E23

Der LLL-Algorithmus ist ein nach A. Lenstra, H. Lenstra und L. Lovasz (1982) benannter Algorithmus, der für ein Z-Gitter eine Basis aus möglichst kurzen Vektoren berechnet. Diese Vektoren sind Approximationen für die kürzesten voneinander linear unabhängigen Vektoren des Gitters. Bei seiner Entdeckung war der LLL-Algorithmus der erste effiziente Gitterreduktionsalgorithmus über den ganzen Zahlen. Folgen wir den Quellen von A. Schiemann (1998) und H. Napias (1996), können wir eine Verallgemeinerung des Algorithmus auf hermitesche Formen - definiert auf einem Gitter über den Ganzheitsring eines Zahlkörpers - entwickeln. Hierzu untersuchen wir die Frage nach der Reduziertheit einer hermiteschen Form und beantworten das Problem der Qualität mit a-priori Abschätzungen für die Basisvektoren.

Roland Piontek

TU Dortmund