Ganzzahlige Beziehungen

• gegeben: Näherungs-Wert einer algebraischen Zahl, Bsp: x = 0.41421356237309515

  gesucht: das Minimalpolynom für x,

  d.h., Zahlen c₀,…, c_n∈$\mathbb {Z}$ mit 0 = $\sum_{k}^{}$c_kx^k

• Ansatz: bestimme kurzen Vektor in

  Gitter mit Basis b_k = [0...0, 1, 0...0,⌈F⋅x^k⌋]

  die 1 auf Position k und F groß (Bsp: F = 10⁵)

  B = $\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 10000 & 41421 & 17157 \end{pmatrix}$