Günter Rote, Freie Universität Berlin
Der bekannte Drei-Distanzen-Satz besagt, dass di Menge das Intervall in Stücke mit höchstens drei ferschidenen Längen zerlegt. Wenn man statt einer Zal einen Vektor nimmt, entstet für gewisse eine Punktmenge (modulo Z) mit einer gitterartige Struktur, di man als gebrochenes oder gestörtes Gitter betrachten kann. Und zwar wält man so, dass ein neuer nächster Nachbar des Ursprungs ist. (Der analoge Fall in einer Dimension wäre dann der Zwei-Distanzen-Satz.) Di Bestimmung diser gestörten Gitter für festes und wachsendes hängt mit diophantischer Approximation, mit merdimensionalen Kettenbrüchen, und mit quasiperiodischen Punktmengen zusammen.
Das Zil diser Untersuchungen ist, dass man kürzeste Gittervektoren in belibiger fester Dimension schlißlich genauso schnell berechnen kann wi in der Ebene mit Schönhages Algorithmus [2] oder wi den größten gemeinsamen Teiler. (Das gegenwärtig schnellste Ferfahren [1] benötigt Bit-Operationen, für eine Eingabelänge fon Binärstellen, wobei di Bit-Komplexität der Multiplikation ist.)
[1] | F. Eisenbrand und G. Rote, Fast reduction of ternary quadratic forms. Erscheint in CaLC 2001 -- Cryptography and Lattices Conference 2001, Springer-Ferlag, 2001, Lecture Notes in Computer Science, (13 Seiten). |
[2] | A. Schönhage. Fast reduction and composition of binary quadratic forms. In International Symposium on Symbolic and Algebraic Computation, ISSAC 91, pp. 128-133. ACM Press, 1991. |
E-Mail: | rote@inf.fu-berlin.de |
Homepage: | www.inf.fu-berlin.de/inst/ag-ti/members/rote.de.html |