Pohst, MichaelGeißler, Katharina2015-11-202003-05-282003-05-282003-05-28urn:nbn:de:kobv:83-opus-6149https://depositonce.tu-berlin.de/handle/11303/1010http://dx.doi.org/10.14279/depositonce-713Sei F ein algebraischer Zahlkörper oder ein algebraischer Funktionenkörper über Q oder einem endlichen Körper. In dieser Arbeit beschreiben wir einen effizienten Algorithmus zur Berechnung der Galoisgruppe eines normierten, irreduziblen und separablen Polynoms f vom Grad n <= 23 über F. Unser Ansatz ist frei von Approximationsfehlern und liefert bewiesene Ergebnisse bei schnellen Laufzeiten. Grundlage des Algorithmus ist das Verfahren von Stauduhar und die Verwendung von p-adischen Approximationen der Nullstellen des Polynoms f. Für die Berechnungen wird der Zerfällungskörper des Polynoms f in einer geeigneten unverzweigten p-adischen Erweiterung approximiert. Einer der Schwerpunkte dieser Arbeit bildet die Entwicklung von Algorithmen zur Nullstellenberechnung in diesen Erweiterungen und zur Rekonstruktion von algebraischen Elementen aus einer p-adischen Approximation. Für die Rekonstruktionsalgorithmen werden Techniken verwendet, die auf Gittern basieren. Ferner werden Schranken für die Präzision hergeleitet, um die Korrektheit der Ergebnisse zu garantieren. Speziell im Funktionenkörperfall über Q wird dabei auf die Ergebnisse des Restklassenkörpers (Zahlkörperfall) zurückgegriffen. Das ursprüngliche Verfahren von Stauduhar wird in vielerlei Hinsicht erweitert, um es speziell für große Grade effizient zu machen. Wir zeigen, wie man durch Berechnung von Teilkörpern des Körpers F(a), wobei a eine Nullstelle von f ist, auf Blocksysteme der Galoisgruppe schließen kann. Somit wird es möglich, die Galoisgruppe in geeignete Kranzprodukte einzubetten und die Einstiegspunkte im Verfahren von Stauduhar variabel zu halten. Weiter wird eine Kombination des Verfahrens mit der absoluten Resolventenmethode vorgestellt, mittels derer die Verwendung extrem großer p-adischer Präzisionen umgangen werden kann. Dadurch wird die Berechnung von primitiven Galoisgruppen höheren Grads überhaupt erst ermöglicht. Darüber hinaus wird der Frobenius-Automorphismus des zugehörigen p-adischen Körpers gewinnbringend eingesetzt, da er Erzeuger einer Untergruppe der Galoisgruppe ist. Durch ihn lassen sich sogenannte verkürzte Nebenklassenrepräsentantensysteme berechnen, die für die zeitkritischen Stellen im Verfahren von Stauduhar enorme Verbesserungen darstellen. Wir beschreiben Berechnungsmethoden der Daten, die für das Verfahren von Stauduhar notwendig sind, und geben Algorithmen an, mittels derer speziell optimierte Invarianten bestimmt werden können. Diese führen zu weiteren erheblichen Verbesserungen für das Laufzeitverhalten der Galoisgruppenberechnung. Den Abschluß bilden eine Vielzahl illustrativer Beispiele, die die Leistungsfähigkeit und die Anwendbarkeit des Verfahrens belegen.de510 MathematikAlgebraische FunktionenkörperAlgebraische ZahlkörperAlgorithmenGaloisgruppenGitterRekonstruktionResolventenDoctoral Thesis