3. Übung Elementare Algorithmen in der Algebra

Priv. Doz. Dr. G. Nebe (SS 00)

Aufgabe 10. Algorithmus 2.15 führt die Berechnung einer rationalen Approximation einer modulo N bekannten Zahl c auf die Bestimmung eines kleinen “Minimalpolynoms” (nicht normiert, vom Grad 1) von c zurück. Verallgemeinern Sie diese Strategie für beliebige Grade: Gegeben: eine Zahl c ∈ ℤ, n, N ∈ ℕ. Gesucht: a_{0}, …, a_{n} ∈ ℤ mit ∑_{i=0}^{n} a_{i}^{2} ≠ 0 minimal, so dass ∑_{i=0}^{n} a_{i}c^{i} ≡ 0 (mod N). Bestimmen Sie ein kleines Minimalpolynom vom Grad 2 für c ≡ 280182 (mod 5^{8}). (Hinweis: Mit readlib(lattice); erhält man eine Funktion “lattice” in MAPLE, die den LLL-Algorithmus zum Finden kurzer Vektoren in Gittern durchführt.)

Aufgabe 11. Sei L ein Gitter im Euklidischen Raum (V, Φ). Ein Vektor v ∈ L heißt primitiv, falls a^{−1}v ∉ L für alle 1 ≠ a ∈ ℕ. Zeigen Sie, dass v ∈ L genau dann primitiv ist, wenn man v zu einer Gitterbasis von L ergänzen kann. Sei v ∈ L primitiv, π : V → v^{⊥} die Orthogonalprojektion auf v^{⊥} und L′ := π(L). Zeigen Sie, dass det(L′) = det(L)/Φ(v, v). Sind v_{2}, …, v_{n} ∈ L, so dass (π(v_{2}), …, π(v_{n})) eine Gitterbasis von L′ ist, dann ist (v, v_{2}, …, v_{n}) eine Gitterbasis von L.

Aufgabe 12. Geben Sie ein Beispiel eines 2-dimensionalen Gitters an, für welches in der Hermite Ungleichung Gleichheit gilt.

Aufgabe 13. Ersetzt man den Parameter 3/4 in der Definition einer LLLreduzierten Basis (3.10 (b)) durch einen Parameter α ∈ (1/4, 1), so gelten analoge Aussagen wie in Satz 3.11 (i), (ii), (iii), mit β := 4/(4α − 1) anstelle von 2.

Abgabe: Donnerstag, den 4.5.00, in der Übung 12:30 Uhr im kl. physik. Hörsaal