Gitterreduktion und Empirische Mathematik

Integer relations  

Anstatt beliebige Ausdrücke zu bilden, ist es erfolgversprechend, sogenannte integer relations zu suchen: kleine ganzzahlige Beziehungen . Was meine ich damit?

Nehmen wir . Dann erfüllt dieses die Beziehung

und das identifiziert somit in guter Näherung als .

Diese Beziehung ist ganzzahlig, da wir nur ganzzahlige Koeffizienten benutzen. Wieso kleine ganze Zahlen? Nunja, naturgemäß ist auch

ist eine ganzzahlige Beziehung, oder viel schlimmer Die Näherung ist aber nicht jene aussagekräftige, die wir wollten.

Gut - eine Bruchzahl, das war einfach. Nehmen wir die Zahl als Näherung von . Hier finden wir keine sinnvolle ganzzahlige Beziehung, die nur involviert ( ist irrational!). Aber natürlich ist

eine wunderbare kleine ganzzahlige Beziehung zwischen und . Das bringt uns auf die richtige Fährte. Wir suchen integer relations zwischen , Potenzen , vielleicht Potenzen von Konstanten und ... Je mehr Komplexität wir dem gesuchten Ausdruck zugestehen, desto mehr potenzielle Parameter müssen wir vorberechnen, Logarithmen, Exponentiale inklusive. Dann hoffen wir auf eine knackige ganzzahlige Beziehung zwischen diesen Werten.

Gehen wir doch mal das vom Anfang des Artikels an. Ich schenke euch folgende Beziehung (nachrechnen)

Eindeutig liegt hier ein exakter Ausdruck für in der Luft. Welcher das ist? Dazu müssen wir wieder die Gleichung lösen. -Terme nach rechts, binomische Formel auf der linken Seite anwenden, Wurzel ziehen. Wir formen um:

Die plausible Lösung ist also .

Die große Frage ist nun: Wie findet man solche integer relations? Man kann natürlich anfangen und Zahlenkombinationen durchprobieren. Das ist systematischer als das Erzeugen beliebiger Ausdrücke wie oben, aber immer noch quälend langsam, soll heißen, exponentiell in der Anzahl der Parameter, zwischen denen man eine Beziehung sucht. Wir werden nun sehen, wie integer relations auf eine primitive Weise ein Gitterproblem ergeben, und daraufhin den Reduktionsalgorithmus LLL zur Lösung anwenden.

Gitterreduktion und LLL  

Gitter sind eine regelmäßige Anordnung von Punkten (Vektoren) im Raum, die man erhält, indem man ausgehend von Basisvektoren ganzzahlige Kombinationen bildet. Zwei solcher Basen können durchaus dasselbe Gitter liefern, wenn sie sich ineinander ausdrücken lassen. Leider sieht man Basen nicht an, ob das Gitter, das sie erzeugen, irgendwelche besonders kurzen Vektoren enthält. Wenn ja, würde man sich eine Basis aus solchen Vektoren wünschen. Ansonsten passiert es, dass wir für einen sehr kurzen Vektor erst sehr weit in eine Richtung laufen müssen und dann wieder sehr weit zurück, um fast am Anfang wieder herauszukommen. Das unterscheidet "gute" und "schlechte" Basen. Die Aufgabe, zu einer beliebigen Gitterbasis eine gute Basis zu finden, die dasselbe Gitter erzeugt, heißt Gitterreduktion.

In der verlinkten Kolumne war vom 2-dimensionalen Gitter mit folgender Basis die Rede

Wie können wir diese Basis zu einer guten Basis reduzieren? Der vielleicht prominenteste Algorithmus dazu heißt LLL-Algorithmus und hat unzählige Anwendungen. Leider handelt es sich um einen sehr ausgefeilten Algorithmus, den man nicht mal so eben selbst implementiert. Er ist aber Standard in den meisten Computeralgebrasystemen.

Wir wollen ihn gleich austesten und benutzen das CAS Macaulay2, das wir dankenswerterweise direkt interaktiv im Browser ausführen können. Im Eingabefenster sehen wir, dass uns mit dem geladenen Package LLLBases direkt eine Implementierung zur Verfügung steht.

Wir schreiben die Basis unseres Gitters in die Spalten einer 2x2-Matrix und rufen die Funktion LLL auf. In Code

m = matrix{
    {4831, 129361},
    {220,  5891}
};

LLL m

Ins Eingabefenster kopieren und Enter drücken. Ausgabe ist die Matrix

Unser Gitter ist tatsächlich das Einheitsgitter und wird von und erzeugt (Vorzeichen spielen keine Rolle)!

Die Ausgabe von LLL hat zudem die schöne Eigenschaft, dass der erste Basisvektor der reduzierten Basis ein sehr kurzer Gittervektor (short vector) ist. Das werden wir jetzt für die Suche nach integer relations benutzen.

Wir wollen die ganzzahlige Beziehung zu selbstständig finden. Wir beziehen die Parameter mit ein. Betrachten wir ein Gitter mit folgender Basis

Eine Linearkombination der Spalten mit ganzen Zahlen liefert einen Vektor

In den ersten vier Koordinaten erhalten wir einfach unsere Koeffizienten wieder und in der letzten Koordinate die entsprechende Linearkombination unserer Parameter. Ziel ist es jetzt, die letzte Koordinate auf 0 zu bekommen! So erhalten wir eine ganzzahlige Beziehung, das allein berücksichtigt aber noch nicht, dass die Koeffizienten möglichst klein seinen sollen. Wir beziehen die Koeffizienten mit ein, indem wir einen Vektor suchen, der insgesamt möglichst kurz ist.

