Oberseminar Komplexität und Algorithmen

Wintersemester 2005/2006

Prof. Dr. Peter Bürgisser



Termin: Donnerstag, 14:15-15:45 im E2.304

Beginn: Donnerstag, den 24.11. um 14:00 s.t. im E2.304

Wichtig: Wir bitten Interessenten, sich in die Mailingliste seminarca einzutragen.


Vorträge

Do, 24.11.2005 Punktezählen auf elliptischen Kurven - Die Hasseschranke
Christiane Peters
Folien
Do, 15.12.2005 Die p-adische Regel von Descartes
und Dennis Amelunxen
Do, 22.12.2005

Nach der sogenannten Regel von Descartes lässt sich die Anzahl der reellen nichttrivialen Nullstellen (also alle x<>0 mit f(x)=0) eines Polynoms f in einer Unbestimmten nach oben abschätzen durch 2k, wobei k+1 die Anzahl der Terme in f ist.
In der Arbeit "On the factorization of lacunary polynomials" beweist H.W. Lenstra, Jr. ein p-adisches Analogon dieser Regel: Sei p prim, L eine endliche Erweiterung der p-adischen Zahlen und k eine positive ganze Zahl. Dann gibt es eine Konstante B=B(k,L), so dass gilt: Ein Polynom f aus L[T], welches höchstens k+1 (nichtverschwindende) Terme hat, hat höchstens B nichttriviale Nullstellen in L (gezählt mit Vielfachheit).
Aus diesem p-adischen Resultat folgert er noch eine Aussage über beliebige Zahlkörper. Seien m, k und d positive ganze Zahlen. Dann gibt es eine Konstante A=A(m,k,d), so dass für jeden Zahlkörper K vom Grad höchstens m über den rationalen Zahlen gilt: Sei f aus K[T] ein Polynom mit höchstens k+1 (nichtverschwindenden) Termen, das Null nicht als Nullstelle hat, und sei g ein Faktor von f, dessen irreduzible Faktoren höchstens den Grad d haben. Dann ist der Grad von g nach oben beschränkt durch A. (Als Korollar folgt eine Aussage über die Anzahl der Nullstellen von f.)

In dem Vortrag sollen zunächst die p-adischen Zahlen definiert, endliche Erweiterungen davon untersucht und schließlich der vollständige algebraische Abschluss konstruiert werden. Außerdem wird noch das (p-adische) Newton-Polygon (eines Polynoms) definiert und dessen Eigenschaften untersucht. Anschließend soll die Argumentation von Lenstra nachvollzogen und seine (Haupt-)Ergebnisse bewiesen werden.

Folien, Übersicht Körpererweiterungen
Do, 12.01.2006 Punktezählen auf elliptischen Kurven über endlichen Körpern - Der Algorithmus von Schoof
Christiane Peters

Der Algorithmus von Schoof aus dem Jahr 1984 lieferte den Durchbruch in der Algorithmik der Primzahltests mit Hilfe elliptischer Kurven über endlichen Körpern. Dieser Polynomialzeitalgorithmus ermöglichte die Entwicklung des sogenannten "Elliptic Curve Primality Proving", wofür der Goldwasser-Kilian-Primzahltest aus dem Jahre 1986 eines der ersten Beispiele darstellt.

Schoofs Algorithmus berechnet die Anzahl Punkte einer elliptischen Kurve E über einem endlichen Körper K in polynomieller Zeit. Die Idee beruht auf der Berechnung der Spur des Frobenius-Endomorphismus' in der l-Torsion der Kurve E für "kleine" Primzahlen l. Das Ergebnis kann mit Hilfe des Chinesischen Restsatzes und der Hasseschranke eindeutig bestimmt werden.

Do, 26.01.2006 Zählen und Erzeugen von magischen Quadraten
Stefan Wolf

In dem Vortrag wird ein Zusammenhang zwischen magischen Quadraten und bestimmten Invariantenringen hergestellt, so dass man mit Methoden der Invariantentheorie sowohl quantitative als auch qualitative Aussagen über magischen Quadrate herleiten kann.

Zuerst wird eine Bijektion zwischen kombinatorischen Strukturen und Invariantenringen einer gewissen Torusoperation angegeben. Damit kann man dann zuerst die Erzeuger und dann auch die Anzahl der magischen Quadrate bestimmen. Anschliessend wird auf eine Methode eingegangen, mit der es möglich ist, ohne Umweg über die Erzeuger die Anzahl magischer Quadrate zu bestimmen.

Diplomarbeit