1
Computeralgebra
ZusatzBlatt
12.08.2015
Prof. Dr. T. de Jong / M. Pauly
Bei Aufgabe 1 bis 7 handelt es sich um eine alte Klausur. Die weiteren Aufgaben sollen einige
Themen abdecken, die in der Klausur damals nicht vorkamen.
Aufgabe 1.
1. Beschreiben Sie den Algorithmus zum schnellen Potenzieren modulo n.
2. Wie viele Multiplikationen benötigen Sie damit, um 2345 mod 373 zu berechnen?
Aufgabe 2.
1. Zeigen Sie: Ist n gerade, p eine Primzahl und xn ≡ 1 mod p, so ist xn/2 ≡ ±1 mod p.
2. Zeigen Sie durch ein Gegenbeispiel, dass diese Aussage nicht gilt, wenn p zusammengesetzt
ist.
3. Beschreiben sie den Miller-Rabin-Test:
• Was berechnet man, um zu testen, ob eine Zahl n prim ist?
• Bei welchem Ergebnis sind welche Aussagen möglich? Warum?
Aufgabe 3.
1. Definieren sie die Begriffe Resultante und Sylvestermatrix.
2. Welche Aussage erlaubt die Resultante R(f, g) über die beiden Polynome f und g? Was
besagt R(f, f 0 ) über f ?
3. Überprüfen Sie, ob f = X 5 + X + 1 in F2 [X] quadratfrei ist.
4. Wenden Sie den Berlekamp-Algorithmus auf (den quadratfreien Teil von) f an.
5. Wie können Sie ein normiertes Polynom in Z[X] faktorisieren? Beschreiben Sie ein Verfahren.
Aufgabe 4.
1. Geben Sie die Definition einer Monomordnung auf R := K[X1 , ..., Xn ].
2. Was ist eine Eliminationsordnung für T ⊂ {X1 , ..., Xn }?
3. Geben Sie eine Eliminationsordnung auf R an. Für welche Teilmenge T ⊂ {X1 , ..., Xn } ist
dies eine Eliminationsordnung?
4. Geben Sie eine Monomordnung auf R an, die keine Eliminationsordnung für irgendein ∅ 6=
T ⊂ {X1 , ..., Xn } ist.
Aufgabe 5.
1. Definieren Sie den Begriff Gröbnerbasis.
Wann heißt eine Gröbnerbasis minimal bzw. reduziert?
2. Sei g1 = XY + X und g2 = X 2 + 2Y . Berechnen Sie eine Gröbnerbasis von I = hg1 , g2 i bzgl.
degrevlex mit X > Y .
3. Liegt f = X 2 + Y 2 + 3Y in I?
2
Aufgabe 6. Sind die folgenden Aussagen wahr oder falsch? Geben sie einen Beweis oder ein
Gegenbeispiel an.
1. Jedes maximale Ideal ist ein Primideal.
2. Jedes Primideal ist maximal.
Sei R = K[X1 , ..., Xn ], I, J ⊆ R Ideale.
3. Wenn I ⊆ J, so ist V(J) ⊆ V(I).
4. Wenn I ( J, so ist V(J) ( V(I).
Aufgabe 7. (Bonus: bis zu 10 Punkte) Wenn Sie noch etwas relevantes aus der Vorlesung wissen,
nach dem bisher nicht gefragt wurde, können Sie es uns hier mitteilen.
Aufgabe 8. Welche der folgenden Gruppen sind zyklisch? Geben Sie im zyklischen Fall einen
Erzeuger an.
1. Z/9Z (Gruppe bezüglich +).
2. Z/6Z ⊕ Z/15Z (Gruppe bezüglich +).
3. Z/6Z ⊕ Z/35Z (Gruppe bezüglich +).
4. (Z/9Z)∗ (Gruppe bezüglich ·).
5. (Z/15Z)∗ (Gruppe bezüglich ·).
Aufgabe 9.
1. Faktorisieren Sie die Zahl n := 2993 mit der pollardschen Rho-Methode mit f (x) := x3 +x+1
und x0 = 4.
2. Was besagt die Verbesserung von Brent? Wieso funktioniert diese?
3. Was ist die Idee der pollardschen p − 1 Methode?
4. Zeigen Sie (nicht durch Probedivision), dass die Zahl 317 eine Primzahl ist.
Aufgabe 10. Zeigen Sie, dass die folgenden zwei Polynome in Q[x] irreduzibel sind.
1. f1 (x) := x7 + 15x5 + 27x4 + 18x2 + 21x + 105.
2. f2 (x) := x5 + 5x4 + 10x3 + 10x2 + 5x + 3.
Aufgabe 11.
1. Wie sieht der Körper mit 125 Elementen aus?
2. Wieviele irreduzible Polynome vom Grad 4 gibt es in Z/5Z[x]?
Aufgabe 12.
1. Bestimmen Sie die Menge V(xy) ⊂ C2 .
2. Ist die Menge der 26-ten (primitive) Einheitswurzeln eine affine Varietät in C?
3. Ist R2 ⊂ C2 eine affine Varietät?
4. Ist Z ein noetherscher Ring? Beweisen Sie Ihre Aussage!
3
Aufgabe 13.
1. Wie können Sie testen, ob ein Gleichungssystem aus Polynomen mit Koeffizienten in C eine
Lösung besitzt oder nicht?
2. Wie verhalten sich affine Varietäten, falls man mit ihren Idealen die Operationen · bzw. +
bzw. ∩ durchführt?
3. Wie können Sie (mit Hilfe von Gröbner Basen) den Schnitt zweier Ideale berechnen?
Aufgabe 14. Sei I = (x3 +3y 2 z+17z 2 y−14z, y 4 −x2 +15zy 2 +z 3 +5, z 2 +3x−2y+25) ⊂ C[x, y, z].
Zeigen Sie, dass I ein nulldimensionales Ideal ist. Wie könnte man die Anzahl der Elemente von
V(I) bestimmen?
© Copyright 2024 ExpyDoc