Das minimiert wiederum die Qualität der Beziehung und die Größe der Koeffizienten in gleichem Maße. Die Summe in der letzten Koordinate könnte erheblich von Null abweichen, wenn nur die benutzen Koeffizienten klein sind. Wir gewichten das, indem wir z.B. die Basis

benutzen. Das Durchmultiplizieren mit irgendeiner großen Zahl ändert nichts an den Koeffizienten der Beziehung, sorgt aber dafür, dass in erster Linie die letzte Koordinate minimiert wird. Schließlich können wir diese Zahlen sogar abrunden und eine rein ganzzahlige Matrix bekommen. Ein short vector im von diesen Vektoren erzeugten Gitter löst das ganzzahlige Beziehungsproblem, und diesen finden wir als ersten Ausgabevektor von LLL.

Zu abstrakt?

x = 3.8416075273496059561780;
n = 1000000000;

m = matrix{
    {1, 0, 0, 0},
    {0, 1, 0, 0},
    {0, 0, 1, 0},
    {0, 0, 0, 1},
    {floor(n*1), floor(n*x), floor(n*x^2), floor(n*pi)}
};

LLL m

Für die unreduzierte Basis m haben wir

| 1          0          0           0          |
| 0          1          0           0          |
| 0          0          1           0          |
| 0          0          0           1          |
| 1000000000 3841607527 14757948394 3141592653 |

LLL gibt das Ergebnis

| 1   -286 430  134   |
| 4   178  897  241   |
| 4   -31  -315 64    |
| -24 19   246  -638  |
| 12  -1   247  -1391 |

aus. Die erste Spalte bedeutet, dass die Koeffizienten die letzte Koordinate auf den Wert minimieren. In der Größenordnung von einer Milliarde, die wir dranmultipliziert haben, kann man das glatt als Null gelten lassen. Ablesen der Koeffizienten: Wir haben die Beziehung

gefunden.

Komplexität  

Je komplexer wir die Ausdrücke vermuten, desto mehr Parameter müssen wir einbeziehen und desto hochdimensionaler werden die Gitter. Das Integer Relation-Problem ist NP-vollständig, da es sogar eine Verallgemeinerung des berüchtigten Subset-Sum-Problems ist.

Gegeben eine Liste von Zahlen und eine vorgegebene Zahl , gibt es eine Auswahl von Zahlen aus der Liste, die sich zu summieren?

Die Lösung ist nämlich nichts anderes als eine integer relation zwischen den gelisteten Zahlen und , die nur Koeffizienten 0 und 1 benutzt (und vor ). Ebenso sind das Auffinden von short vectors und Gitterreduktion NP-vollständig, da wir diese Verfahren ja eben benutzt haben, um integer relations zu finden. Wer möchte, kann sich einmal versuchen und mit LLL und Macaulay2 auch ein Subset-Sum-Problem lösen. Der Code von oben muss strukturell kaum modifiziert werden.

Der LLL-Algorithmus ist ein polynomieller und für mittelgroße Matrizen ziemlich effizienter Algorithmus, allerdings wird eine Ausgabe mit steigender Dimension exponentiell schlechter. Sprich, irgendwann ist der gefundene erste Basisvektor nicht unbedingt der kleinste des Gitters, sondern nur bis auf irgendeinen großen Faktor. Man kann also stets LLL als effizienten Ansatz probieren, aber muss dann über die Qualität der gefundenen Relationen nachdenken.

Empirische Mathematik  

Wir haben gesehen, wie man zu gegebenen Rundungswerten symbolische Ausdrücke raten kann. Bekommen wir tatsächlich einen Ausdruck hin, ist dessen Wert unterschiedlich. Wenn man lang genug mit immer komplexeren Formeln sucht, wird man schließlich immer irgendwie fündig, nur was sagt das noch? Gelangt man aber, wie man hofft, zu einer knappen prägnanten Formel, kann man so tatsächlich auf einen neuen Zugang zu mathematischer Wahrheit gestoßen sein, der die Erforschung lohnt. Gerade durch die Leistungsfähigkeit von Computern, die solche Entdeckungen heute möglich macht, gesellt sich zur klassischen deduktiven Arbeitsweise des Mathematikers eine empirische hinzu. Einen korrekten Beweis ersetzt ein Computerfund natürlich nie, eine Quelle für Inspiration und Intuition kann er allemal sein.

Zum Austoben  

Wer zum Abschluss des Artikels Lust bekommen hat, sich auszutesten, versuche sich an folgendem Problem: Die gerundete Zahl entsteht durch einen schönen Ausdruck. Welchen?

Man sollte die mathematischen Konstanten, ihre Potenzen sowie positive und negative Potenzen von berücksichten. Die Antwort darf gerne in den Foren gepostet werden :)

Quellen  

• Beispiel für das gezeigte Verfahren auf Wikipedia
• Hoffstein, Pipher, Silvermann: Introduction to Mathematical Cryptography [Kapitel über Gitter, Subset sum problem und LLL]
• Ich will nicht verschweigen, dass die Erlösung aller Erstsemester, Wolframalpha , ebenfalls versucht, zu gegebenen Eingaben plausible geschlossene Ausdrücke zu finden: Beispiel

Ihre Meinung  

Falls Sie Fragen zu diesem Artikel haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.