LLL-Algorithmus

gegeben eine (hochgenaue) Näherung x einer algebraischen Zahl, gesucht das dazugehörige Polynom.

Bestimme eine kurzen Vektor in dem Gitter, das durch diese Spaltenvektoren aufgespannt wird:

$$\left(\vphantom{ \begin{array}{ccc} 1 & & 0 \\ & \ddots & \\ & & 1 \\ F\cdot x^d & \dots & F\cdot x^0 \end{array}}\right.$$$$\begin{array}{ccc} 1 & & 0 \\ & \ddots & \\ & & 1 \\ F\cdot x^d & \dots & F\cdot x^0 \end{array}$$$$\left.\vphantom{ \begin{array}{ccc} 1 & & 0 \\ & \ddots & \\ & & 1 \\ F\cdot x^d & \dots & F\cdot x^0 \end{array}}\right)$$

Dabei F sehr groß wählen.

Matrix berechnen durch diese Mupad-Funktion

M := (x, d, f) -> [[(if s = z then
                         1
                       else
                         if z = d + 1 then
                           round(f*x^((d + 1) - s))
                         else
                           0
                         end_if
                       end_if) $ s = 0..d] $ z = 0..d + 1]
DIGITS := 50
x:=2^(1/2)+3^(1/3)

kurzen Gittervektor finden durch LLL-Algorithmus (Lenstra,Lenstra,Lovasz), findet nicht den kürzesten, hat dafür aber vernünftige Laufzeit.

lllint (M(x,6,10^40)  -- verschiedene Dimensionen probieren

liefert Kandidaten für Koeffizienten eines Polynoms mit Nullstelle x.

Andere Anwendung (Übung): finde nahe beieinanderliegende (Primzahl-)Produkte Matrix wie oben, untere Zeile besteht aus F log(2), F log(3), F log(5), F log(7). Für F = 10⁶ findet man die Koeffizienten [4, - 2, 11, - 2, - 6], das entspricht 2⁴5¹1 = 781250000, 3²*7²*11⁶ = 781258401. vgl. abc-Vermutung und Tabelle http://www.mathematik.uni-jena.de/~aros/abc.html