U ber die Berechnung von Teilkorpern
algebraischer Zahlkorper
Diplomarbeit
von
Jurgen Kluners
aus Meerbusch
Angefertigt am Fachbereich 3 Mathematik
der Technischen Universitat Berlin
Berlin 1994
Inhaltsverzeichnis
Kapitel 1. Einleitung
3
Kapitel 2. Grundlagen
5
1.
2.
3.
4.
5.
6.
7.
Algebraische Zahlkorper und deren Teilkorper : : : : : : : : : : : : : : : : : : : : : :
Primideale in der Maximalordnung : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Galoistheorie : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Hensel-Lifting : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Das van der Waerden-Kriterium : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Gitter und LLL-Reduktion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Kettenbruchentwicklung : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Kapitel 3. Bewertungstheorie und p-adische Korper
1.
2.
3.
4.
Bewertungen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
p-adische Korper : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Erweiterungen von p-adischen Korpern : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Unverzweigte p-adische Erweiterungen : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Kapitel 4. Imprimitivitatsgebiete und Blocke
1.
2.
3.
4.
Einfuhrung : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Eigenschaften von Blocken : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Blocke der Galoisgruppe von endlichen Erweiterungen von F p : : : : : : :
Der Zusammenhang zwischen Blocken und Teilkorpern : : : : : : : : : : : : :
1
5
8
11
12
13
16
17
21
21
23
24
25
29
29
30
32
33
2
INHALTSVERZEICHNIS
5.
6.
Berechnung von moglichen Blocken : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 36
Beispiele : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 40
Kapitel 5. Zur Konstruktion von Teilkorpern
1.
2.
3.
4.
5.
6.
7.
Einleitung : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Zur Abschatzung der Koezienten des gesuchten Minimalpolynoms :
Konstruktion von Teilkorpern mit Hilfe des LLL-Algorithmus : : : : : : :
Ein zweites Verfahren zur Berechnung von Teilkorpern : : : : : : : : : : : : :
Zum Hensel-Lifting uber dem Ring oE : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Der allgemeine Fall : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Beispiele : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Kapitel 6. Zur Einbettung von Teilkorpern
1.
2.
3.
4.
5.
Einleitung : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Zur Abschatzung der Koezienten des Einbettungspolynoms : : : : : : :
Das verallgemeinerte Newton-Lifting : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
Bestimmung des Einbettungspolynoms aus der Approximation : : : : : :
Beispiele : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
43
43
44
45
52
57
58
61
65
65
67
69
73
76
Kapitel 7. Beispiele
79
Literaturverzeichnis
87
Bezeichnungen
89
KAPITEL 1
Einleitung
Nach den Pionierarbeiten Kummers wurde bis 1871 nichts uber die Theorie der
algebraischen Zahlen veroentlicht. Dies war das Jahr, in dem Dedekind seine Arbeit uber die Grundlagen der Theorie der algebraischen Zahlen als X. Supplement
zur zweiten Auage der Dirichletschen Vorlesungen uber Zahlentheorie publizierte
[Ded]. In der 1894 veroentlichten vierten Auage ndet man das X. Supplement,
das inzwischen zum XI. Supplement geworden war, in seiner endgultigen Form. Es
ist ein Meisterwerk der mathematischen Literatur, in dem Dedekind neben dem
Begri des Korpers auch den Begri des Moduls einfuhrte, wobei er darunter das
verstand, was wir jetzt einen Teilkorper nennen.
Die Kenntnis der Teilkorper eines gegebenen Zahlkorpers erlaubt einen tieferen
Einblick in seine Struktur. So bemerkt schon Hilbert [Hil]: "Der Galoissche Korper
gestattet ein sehr genaues Studium der Zerlegungsgesetze seiner Zahlen mit Rucksicht auf die in ihm enthaltenen Unterkorper, und die sich hierbei ergebenden
Resultate sind vor allem fur die Anwendung der allgemeinen Korpertheorie auf
besondere Zahlkorper von Wichtigkeit.\
Es besteht also ein groes Interesse, die Teilkorper eines gegebenen algebraischen
Zahlkorpers zu bestimmen. Wir konnten versuchen, zuerst die Galoisgruppe der
normalen Hulle unseres Korpers zu bestimmen, um hiernach mit deren Hilfe die
Teilkorper auszurechnen. Es erweist sich jedoch als zu aufwendig, die Galoisgruppe
auszurechnen.
Dixon stellte 1990 in [Dix1] einen Algorithmus zur Bestimmung aller Teilkorper
eines algebraischen Zahlkorpers vor. Der hier vorgestellte Algorithmus benutzt
Dixons Ideen, verbessert diesen aber entscheidend an verschiedenen Stellen. Unser
Verfahren zur Bestimmung der Teilkorper teilt sich in drei Schritte auf.
3
4
1. EINLEITUNG
Im ersten Teil unseres Verfahrens, den wir im 4. Kapitel unserer Arbeit vorstellen,
wollen wir mogliche Kandidaten fur Teilkorper nden. Wir konnen beweisen, da
es eine Bijektion zwischen den Teilkorpern und ausgezeichneten Imprimitivitatsgebieten (Blocken) der Galoisgruppe gibt. Mit Hilfe des van der Waerden-Kriteriums
[Wae] konnen wir zyklische Untergruppen der Galoisgruppe bestimmen und mit
Kenntnis dieser konnen wir auf passende Blocke zuruckschlieen. Dazu werden
wir Eigenschaften von Blocken herleiten, die wir zur Berechnung dieser einsetzen
werden.
Das 5. Kapitel dieser Arbeit beschaftigt sich mit der Aufgabe, aus den berechneten
Blocken, ein erzeugendes Polynom des gesuchten Teilkorpers zu bestimmen. Hier
entwickeln wir ein neues Verfahren, welches nur mit Hilfe von Faktorisierungen
von Polynomen uber endlichen Korpern und dem Hensel-Lifting uber p-adischen
Korpern die Teilkorper berechnet.
Der letzte Teil unseres Algorithmus, den wir wir im 6. Kapitel vorstellen werden, beschaftigt sich mit der Einbettung des gefundenen Teilkorpers in den gegebenen Korper. Auch hier konnen wir die Berechnungen in p-adischen Korpern
durchfuhren. Es werden jedoch auch kompliziertere zahlentheoretische Methoden
verwandt.
In dieser Arbeit wird erstmalig ein Algorithmus zur Teilkorperberechnung vorgestellt, der auch auf einem Computer implementiert wurde. Mittels dieses Programms besteht die Moglichkeit ezient Teilkorper auszurechnen. Bisher wurden
bei mehr als 1000 Zahlkorper Teilkorper mit ihren Einbettungen bestimmt. Die
Kenntnis solcher Teilkorper ist fur viele Algorithmen der konstruktiven Zahlentheorie von groer Bedeutung. So konnen diese Ergebnisse z.B. dazu benutzt
werden, Ganzheitsbasen oder Einheiten zu berechnen. Bei der Ganzheitsbasenberechnung kann man versuchen, das Problem zuerst im Teilkorper und hiernach
mit relativen Methoden zu losen. Bei der Einheitenberechnung kann man bereits
viele unabhangige Einheiten in den Teilkorpern bestimmen und sie mittels der
berechneten Einbettung in den gegebenen Korper liften. Weiterhin besteht die
Moglichkeit, dieses Verfahren zur Galoisgruppenberechnung einzusetzen. So stellt
der Algorithmus meistens sehr schnell fest, wenn ein Korper primitiv ist, d.h.
keine Teilkorper hat. Auch lassen die berechneten Teilkorper Ruckschlusse auf die
mogliche Galoisgruppe zu.
Wir werden am Ende der Arbeit mit einer groen Anzahl von Beipielen die Leistungsfahigkeit des Verfahrens unterstreichen.
KAPITEL 2
Grundlagen
1. Algebraische Zahlkorper und deren Teilkorper
In dieser Arbeit betrachten wir endliche Korpererweiterungen des Korpers Q .
Hierzu sei ein beliebiges normiertes Polynom f 2 Z[t] gegeben, welches irreduzibel ist. Weiterhin sei eine Nullstelle des Polynoms f . Durch K = Q () wird
eine uber Q algebraische Korpererweiterung vom Grad n deniert, wenn n der
Grad des Polynoms f ist. Eine solche Korpererweiterung heit dann algebraischer
Zahlkorper. Falls nun ein Korper L existiert, fur den Q L K gilt, so wird
dieser als Teilkorper von K bezeichnet. Die Angabe eines Algorithmus zur Berechnung aller Teilkorper L eines gegebenen Korpers K ist das Hauptziel dieser
Arbeit. Zum besseren Verstandnis wollen wir mit einem Beispiel starten.
Beispiel 2.1. Wir betrachten f (t) = t6 + 108. Dieses Polynom erzeugt eine Kor-
pererweiterung vom Grad 6. Sei eine Nullstelle von f . Dieser Korper besitzt 3
Teilkorper vom Grad 3. Alle werden durch
g(t) = ti3 p 108
p das Minimalpolynom
i p
108 und 3 = e 108.
erzeugt. Die Nullstellen von g sind 1 = 108; 2 = e
Wie man leicht sieht, werden durch diese Nullstellen jeweils paarweise verschiedene
Zahlkorper erzeugt, die aber alle isomorph sind. Wir kp
onnen diese Korper aber
durch ihre Einbettung in Q () unterscheiden. Mit = i 108 gilt dann:
3
2
3
3
6
(i) 1 = 2 .
(ii) 2 = 12 2 + 121 5 .
(iii) 3 = 12 2 121 5.
5
4
3
3
6
2. GRUNDLAGEN
Q (i
Q(
p
3
108)
Q (e
2
p
i
3
6
108)
p
3
108)
Q (e
i
4
3
p
3
108)
Q
Da wir alle Teilkorper L eines gegebenen Korpers K bestimmen wollen, mussen
wir isomorphe aber nicht identische Korper unterscheiden. Dies geschieht dadurch,
da wir nicht nur ein Minimalpolynom eines Teilkorpers L, sondern auch seine Einbettung in den Korper K berechnen. Dadurch erhalten isomorphe Teilkorper verschiedene Einbettungen in den Korper K und konnen somit unterschieden werden.
Allerdings kann es auch passieren,
p da manpin dieser Darstellung auch identische
Korper unterscheidet, z.B. Q ( 2) und Q ( 2). Der folgende Satz beschreibt, wie
die Einbettung aussieht. Vorher wollen wir aber noch zwei Begrie klaren.
Definition 2.2. Ein Element 2 K heit ganz (algebraisch), falls einer normierten algebraischen Gleichung
m + b1 m 1 + : : : + bm = 0
mit Koezienten bi 2 Z (1 i m) genugt.
Definition 2.3. Es sei f 2 Z[t] normiert und irreduzibel. Dann heit f erzeugendes Polynom fur den Zahlkorper K , wenn eine Nullstelle von f ein primtives
Element von K ist.
Generalvoraussetzung
Fur den Rest dieses Kapitel bezeichne f ein erzeugendes Polynom des Zahlkorpers
K = Q (), eine Nullstelle und n den Grad von f .


1. ALGEBRAISCHE ZAHLKORPER
UND DEREN TEILKORPER
7
Satz 2.4. Sei ein ganzes Element von K , welches einen Teilkorper L erzeugt.
Dann existiert ein eindeutig gegebenes Polynom h 2 Q [t] derart, da h() = und der Grad von h echt kleiner als n ist.
Beweis: Wir stellen eindeutig in der Potenzbasis (1; ; : : : ; n 1) von K dar,
d.h. es gilt: = b0 + b1 + : : : + bn 1n 1 (bi 2 Q ; 0 i < n). Wir denieren
nun h(t) := b0 + b1t + : : : + bn 1 tn 1. Aufgrund der Konstruktion ist h eindeutig
bestimmt und leistet das Gewunschte.
Die Koezenten von h liegen in Q und nicht notwendigerweise in Z, da als ganzes
Element nicht unbedingt in der Gleichungsordnung Z[] liegen mu. Diesen Eekt
haben wir schon im obigen Beispiel gesehen.
Also kann jeder Teilkorper L durch ein Paar (h; g) mit h 2 Q [t] und g 2 Z[t]
dargestellt werden, fur welches gilt:
(1) L = Q (h()).
(2) g ist Minimalpolynom zu h().
Bevor wir diese Bedingung anders ausdrucken, vereinbaren wir noch eine Schreibweise.
Definition 2.5. Seien !; g und h 2 Z[t] oder Q [t] Polynome. Dann wird folgende
Schreibweise deniert:
g h mod ! genau dann, wenn (g h) in Q [t] von ! geteilt wird.
Satz 2.6. Sei L durch (h; g ) mit h 2 Q [t] und g 2 Z[t] beschrieben. Dann sind
aquivalent:
(1)
(2)
g ist Minimalpolynom zu h().
g ist irreduzibel und g(h) 0 mod f .
Beweis: (1)) (2): Da g Minimalpolynom zu h() ist, ist g nach Denition
irreduzibel. Wir nehmen nun an, da g(h) ! mod f mit ! 2 Q [t] gilt. Wegen
f () = g(h()) = 0 folgt !() = 0 und somit wird ! von f geteilt. Also gilt
g(h) 0 mod f .
(2)) (1): Sei nun umgekehrt g(h) 0 mod f . Daraus folgt dann wegen f () = 0,
da g(h()) = 0 gilt. Da g zudem irreduzibel ist, folgt die Behauptung.
Die vorangegangenen U berlegungen zeigen, da zur Bestimmung der Teilkorper
zwei Dinge berechnet werden mussen. Als erstes mussen die Minimalpolynome
8
2. GRUNDLAGEN
der Teilkorper und dann die Einbettungen berechnet werden. Dieses wird im 4.
bzw. 5. Kapitel dieser Arbeit erlautert werden.
Da die Bedingung f j g(h) in Q [t] sehr haug getestet werden mu, werden wir hier
kurz die Implementierung erlautern. Die Komposition g(h) konnen wir mit Hilfe
des Horner-Schemas ausrechnen. Da der Grad von g(h) sehr gro werden kann und
die Arithmetik uber den rationalen Zahlen durchgefuhrt werden mu, erweist es
sich als ungunstig, zuerst g(h) auszurechnen und hiernach den Rest von g(h) mod f
zu bestimmen. Geschickter ist es, wenn wir wahrend der Berechnung von g(h)
nach jedem Schritt des Horner-Schemas die Koezienten modulo f reduzieren.
Dadurch werden die Grade der Polynome klein gehalten.
2. Primideale in der Maximalordnung
Im folgenden werden wir den Begri der Maximalordnung klaren.
Definition 2.7. Wir denieren oK := f 2 K j ist ganzg als die Menge der
ganz algebraischen Elemente in K .
Die Menge der ganz algebraischen Zahlen ist ein Ring. Zusatzlich gilt der folgende
Satz:
Satz 2.8. Der Ring oK ist ein freier Z-Modul vom Rang n. Ist !1 ; : : : ; !n eine
Z-Basis von oK , so nennen wir sie eine Ganzheitsbasis von K .
Mit Hilfe dieses Satzes konnen wir folgendes denieren:
Definition 2.9. Wir denieren einen unitaren Teilring R von oK , der ein freier
Z-Modul vom Rang n ist, als eine Ordnung des Zahlk
orpers K . Weiterhin bezeichnen wir oK als Maximalordnung von K .
Wir wollen nun auf einige wichtige Eigenschaften der Maximalordnung eingehen.
So ist es sehr angenehm fur die praktische Arbeit, da die Maximalordnung ein
sogenannter Dedekindring ist. Hiermit beschaftigen sich die nachste Denition
und die folgenden Aussagen.
Definition 2.10. Es sei R ein Integritatsring mit 1 und M sein Quotientenkorper.
(i) Eine Teilmenge b 6= ; von M heit gebrochenes Ideal von R, falls 2 R
und ein Ideal a in R existieren mit b = 1 a:
2. PRIMIDEALE IN DER MAXIMALORDNUNG
9
(ii) Falls die gebrochenen Ideale von R eine multiplikative Gruppe bilden, so
bezeichnen wir R als Dedekindring.
Satz 2.11. Ist R ein Dedekindring, so gelten
(i) Jedes Ideal a (a 62 ff0g; Rg) hat eine bis auf Reihenfolge eindeutige Zerlegung
a = p1 : : : pr
in Primideale pi von R (1 i r).
(ii) Jedes Primideal p 6= f0g in R ist maximal.
Wir bezeichnen mit IK die Menge der gebrochenen Ideale in oK . Da die Zerlegung eines Ideals in Primideale eindeutig ist, folgt aus der Gruppeneigenschaft der
gebrochenen Ideale, da auch die gebrochenen Ideale Potenzprodukte von Primidealen sind. Deshalb ist die folgende Denition sinnvoll.
Definition 2.12. Fur ein Primideal p in oK denieren wir:
p() : IK ! Z : a = pk b 7! k;
wobei b in ein Potenzprodukt von Primidealen zerlegt werden kann, welches p nicht
enthalt.
Im folgenden werden wir einige Eigenschaften von Primidealen auisten. Seien
hierzu Q L K algebraische Zahlkorper. Mit oK und oL seien die zugehorigen
Maximalordnungen bezeichnet. Weiterhin sei p ein Primideal von oL und P ein
Primideal von oK . Mit diesen Bezeichnungen gilt das folgende Lemma:
Lemma 2.13. Die folgenden Aussagen sind aquivalent:
(i)
(ii)
(iii)
(iv)
(v)
P j poK
P poK
Pp
P \ oL = p
P\L=p
Falls in oK die Primidealzerlegung poK = Pe1 : : : Pegg in paarweise verschiedene
Primideale gilt, so sind die Primideale fP1 ; : : : ; Pg g gerade die Ideale, die die
Bedingungen des Lemmas erfullen. Daher denieren wir:
Definition 2.14. Erfullen P und p eine der Bedingungen von 2.13, so sagen wir,
da P uber p bzw. p unter P liegt.
1
10
2. GRUNDLAGEN
In der Theorie der Primidealzerlegung spielen die beiden folgenden Begrie eine
wesentliche Rolle.
Definition 2.15. Sei p ein Primideal in oL . Wir betrachten die folgende Prim-
idealzerlegung in paarweise verschiedene Primideale in oK :
poK = Pe1 : : : Pegg :
Dann denieren wir e(Pi =p) := ei als den Verzweigungsindex von Pi uber p. Gilt
e(Pi=p) > 1 fur ein i, so heit p verzweigt in K . Ansonsten heit p unverzweigt.
Als den Tragheitsgrad von Pi uber p bezeichnen wir mit f (Pi =p) den Korpergrad
[(oK =Pi) : (oL=p)].
1
Bemerkung 2.16. Es sei oK die Maximalordnung von K , p 6= f0g ein Primideal
in oK , welches uber pZ liegt und f = f (p=pZ). Dann ist oK =p = F q , wobei F q ein
endlicher Korper mit pf Elementen ist.
Falls K galoissch uber L ist, so konnen wir fur die Zerlegung eines Primideals p
eine noch scharfere Aussage treen.
Satz 2.17. Es sei K eine normale Erweiterung von L und p ein Primideal in oL .
P1 und P2 seien zwei Primideale in oK , die uber p liegen. Dann folgt e(P1 =p) =
e(P2 =p) und f (P1=p) = f (P2 =p).
Wir wollen an dieser Stelle noch anmerken, da wir nur an unverzweigten Primidealen interessiert sind. Diese Einschrankung werden wir noch gezielt ausnutzen.
Die folgenden wichtigen Resultate konnen z.B. in [Mar] entnommen werden.
Satz 2.18. Es sei L ein algebraischer Zahlkorper und K und M zwei endliche und
algebraische Erweiterungen von L. Es sei p ein Primideal in oL , welches in K und
M unverzweigt ist. Dann bleibt p auch in der Komposition KM unverzweigt.
Eine einfache Folgerung aus diesem Satz ist das folgende Korollar.
Korollar 2.19. Es sei L ein algebraischer Zahlkorper und K eine endliche, al-
gebraische Erweiterung von L. Wieder sei p ein Primideal von oL. Falls p unverzweigt in K bleibt, so bleibt p auch unverzweigt in der normalen Hulle M von
K=L.
3. GALOISTHEORIE
11
3. Galoistheorie
Die Galoistheorie ist ein wichtiges Hilfsmittel fur die Berechnung der Teilkorper.
Leider ist es erheblich zu kompliziert, zuerst die Galoisgruppe zu bestimmen, um
mit deren Hilfe die Teilkorper zu berechnen. Trotzdem konnen Teile der Galoistheorie auch sinnvoll fur die Teilkorperberechnung eingesetzt werden. Deswegen
werden wir hier die wichtigsten Aussagen der Galoistheorie auisten. Fur weitere
Aussagen und die Beweise verweisen wir auf die verschiedenen Standard{Werke
der Algebra.
Definition 2.20. Es sei E=F eine endliche Korpererweiterung. Mit Aut(E ) be-
zeichnen wir die Menge der Korperautomorphismen des Korpers E und sei G :=
G(E=F ) := f 2 Aut(E ) j (x) = x fur alle x 2 F g. Die Korpererweiterung
E=F heit galoissch oder Galoiserweiterung, falls E=F normal und separabel ist.
In diesem Fall ist G(E=F ) die zugehorige Galoisgruppe.
Satz 2.21. Hauptsatz der Galoistheorie
Sei E=F endliche Galoiserweiterung. Dann besteht eine Bijektion zwischen den
Teilkorpern F L E und den Untergruppen von G(E=F ) mittels L wird abgebildet auf G(E=L) und umgekehrt. Dabei ist L=F genau dann galoissch, wenn
G(E=L) Normalteiler von G(E=F ) ist. In diesem Falle ist G(L=F ) isomorph zu
G(E=F )=G(E=L).
Damit wir die Galoisgruppe einfacher bezeichnen konnen, wollen wir die folgende
Schreibweise vereinbaren.
Definition 2.22. Es sei F ein Korper und g 2 F [t] ein normiertes Polynom,
welches nicht notwendigerweise irreduzibel ist. Weiterhin seien 1 ; : : : ; m die
Nullstellen von g. Dann bezeichnet Gal(g) die Galoisgruppe von F (1 ; : : : ; m)=F .
Der Hauptsatz der Galoistheorie ist fur beliebige Korpererweiterungen anwendbar.
Noch starkere Aussagen lassen sich aber treen, wenn wir endliche Erweiterungen
von endlichen Korpern betrachten. Dies soll im folgenden Satz getan werden.
Satz 2.23. Es sei p 2
P und K eine endliche Erweiterung von F p vom Grad n,
d.h. K = F q mit q = pn. Dann ist K=F p galoissch mit G(K=F p ) = < >, wobei
der Frobenius-Automorphismus (x 7! xp) ist. Ist L eine Erweiterung von K
vom Grad nm, so ist auch L=K galoissch mit Galoisgruppe G(L=K ) = < > mit
: x 7! xp (x 2 L).
12
2. GRUNDLAGEN
4. Hensel-Lifting
Das Hensel-Lifting liefert eine Methode, eine Kongruenzfaktorisierung modulo eines Ideals b zu einer Kongruenzfaktorisierung modulo bk fur ein beliebiges k 2 N zu
liften. Diese Methode wird z.B. bei der Polynomfaktorisierung angewendet. Dabei
soll ein Polynom f 2 Z[t] faktorisiert werden. Dies geschieht dadurch, da dieses
Polynom modulo pZ[t] faktorisiert wird. Falls keine doppelten Faktoren auftreten,
wird diese Faktorisierung dann mittels des Hensel-Liftings zu einer Faktorisierung
modulo pk Z[t] geliftet, wobei k vom gegebenen Polynom f abhangt. Dann wird
versucht, aufgrund der gewonnenen Kongruenzfaktorisierung Ruckschlusse auf die
Faktorisierung von f 2 Z[t] zu machen. In dieser Arbeit werden wir das HenselLifting auch benutzen, um die sog. Blocke der Galoisgruppe eines Polynoms f zu
berechnen. Hierbei benotigen wir allerdings eine allgemeinere Version des HenselLiftings als beim obigen Verfahren. Diese stellen wir im folgenden Satz vor.
Satz 2.24. Hensel-Lemma
Sei R ein unitarer kommutativer Ring, b ein Ideal von R. Ferner seien f; f10 und
f20 2 R[t] normierte, nicht konstante Polynome, fur die folgendes gilt:
(1)
(2)
f f10f20 mod b[t]
a10 f10 + a20 f20 = 1 + a00 (ai0 2 R[t]; 1 i 2; a00 2 b[t])
Dann kann man fur jedes k 2 N Polynome f1k ; f2k ; a1k ; a2k und a0k bestimmen, so
da folgende Bedingungen erfullt sind:
(1)
(2)
(3)
f f1k f2k mod b2k [t]
fik fi0 mod b[t] (fik 2 R[t] normiert, nicht konstant) (i = 1; 2)
a1k f1k + a2k f2k = 1 + a0k (aik 2 R[t]; deg(aik ) < deg(f3 i;k );
1 i 2; a0k 2 b2k [t])
Der Beweis dieses Satzes kann [PoZa] entnommen werden. Da wir den Algorithmus
fur einen komplizierteren\ Ring benutzen wollen, werden wir ihn im folgenden
auisten. "In einem spateren Teil dieser Arbeit werden wir uns dann uberlegen, wie
wir die arithmetischen Operationen, die fur diesen Algorithmus benotigt werden,
durchfuhren konnen. Die Bezeichnungen stimmen mit denen in [PoZa] uberein, so
da man die Korrektheit des Algorithmus dort sehr gut nachvollziehen kann.
Algorithmus 2.25. Hensel-Lifting
Input:
R; b; k; f; f10; f20 ; a10; a20 ; a00 wie im Satz 2.24.
5. DAS VAN DER WAERDEN-KRITERIUM
Output:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
13
Polynome f1k ; f2k wie im Satz 2.24.
Setze i = 0.
Falls i = k ist, gib f1k und f2k aus und terminiere.
Setze di = f f1i f2i .
Setze d1i = a2i di.
Setze d2i = a1i di.
Setze dji = dji mod fji (Division mit Rest) fur (j = 1; 2).
Setze fj (i+1) = fji + dji fur (j = 1; 2).
Setze bji = aji(a0i + a1id1i + a2i d2i ) fur (j = 1; 2).
Setze aj (i+1) = aji + bji fur (j = 1; 2).
Setze aj (i+1) = aj (i+1) mod f(3 j )(i+1) (Division mit Rest) fur (j = 1; 2).
Setze a0(i+1) = a1i f1i + a2i f2i 1.
Setze i = i + 1 und gehe nach (2).
Im obigen Satz sind die Kongruenzen nur fur zwei Faktoren formuliert. Der Satz
kann aber auch sukzessiv auf mehrere Faktoren angewendet werden, da die einzige
Voraussetzung an die Faktoren ist, da deren ggT 1 ist. Das heit, da die Faktoren
nicht irreduzibel sein mussen. Dies bedeutet, da man mehrere Faktoren zu einem
ausmultiplizieren kann, um danach das Hensel-Lemma auf die verbleibenden zwei
Faktoren anzuwenden. Hiernach kann man f durch den einen neu erhaltenen
gelifteten Faktor dividieren und das Verfahren auf die verbleibenden Faktoren
erneut anwenden.
Zum Abschlu dieses Abschnitts werden wir noch den Begri einer modulo pk Approximation erklaren.
Definition 2.26. Fur p 2 P; k 2 N heit g~ 2 Z[t] eine modulo pk -Approximation
von g 2 Z[t], wenn g g~ mod pk Z[t] gilt. Wir sagen 2 Z ist eine modulo
pk -Approximation eines primitiven Elements eines Zahlkorpers L, wenn g~() 0 mod pk fur ein erzeugendes Polynom g von L ist.
5. Das van der Waerden-Kriterium
In diesem Abschnitt wollen wir einen Satz zur Verfugung stellen, der fur unser Verfahren der Teilkorperberechnung von zentraler Bedeutung ist. Mit dem folgenden
Satz konnen wir mit Hilfe von Kongruenzfaktorisierungen modulo eines Primideals pZ Elemente der Galoisgruppe eines erzeugenden Polynoms eines Korpers
bestimmen. Da die Algorithmen zum Faktorisieren von Polynomen uber endlichen Korpern sehr schnell ist, konnen wir innerhalb kurzester Zeit verschiedene
14
2. GRUNDLAGEN
Elemente der Galoisgruppe bestimmen. Die Kenntnis moglichst vieler Elemente
der Galoisgruppe ist Grundlage des Algorithmus zur Teilkorperberechnung, den
wir in den folgenden Kapiteln vorstellen.
Satz 2.27. van der Waerden-Kriterium
Es seien R ein ZPE-Ring, p ein Primideal in R, R = R=p sein Restklassenring,
E und E die Quotientenkorper von R und R, g ein Polynom aus R[t] und g das g
in der Homomorphie R ! R zugeordnete Polynom, die beide als doppelwurzelfrei
vorausgesetzt werden. Dann ist G =Gal(g) (als Permutationsgruppe der passend
angeordneten Wurzeln) eine Untergruppe der Gruppe G =Gal(g).
Der Beweis dieses Satzes kann in Kapitel 25 von [Wae] entnommen werden. Dies
ist die allgemeine Form dieses Satzes. Weil wir in unserem Verfahren sehr haug
eine spezielle Form dieses Satzes benotigen, stellen wir diese im folgenden Satz
vor.
Satz 2.28. Es sei g 2 Z[t] ein normiertes und irreduzibles Polynom. Ferner
sei ein p 2 P gegeben, welches nicht disc(g) teilt. Es gelte: g(t) g1 (t) : : : gm(t) mod pZ[t]. Dann enthalt Gal(g) eine zyklische Untergruppe U , die von einer Permutation erzeugt wird. Wenn man nun in elementfremde Zykel zerlegt,
so entsprechen die Anzahl der Nullstellen, die in diesen Zykeln permutiert werden,
gerade den Graden der Polynome gi (i = 1; : : : ; m). Weiterhin permutiert gerade
die Nullstellen eines irreduziblen Faktors gi untereinander.
Damit wir die Anwendung dieses Satzes besser verstehen konnen, betrachten wir
im folgenden einige Beispiele zu 2.28. Zur kurzeren Schreibweise schreiben wir nur
g mod p und meinen damit g mod pZ[t].
Beispiel 2.29. Es sei g (t) = t4 + 2 und G =Gal(g ). Die Nullstellen von g seien
mit 1 ; : : : ; 4 bezeichnet. Wir bestimmen im folgenden die Faktorisierungen von
g mod 2; 3; 5; 7.
(i)
(ii)
(iii)
(iv)
g(t) t4 mod 2.
g(t) (t + 2)(t + 1)(t2 + 1) mod 3.
g(t) t4 + 2 mod 5
g(t) (t2 + 6t + 4)(t2 + t + 4) mod 7.
Die erste Faktorisierung ist fur uns unbrauchbar, da g mod 2 doppelte Nullstellen
hat und damit 2 ein Diskrimantenteiler von g ist. Wir konnen den Satz somit nicht
anwenden. In der nachsten Faktorisierung tauchen keine doppelten Nullstellen auf.
3 ist somit kein Diskriminantenteiler und der Satz ist anwendbar. Wir erhalten,
5. DAS VAN DER WAERDEN-KRITERIUM
15
da G eine Permutation enthalt, deren Zerlegung in elementfremde Zykel gerade
so aussieht:
= (1)(2 )(34):
Dabei sollen die Nullstellen passend numeriert sein. Auch die beiden folgenden
Faktorisierungen erfullen die Voraussetzung unseres Satzes. Wir konnen also zwei
weitere Elemente von G bestimmen:
~ = (i i i i ) und = (j j )(j j ):
1
2
3
4
1
2
3
4
Unser Problem bei diesem Satz ist, da wir die Nullstellen i 2 C , die in einem
Zykel liegen, nicht identizieren konnen. Deswegen konnen wir auf diese Weise
nur eine ungefahre Vorstellung von den Elementen der Galoisgruppe bekommen.
Das Element , welches wir im Satz bestimmen, ist der Erzeuger der zyklischen
Galoisgruppe von F q =F p , welche durch das Polynom g erzeugt wird. Dabei ist
g 2 F p [t] das Polynom, welches aus g dadurch entsteht, da alle Koezienten
von g modulo p reduziert werden. Ein Erzeuger dieser Galoisgruppe ist nach 2.23
der Frobeniusautomorphismus , der x auf xp (x 2 F q ) abbildet. Bekanntermaen
kann eine zyklische Gruppe mehrere Erzeuger besitzen. Wenn k die Ordnung und
ein Erzeuger dieser Gruppe ist, so werden alle Erzuger durch j mit 1 j <
k bestimmt, fur die ggT(j; k) = 1 gilt. Wir konnen nun das folgende Lemma
beweisen.
Lemma 2.30. Es gelten die Bezeichnungen dieses Abschnitts. Dann haben alle
Erzeuger der zyklischen Galoisgruppe G von F q =F p den selben Zykeltyp, d.h. die
Langen der elementfremden Zykel sind gleich.
Beweis: Es seien und ~ zwei Erzeuger von G und es gelte die Zerlegung
= 1 : : : u in elementfremde Zykel. Dann existiert ein 1 j < k mit
~ = j und ggT(j; k) = 1. Es sei l die Lange eines beliebigen elementfremden
Zykels i von . Da die Zykellangen der elementfremden Zykeln die Ordnung k
der Gruppe G teilen, folgt ggT(j; l) = 1. Hieraus folgt aber, da ij wieder ein
Zykel der Lange l ist. Damit ist die Behauptung gezeigt.
Wir wollen an dieser Stelle anmerken, da dieses Lemma auch fur den relativen
Fall gilt, d.h. fur die allgemeine Version 2.27. Da in dem Satz nichts uber die
Permutation der Nullstellen in einem Zykel ausgesagt wird, konnen wir fur unsere
Betrachtung davon ausgehen, da wir den Frobeniusautomorphismus bestimmt
haben. Im nachsten Kapitel uber p-adische Korper werden wir noch einmal auf
diese Problematik zuruckkommen.
16
2. GRUNDLAGEN
6. Gitter und LLL-Reduktion
In diesem Abschnitt werden wir Gitter und die LLL-Reduktion von A.K. Lenstra,
H.W. Lenstra und L. Lovasz einfuhren. Die LLL-Reduktion ist eine Reduktion
der Basisvektoren eines Gitters, die 1982 in [LLL] entwickelt wurde. Sie wurde
ursprunglich fur die Faktorisierung von Polynomen mit ganzrationalen Koezienten eingefuhrt. Der Algorithmus hat allerdings gerade in vielen anderen Bereichen
eine sehr groe Bedeutung erlangt. So werden auch wir diesen Algorithmus zur
Teilkorperberechnung einsetzen. Das Wesentliche an dieser Gitterreduktion ist einerseits die polynomielle Laufzeit und andererseits die Abschatzungen, die wir fur
eine LLL-reduzierte Basis angeben konnen.
Definition 2.31. Gitter
(1) Sei n 2 N und eine Teilmenge eines n-dimensionalen Vektorraums Rn . heit Gitter, wenn eine Basis b1 ; : : : ; bn von R n existiert, so da folgendes
gilt:
n
n
X
X
= Zbi = f ribi : ri 2 Z (1 i n)g:
i=1
i=1
In diesem Fall heit b1 ; : : : ; bn Basis und n der Rang oder die Dimension
von .
(2) Die Determinante d() des Gitters ist deniert durch:
d() = j det(b1; : : : ; bn)j;
wobei die bi als Spaltenvektoren geschrieben werden. d() ist eine positive
reelle Zahl, die nicht von der Wahl der Basis abhangt (vgl. [Cas1]).
In der folgenden Denition werden Groen deniert, die beim Gram-SchmidtOrthogonalisierungsverfahren benotigt werden.
Definition 2.32. Seien b1 ; : : : ; bn 2 R n linear unabhangig. Die Vektoren bi (1 i n) und die reellen Zahlen ij (1 j < i n) werden dann induktiv wie folgt
deniert:
b
i
= bi
i 1
X
j =1
ij bj ;
(b ; b )
ij = (bi ; bj) ;
j j
wobei (; ) das kanonische innere Produkt auf dem R n bezeichne.
7. KETTENBRUCHENTWICKLUNG
17
Definition 2.33. Eine Basis b1 ; : : : ; bn eines Gitters heit LLL-reduziert, falls
die beiden folgenden Bedingungen erfullt sind:
j ij j 21 fur 1 j < i n
j bi + ii 1bi 1 j2 43 j bi 1 j2 fur 1 < i n:
Hierbei bezeichne j j die euklidische Lange.
Im weiteren kann man jetzt mehrere Abschatzungen fur eine LLL-reduzierte Basis
angeben, welche in [LLL, Poh] nachgelesen werden konnen. Wir benotigen lediglich
das folgende:
Satz 2.34. Sei ein Gitter mit LLL-reduzierter Basis b1 ; : : : ; bn . Dann gelten
die beiden folgenden Abschatzungen.
d() jb1 j2 n
Y
jbi j
i=1
2n 1jxj2 fur
(2-1)
alle x 2 ; x 6= 0
(2-2)
Beweis: (2-1) ist die bekannte Hadamardsche Ungleichung. Die Gleichung (2-2)
wird in [LLL] gezeigt.
Wir haben jetzt einige Eigenschaften einer LLL-reduzierten Basis beschrieben.
Bis jetzt ist oen geblieben, wie wir eine solche Basis berechnen konnen. Dieser
Algorithmus wird z.B. in [LLL, Poh, PoZa] aufgefuhrt. Wir mochten daher an
dieser Stelle darauf verzichten, diesen Algorithmus aufzufuhren.
7. Kettenbruchentwicklung
In diesem Abschnitt werden wir die grundlegenden Begrie der Kettenbruchentwicklung denieren. Wir benotigen die Kettenbruchentwicklung, um die Korrektheit unseres Einbettungsalgorithmus zu beweisen. Eine andere Anwendung der
Kettenbruchentwicklung ist zum Beispiel das Erkennen von irrationalen Zahlen.
So ist eine reelle Zahl genau dann rational, wenn ihre Kettenbruchentwicklung
endlich ist. Kommen wir nun zu den wichtigsten Denitionen und Eigenschaften. Die Beweise dieser werden in [Khi] gefuhrt. Dieses Buch sei auch denjenigen
empfohlen, die mehr uber die Kettenbruchentwicklung erfahren wollen. Anzumerken bleibt noch, da wir in unserer Arbeit nur endliche Kettenbruche uber
den naturlichen Zahlen betrachten. Deswegen werden wir hier auch nur diesen
Spezialfall denieren.
18
2. GRUNDLAGEN
Definition 2.35. Kettenbruche
(1) Einen Ausdruck der Form
a0 +
1
a1 + a + 1 2
+ a1n
bezeichnen wir als n-gliedrigen Kettenbruch. Dabei soll a0 2 Z und fur
1 i n ai 2 N sein.
(2) Der einfacheren Schreibweise wegen schreiben wir einen solchen Kettenbruch in der Form:
[a0; a1 ; a2; : : : ; an]:
(3) Ferner bezeichnen wir fur 0 i n
rk = [ak ; ak+1; : : : ; an]
als den Rest des endlichen Kettenbruches.
(4) Einen Kettenbruch sk = [a0 ; a1; : : : ; ak ] mit k n bezeichnen wir als Abschnitt des endlichen Kettenbruches [a0 ; a1 ; a2 ; : : : ; an]:
Um besser arbeiten zu konnen, denieren wir rekursiv eine kanonische Darstellung
fur unsere Kettenbruche: Fur einen 0-gliedrigen Kettenbruch [a0] setzen wir die
Darstellung a1 und fur n-gliedrige Kettenbruche schreiben wir:
[a0 ; a1; a2; : : : ; an] = [a0 ; r1] = a0 + 1 :
r1
Dabei ist r1 der Rest unseres Kettenbruches. Da r1 selbst nur (n 1)-gliedrig
ist,
0
p
haben wir bereits eine kanonische Darstellung deniert. Es gilt: r1 = q0 . Hieraus
folgt dann:
q 0 a p0 + q 0
[a0 ; a1; a2; : : : ; an] = a0 + 0 = 0 0 :
p
p
Dieser letzte Bruch soll die kanonische Darstellung unseres Kettenbruches sein.
Definition 2.36. Die kanonischen Darstellungen des Abschnittes
sk = [a0 ; a1 ; : : : ; ak ] (k n)
denieren wir als Naherungsbruch der Ordnung k von [a0 ; a1 ; a2 ; : : : ; an] und bezeichnen ihn in der Form pqkk :
0
Im folgenden werden wir einige Ergebnisse auisten, die wir fur unsere Beweise in
den spateren Kapiteln benotigen werden.
7. KETTENBRUCHENTWICKLUNG
19
Satz 2.37. Bildungsgesetz der Naherungsbruche
Fur ein beliebiges k 1 gilt:
pk = ak pk 1 + pk 2 und qk = ak qk 1 + qk 2:
Dabei setzen wir p 1 = 1 und q 1 = 0.
Beweis: Dieser Satz entspricht Satz 1 in [Khi].
Satz 2.38. Fur ein beliebiges 1 k n gilt:
p r +p
[a0 ; a1; a2 ; : : : ; an] = k 1 k k 2 :
qk 1rk + qk 2
Hierbei gehoren die pi; qi und ri zu dem links in der Gleichung stehenden Kettenbruch.
Beweis: Der Beweis steht in Satz 5 von [Khi].
Satz 2.39. Jeder unkurzbare Bruch ab , der der Ungleichung
j ab j < 21b2
genugt, ist ein Naherungsbruch der Zahl . Hierbei ist = [a0 ; a1; a2 ; : : : ; an].
Beweis: Dieses Ergebnis wird in Satz 19 von [Khi] bewiesen.
20
2. GRUNDLAGEN
KAPITEL 3
Bewertungstheorie und p-adische Korper
Fur die Durchfuhrung unseres Algorithmus mussen wir Berechnungen in sogenannten p-adischen Vervollstandigungen algebraischer Zahlkorper durchfuhren. Hierzu
stellen wir nun die wichtigsten Ergebnisse dieser Theorie vor. Die folgenden Aussagen werden u.a. in [PoZa] und [Nar] bewiesen.
1. Bewertungen
Als erstes werden wir den Begri einer Bewertung einfuhren.
Definition 3.1. Sei K ein Korper und : K ! R eine Abbildung mit den
folgenden Eigenschaften:
(i)
(ii)
(iii)
(iv)
(1) = 1
(x) 0; (x) = 0 , x = 0 ; 8x 2 K
(x y) (x) + (y) ; 8x; y 2 K
(x y) = (x) (y) ; 8x; y 2 K
heit dann Bewertung des Korpers K . Gilt statt (iii) die starkere Bedingung
(x y) max( (x); (y)); 8x; y 2 K;
so bezeichnen wir als nicht-archimedische Bewertung des Korpers K , oder kurz
als Krullbewertung. Andernfalls bezeichnen wir als archimedische Bewertung.
Bemerkung 3.2. Ist eine Bewertung des Korpers K , so wird durch
d(x; y) := (x y)
eine Metrik auf K deniert.
21
22

3. BEWERTUNGSTHEORIE UND p-ADISCHE KORPER
Damit wir den Begri der Bewertung etwas besser verstehen konnen, betrachten
wir drei Beispiele von Bewertungen. Hierbei ist fur uns besonders das 3. Beispiel
von besonderer Bedeutung.
Beispiel 3.3. (Archimedische und nicht-archimedische Bewertungen)
(i)
Die triviale Abbildung
8
<
: K ! R : x 7! :0 falls x = 0
1 sonst
ist immer eine nicht-archimedische Bewertung.
(ii) Der gewohnliche Absolutbetrag ist eine archimedische Bewertung auf Q .
(iii) Sei K ein algebraischer Zahlkorper und p ein Primideal in oK . Sei die
Funktion p wie in 2.13 deniert. Dann wird durch
8
< p x falls x 6= 0
jxjp; := :0
falls x = 0
( )
mit 2]0; 1[ eine nicht-archimedische Bewertung auf K deniert. Wir
nennen eine solche Bewertung eine p-adische Bewertung auf K .
Definition 3.4. Eigenschaften von Bewertungen
(i)
(ii)
Es seien 1 und 2 zwei Bewertungen auf einem Korper K . Dann heien
diese Bewertungen aquivalent, falls
8; 2 K : 1 ( ) < 1 () , 2 ( ) < 2 ()
gilt.
Ist eine Krullbewertung, deren Bild des Denitionsbereiches zyklisch ist,
so heit diskret.
eine Krullbewertung auf einem Korper K . Dann ist
R := fx 2 K j (x) 1g
ein lokaler Ring mit dem maximalen Ideal
m := fx 2 K j (x) < 1g:
Satz 3.5. Es sei
Wir bezeichnen R als den Bewertungsring und m als das Bewertungsideal von
.

2. p-ADISCHE KORPER
23
Da wir sehr an Bewertungen auf algebraischen Zahlkorpern interessiert sind, stellt
sich uns die Frage, wie diese dort aussehen. Hierauf gibt uns der folgende Satz
eine Antwort.
Satz 3.6. Es sei K ein algebraischer Zahlkorper uber Q . Dann ist jede nicht
triviale Bewertung von K entweder diskret oder archimedisch. Ist eine diskrete
Bewertung, so existiert ein Primideal p von oK und ein 2]0; 1[ mit:
(x) = p(x) 8x 2 K 6=0
Ist
aber eine archimedische Bewertung auf K , so gilt
(x) = j(x)j 8x 2 K;
wobei einer der Q -Isomorphismen von K ist.
Um mit den Bewertungen besser arbeiten zu konnen, ist der folgende Satz von
groer Bedeutung.
Satz 3.7. Es sei eine beliebige diskrete Bewertung uber einem algebraischen
Zahlkorper K . Dann hat sie nach dem vorherigen Satz die Form (x) = p () fur
ein 2]0; 1[. Eine Bewertung ~ auf K ist genau dann aquivalent zu , wenn ein
2]0; 1[ existiert, so da ~ = p() gilt. Weiterhin besitzen aquivalente Bewertungen den gleichen Bewertungsring und das gleiche Bewertungsideal.
In 3.3 haben wir die Bewertung j jp; uber dem algebraischen Zahlkorper K
deniert. Da wir nicht an den eigentlichen Funktionswerten dieser Bewertung,
sondern an dem Bewertungsring und dem Bewertungsideal interessiert sind, ist das
fur uns von untergeordneter Bedeutung. Wir sprechen daher fur ein beliebiges
Primideal von oK von der Bewertung jjp und meinen eine beliebige von p erzeugte
Bewertung.
2. p-adische Korper
Eine sehr wichtige Eigenschaft bildet die Vervollstandigung algebraischer Zahlkorper bezuglich eine Primideals p. Dazu betrachten wir den folgenden Satz.
Satz 3.8. Es sei K ein algebraischer Zahlkorper und p ein Primideal seiner Maximalordnung. Dann existiert ein Korper Kp K mit den f olgenden Eigenschaften:
(i)
Kp ist vollstandig bzgl. der von der Fortsetzung von j jp auf Kp erzeugten
Metrik. Diese Fortsetzung wird ebenfalls mit j jp bezeichnet.
24

3. BEWERTUNGSTHEORIE UND p-ADISCHE KORPER
(ii) K liegt dicht in Kp .
(iii) Ist R ein minimales Restsystem von oK =p mit 0 2 R und ist 2 p n p2 , so
gilt:
1
X
Kp = f i i j i 2 R; m 2 Z; m 6= 0g:
i=m
Die Fortsetzung von j jp auf Kp ist wieder eine diskrete Bewertung. Damit ist
1
X
Rp = f
i =m
ii j i 2 R; m 2 Z0; m 6= 0g
der Bewertungsring von j jp in Kp. Er ist ein lokaler Hauptidealring mit dem
maximalen Ideal
mp = f
1
X
i =m
ii j i 2 R; m 2 Z1; m 6= 0g:
Weiterhin wollen wir noch anmerken, da die Restklassenkorper Rp=mp und oK =p
isomorph zueinander sind.
3. Erweiterungen von p-adischen Korpern
In diesem Abschnitt werden wir einige Aussagen uber p-adische Erweiterungen
treen.
Satz 3.9. Es sei M=Kp eine endliche Erweiterung vom Grad n. Dann existiert

eine bis auf Aquivalenz
eindeutige Fortsetzung j j von j jp auf M mit:
M ist vollstandig bzgl. j j.
jxj = jNM=Kp (x)j1p=n 8x 2 M .
Definition 3.10. Es sei M=Kp eine endliche Erweiterung vom Grad n. p ist das
Primideal des Bewertungrings S von Kp und P das Primideal des Bewertungrings
R von M . Die Zahl e mit der Eigenschaft pR = Pe heit Verzweigungsindex der
Erweiterung M=Kp . Die Zahl f = [(R=P) : (S=p)] heit Tragheitsgrad der Erweiterung M=Kp. Es gilt bekanntlich n = ef . Eine Erweiterung heit unverzeigt,
falls e = 1 ist.
Satz 3.11. Es sei K=L eine Relativerweiterung vom Grad n und jjp eine Bewertung auf L. Gilt dann poK = Pe1 : : :Pegg , so sind die Bewertungen jjPi (1 i g)
alle inaquivalenten Fortsetzungen von j jp nach K .
(i)
(ii)
1
4. UNVERZWEIGTE p-ADISCHE ERWEITERUNGEN
25
Satz 3.12. Mit den Bezeichnungen des letzten Satzes gilt:
ei = e(KPi =Lp) und f (Pi=p) = f (KPi =Lp):
4. Unverzweigte p-adische Erweiterungen
Wir hatten schon einmal kurz erwahnt, da wir nur an unverzweigten p-adischen
Erweiterungen interessiert sind. Diese haben einige sehr schone Eigenschaften,
die wir im folgenden auisten wollen. Sei also Kp=Q p eine p-adische Erweiterung.
Sie heit unverzweigt genau dann, wenn der Verzweigungsindex e von p uber pZp
gerade 1 ist. Die folgenden Aussagen werden in [Nar] bewiesen. In den folgenden
Satzen sei KP=Lp eine p-adische Erweiterung. R sei der Bewertungsring von K
und S der Bewertungsring von L. P und p seien die Bewertungsideale von K bzw.
L.
Satz 3.13. Eine Erweiterung KP =Lp ist unverzweigt genau dann, wenn ein Element a 2 R existiert, fur das die folgenden Bedingungen erfullt sind:
(i)
(ii)
L = K (a), wobei a Nullstelle eines normierten Polynoms F 2 S [t] ist.
a mod P ist eine einfache Nullstelle von F mod p.
Aus diesem Satz konnen wir mehrere einfache Folgerungen ziehen.
Korollar 3.14. Es sei KP =Lp eine unverzweigte und M=Q p eine endliche Erweiterung. Dann ist KPM=Lp M wieder eine unverzweigte Erweiterung.
Korollar 3.15. Es seien KP =Lp und M=Lp unverzweigte Erweiterungen. Dann
sind MKP =Lp wieder unverzeigt.
Im folgenden bezeichnen wir mit K und L die zugehorigen Restklassenkorper. Der
folgende Satz stellt eine wichtige Beziehung zwischen unverzweigten Erweiterungen
und den endlichen Korpern auf.
Satz 3.16. Es sei Lp =Q p eine p-adische Erweiterung. Dann existiert zu jeder end L genau eine unverzweigte Erweiterung KP=Lp derart, da
lichen Erweiterung K=
K und der Restklassenkorper von KP isomorph zueinander sind. Diese Erweite L .
rung ist normal und die Galoisgruppe ist isomorph zu der Galoisgruppe von K=
Aus diesem Satz konnen wir wieder wichtige Folgerungen ziehen.
Korollar 3.17. Es existiert genau eine unverzweigte Erweiterung von
fest vorgebenen Grad.
Qp
mit
26

3. BEWERTUNGSTHEORIE UND p-ADISCHE KORPER
Korollar 3.18. Falls KP =Lp unverzweigt ist, so ist die Galoisgruppe zyklisch.
Ein Erzeuger dieser zyklischen Gruppe ist der sogenannte Frobeniusautomorphismus. Er induziert den Frobeniusautomorphismus der Galoisgruppe von der Erweiterung der zugehorigen Restklassenkorper.
Wir haben also festgestellt, da es nur eine unverzweigte Erweiterung von Q p gibt,
die einen fest vorgegebenen Grad hat. Diese Erweiterung korrespondiert zu der
Erweiterung der zugehorigen Restklassenkorper. So hat sie gleichen Grad und
gleiche Galoisgruppe. Beide Galoisgruppen werden vom Frobeniusautomorphismus erzeugt.
Zum Abschlu dieses Abschnitts betrachten wir noch einen wichtigen Satz zur Darstellung des Bewertungsrings bzw. der Maximalordnung eines p-adischen Korpers,
wie er in [Cas2] zu nden ist.
Satz 3.19. Es sei Kp =Q p eine unverzweigte Erweiterung vom Grad m. Weiterhin seien 1 ; : : : ; m die Vertreter einer Basis von (oKp =p)=(Zp=pZ). Dann ist
1; : : : ; m eine Basis fur die Maximalordnung oKp .
Fur die Praxis bedeutet dieser Satz, da wir ein erzeugendes Polynom fur die
Korpererweiterung unseres Restklassenkorpers kanonisch in Zp[t] einbetten. Die
von diesem Polynom erzeugte Gleichungsordnung ist dann bereits maximal.
Zum Abschlu dieses Kapitels wollen wir noch eine Anwendung des van der Waerden-Kriteriums 2.28 vorstellen.
Satz 3.20. Sei f 2 Z[t] ein irreduzibles, normiertes Polynom und sei ferner p
eine Primzahl fur die f mod p keine doppelten Nullstellen besitzt. Sei nun das
Element der Galoisgruppe von f , welches durch 2.28 bestimmt wurde. Sei k ein
Teiler des Grades der p-adischen Erweiterung E =Q p , die durch f erzeugt wird.
Dann erhalt man durch durch das Faktorisieren von f in einer unverzweigten
Erweiterung vom Grad k uber Q p die Aktion von k im Sinne von 2.28.
Bemerkung 3.21. Damit keine Miverstandnisse auftreten konnen, wollen wir
an dieser Stelle bemerken, wie die Erweiterung E =Q p erzeugt wurde. Sei hierzu
f~ die kanonische Einbettung von f in Zp[t]. Die Nullstellen von f~ seien mit
~1; : : : ; ~n bezeichnet. Dann ist E = Q p (~1 ; : : : ; ~n).
Wir kommen nun zum Beweis des Satzes.
Beweis: Die unverzweigte Erweiterung vom Grad k uber Q p sei mit F bezeichnet.
Sei p das maximale Ideal in der Maximalordnung oF von F . Das Faktorisieren von
4. UNVERZWEIGTE p-ADISCHE ERWEITERUNGEN
27
f in F [t] entspricht der Faktorisierung von f mod p. Mittels dieser Faktorisierung
wird nach 2:28 der Frobeniusautomorphismus ~ der Erweiterung EF =F ausgerechnet. In der Voraussetzung hatten wir bereits den Frobeniusautomorphismus
der Erweiterung E =Q p bestimmt. Wir zeigen nun, da fur die Frobeniusautomorphismen der Zusammenhang k = ~ jE gilt. Hierzu betrachten wir folgende
Abbildung:
EF
~
E
F
n
k
Qp
Wir bezeichnen den Frobeniusautomorphismus von EF =Q p mit . Aus der Galoistheorie ist bekannt, da ~ = k gilt. Weiterhin ist oensichtlich, da = jE
gilt. Damit erhalten wir folgende Gleichung:
~ jE = k jE = k :
Da die Nullstellen von f alle in E liegen und wir an der Aktion von ~ auf diesen
Nullstellen interessiert sind, ist damit die gewunschte Behauptung gezeigt.
28

3. BEWERTUNGSTHEORIE UND p-ADISCHE KORPER
KAPITEL 4
Imprimitivitatsgebiete und Blocke
Als Generalvoraussetzung fur dieses Kapitel sei G Untergruppe der symmetrischen
Gruppe Sn. Dabei soll G stets auf = f1; : : : ; ng operieren. Zusatzlich sei
= 1 : : : u 2 G stets in elementfremde Zykel zerlegt.
1. Einfuhrung
Definition 4.1. Eigenschaften von G
(1) G heit transitiv, falls fur alle 1 i; j n ein g 2 G existiert mit gi = j .
(2) Sei und g 2 G. Dann ist g := f 2 j = g mit 2 g.
(3) Sei ; =
6 . Dann heit Block (Imprimitivitatsgebiet), falls fur alle
g 2 G gilt: g \ 2 f;; g.
(4) = fig (1 i n) und = sind die sogenannten trivialen Blocke,
die anderen heien nicht triviale Blocke.
(5) Sei G transitiv. Falls G einen nicht trivialen Block besitzt, so heit G
imprimitiv, andernfalls heit G primitiv.
(6) Die Anzahl der Elemente eines Blockes wird als Groe bzw. als Blockgroe
bezeichnet.
(7) Blocke 1 ; : : : ; m heien (komplettes) Blocksystem von G, falls folgendes
gilt: S
i = .
(a)
1im
(b) i \ j = ; fur i 6= j .
(c) Alle Blocke haben die gleiche Blockgroe.
(8) Die Blocke, die in einem Blocksystem liegen, heien zueinander konjugiert.
29

4. IMPRIMITIVITA TSGEBIETE UND BLOCKE
30
Der folgende Satz beinhaltet die ersten einfachen Folgerungen aus der Denition
von Blocken. Der Beweis kann [Hup] entnommen werden.
Satz 4.2. Sei G imprimitiv und sei ein nicht
S trivialer Block. Sei H := Gfg :=
fg 2 G j g = g. Sei weiterhin G = r2R Hr die Nebenklassenzerlegung von
G nach H . Dabei sei R ein vollstandiges, minimales Restsystem. Dann gelten
folgende Behauptungen:
(1)
(2)
(3)
(4)
Es ist = S r mit r \ r0 = ; fur r 6= r0 (r; r0 2 R).
r2R
Mit ist fur g 2 G auch g ein Block.
Es gilt: j j=j jj R j.
Die Untergruppe H ist transitiv auf .
Insbesondere bilden die r ; r 2 R ein Blocksystem von G.
2. Eigenschaften von Blocken
In diesem Abschnitt wollen wir Eigenschaften von Blocken einer Gruppe G
herleiten. Grundlage hierfur ist die Kenntnis von einzelnen Elementen der Gruppe
G. Die Untersuchung dieses Sachverhalts ist deswegen von besonderer Bedeutung,
da wir mit Hilfe des van der Waerden-Kriteriums 2.28 zyklische Untergruppen der
Galoisgruppe G und deren Erzeuger erkennen konnen.
Wirr konnen nun die folgenden Begrie denieren.
Definition 4.3. Bezeichnungen fur Zykel
(1) Die Anzahl der Elemente, die in einem Zykel permutiert werden, bezeichnen wir als Lange eines Zykels.
(2) Wir sagen ein Element ist vom Zykeltyp [n1 ; : : : ; nu], wenn die Lange der
i gerade den ni (1 i u) entspricht.
O.E. seien die i (1 i u) gema ihrer Lange aufsteigend geordnet. Das folgende
Lemma liefert uns eine erste Eigenschaft.
Lemma
4.4. Sei G transitiv und ein Block von G. Sei k die kleinste Zahl mit
k
= . Falls ein Zykel l der Lange nl ein Element von einem Block enthalt,
so wird nl von k geteilt und l enthalt exakt nkl Elemente von .

2. EIGENSCHAFTEN VON BLOCKEN
31
Beweis: Sei ein nicht trivialer Block. Wegen \ 2 f;; g existiert
ein k 1 mit k = und j \ = ; fur 1 j < k. Seien o.E. die
ni (1 i n) so nangeordnet, da l = (1 : : : nl ) und 1 2 gilt. Wegen
l l = id folgt l \ 6= ;. Da k die kleinste Zahl mit dieser Eigenschaft
war, wird nl von k geteilt. lk zerfallt somit in k Zykel der Lange nkl und es
gelte, da 1 im ersten der so entstandenen Zykel enthalten ist. Waren noch in
einem weiteren so entstandenem Zykel Elemente aus enthalten, so muten alle
Elemente dieses Zykels in enthalten sein. Da jeder Zykel von lk genau ein
Element von f1; : : : ; k g enthalt, mute ein i (2 i k) in diesem weiteren
Zykel enthalten sein. Dann gilt aber li 11 = i und somit ist i 2 \ i
mit (i 1) < k. Dies ist aber ein Widerspruch.
Das k im Lemma ist von so groer Bedeutung fur unsere weiteren Betrachtungen,
da wir dies in einer Denition festhalten wollen.
Definition 4.5. Sei G transitiv und ein Block von Gk. Dann ist der k-Wert
k(; ) als die kleinste naturliche Zahl deniert, mit = . Wenn klar ist,
auf welches sich der k-Wert bezieht, so wird dies meistens weggelassen. Falls
1; : : : ; m ein komplettes Blocksystem ist, so bezeichnen k1; : : : ; km die k-Werte
zu 1 ; : : : ; m (bezogen auf eine feste Permutation ).
1
Generalvoraussetzung:
Im folgenden sei 1; : : : ; m ein komplettes Blocksystem von Blocken der Groe
d einer Gruppe G. Mit k1; : : : ; km werden die k-Werte zu 1 ; : : : ; m bezeichnet.
In den folgenden Satzen wird eine noch genauere Aussage uber die Verteilung der
i in den Blocken j getroen.
Satz 4.6. Wenn zwei Blocke r und s mit r 6= s Elemente eines Zykels l
enthalten, so folgt kr = ks.
Beweis: Oensichtlich gelten kr ; ks > 1. O.E. seien die Elemente aus so angeordnet, da l = (1 : : : nl ) und 1 2 r gilt. Dann existiert ein j 2 N minimal
mit lj 1 2 s. Wegen 4.2 (2) wird durch lj jedes Element von (1 : : : nl ) \ r
auf ein Element aus (1 : : : nl ) \ s abgebildet. Analog existiert ein ~j , so da
durch l~j jedes Element von (1 : : : nl ) \ s auf ein Element aus (1 : : : nl ) \ r
abgebildet wird. Damit ist gezeigt, da diese beiden Mengen gleich machtig sind
und es folgt kr = ks.
Satz 4.7. Es enthalte sowohl r als auch s Elemente eines Zykels l . Fur 1 i u gilt dann: Falls r Elemente aus i enthalt, so auch s (und umgekehrt).
32

4. IMPRIMITIVITA TSGEBIETE UND BLOCKE
Beweis: Nach 4.6 enthalten r und s jeweils gleichviele Elemente von l . Seien
nun und Elemente von l und gelte 2 r und 2 s. Dann existiert ein
j 2 N mit j = . Sei nun ein beliebiges anderes Element aus r , welches nicht
in l enthalten ist. Falls ein solches Element nicht existiert, ist die Aussage trivial.
Nach 4.2 (2) gehort j = zum selben Block wie j = . Weiterhin gehoren
nach Konstruktion und dem selben Zykel i an. Damit ist die Behauptung
gezeigt.
Korollar 4.8. Sei ein Block von G. Sei k der zugehorige k-Wert zu . Dann
sind durch die k 1 konjugierten Blocke, die Elemente aus den selben Zykeln
enthalten wie , eindeutig bestimmt und konstruierbar.
Beweis: Sei 2 G mit dem zugehorigen k-Wert gegeben. Nach den vorangegangenen Satzen ist es klar, da es genau k 1 konjugierte Blocke gibt, die Elemente
aus den gleichen Zykeln wie entnehmen. Sei aus s Zykeln konstruiert und
seien diese Zykel so aufgebaut, da jeweils das erste Element zu gehort. Analog
zu den vorangegangenen Satzen wird durch j (1 j < k) auf die konjugierten
Blocke abgebildet. Dies bedeutet, da in jedem der s Zykel je eins der ersten k
Elemente zu einem konjugierten Block von gehort.
Die Konstruierbarkeit basiert allerdings auf der Annahme, da die Aktion von auf vollstandig bekannt ist. Dies ist bei unserer Anwendung i.allg. aber nicht
der Fall. Deswegen beschaftigen sich in den nachsten Abschnitten noch weitere
Satze mit diesem Problem.
3. Blocke der Galoisgruppe von endlichen Erweiterungen von F p
In diesem Abschnitt sollen die Ergebnisse, die wir bisher uber Blocke erhalten
haben, angewendet werden. Bekanntermaen sind endliche Erweiterungen von
endlichen Korpern galoissch mit zyklischer Galoisgruppe G. Die Elemente aus werden ab jetzt auch als Wurzeln bezeichnet. Wir betrachten im weiteren folgende Ausgangsposition als weitere Generalvoraussetzung fur den Rest dieses
Kapitels:
Sei f 2 Z[t] normiert und irreduzibel, und sei ein p 2 P derart gegeben, da
f (t) mod pZ[t] keine doppelten Nullstellen besitzt. Weiterhin gelte:
f (t) f1(t) : : : fu(t) mod pZ[t],
wobei die fi (1 i u) in F p [t] irreduzibel sind.


4. DER ZUSAMMENHANG ZWISCHEN BLOCKEN
UND TEILKORPERN
33
Nach dem van der Waerden-Kriterium 2.28 enthalt Gal(f ) (betrachtet als Erweiterung uber Q ) eine zyklische Untergruppe H mit Erzeuger , wobei vom
Zykeltyp [n1 ; : : : ; nu] ist. Die ni (1 i u) entsprechen dabei gerade den Graden der fi. Ein "Schonheitsfehler\ dieser Aussage ist, da man die Wurzeln nicht
richtig unterscheiden kann. Dazu soll der folgende Satz, der auf 4.8 aufbaut, einen
Losungsansatz aufzeigen.
Satz 4.9. Sei der Erzeuger einer zyklischen Untergruppe H von G, wobei die
i (1 i u) auf den Wurzeln der fi operieren. Sei nun ein Block von G.
Dann konnen die zu konjugierten Blocke, die aus den selben Zykeln konstruiert
sind, modulo p eindeutig bestimmt werden.
Bemerkung 4.10. An dieser Stelle wollen wir die Aussage des letzten Satzes
verdeutlichen. Wir haben schon ofters erwahnt, da wir mit Hilfe des van der
Waerden-Kriteriums 2.28, die Nullstellen in einem Block nur modulo p, d.h. im
zugehorigen endlichen Korper, bestimmen konnen. Auf diese Art und Weise ist
die Konstruierbarkeit zu verstehen.
Kommen wir nun zum Beweis des Satzes.
Beweis: ist Erzeuger der zyklischen Galoisgruppe von F q =F p , wobei F q =
F p (1 ; : : : ; n ) ist. Die 1 ; : : : ; n sollen hierbei die Nullstellen von f in einer
passenden Erweiterung von F p sein. Ein Erzeuger dieser Galoisgruppe ist nach
2.23 durch den Frobeniusautomorphismus mit (x) = xp gegeben. Seien nun die
Zykel, die Elemente von enthalten, so angeordnet, da jeweils die erste Wurzel
zu gehort. Die Elemente des i-ten Zykels seien mit i ; : : : ; ini bezeichnet.
j
Dann gilt mit dem Frobeniusautomorphismus: ij = ip . Damit konnen die
gewunschten konjugierten Blocke bestimmt werden.
1
1
1
4. Der Zusammenhang zwischen Blocken und Teilkorpern
In diesem Abschnitt betrachten wir den Zusammenhang zwischen den Teilkorpern
von K = Q () und den Blocken von G =Gal(f ), wobei Nullstelle eines irreduziblen und normierten Polynoms f 2 Z[t] ist. Dabei stellt sich heraus, da
ahnlich zum Hauptsatz der Galoistheorie eine Bijektion zwischen den Teilkorpern
von K und den Blocken von G existiert, die enthalten. Mit Hilfe dieser Aussage
konnen wir dann die bisherigen Ergebnisse uber Blocke anwenden und diese zur
Teilkorperberechnung einsetzen. Das folgende Ergebnis kann [Dix1] entnommen
werden.
34

4. IMPRIMITIVITA TSGEBIETE UND BLOCKE
Satz 4.11. Sei f 2 Z[t] normiert und irreduzibel vom Grad n, und sei eine Nullstelle von f . Sei weiterhin K = Q () ein algebraischer Zahlkorper und G =Gal(f ).
Dann existiert eine Bijektion zwischen den Teilkorpern von K vom Grad m und
den Blocken der Groe d von G, die enthalten. Zusatzlich gilt n = md.
Beweis: Sei L ein beliebiger Teilkorper von K . Dann existiert nach dem Hauptsatz der Galoistheorie eine Untergruppe H von G mit L = Fix(H ). Sei G = fg 2
G j g = g der Stabilisator von in G. Dann ist K = Q () = Fix(G) und
fur H gilt die Beziehung G < H < G. Sei die Bahn (Orbit) von unter H ,
d.h. = fh j h 2 H g. Wir zeigen nun mit Hilfe der Denition 4.1, da ein
Block ist. Sei hierzu ein g 2 G beliebig gewahlt. Wir unterscheiden im folgenden
2 Falle:
(1)
(2)
Sei g 2 H . Wahle nun 2 beliebig. Dann existiert ein h 2 H , so da
h = gilt. Hieraus folgt g 2 wegen g = gh = h~ mit h~ 2 H .
Damit ist gezeigt, da g = gilt.
Sei g 2 G n H . Im folgenden zeigen wir, da g \ = ; gilt. Wir nehmen
hierzu an, da ein 2 existiere mit g 2 . Nun existiert ein h~ 2 H
mit h~ = . Setze g~ = gh~ 2 G n H . Wegen g~ 2 existiert ein h 2 H mit
hg~ = . Damit gilt dann hg~ 2 G und somit hg~ 2 H . Hieraus folgt aber,
da g~ 2 H ist, was zu einem Widerspruch fuhrt.
Damit haben wir sowohl die Blockeigenschaft von als auch H = Gfg gezeigt.
Wegen H = Gfg ist der eindeutig bestimmte Block zu L, der enthalt.
Sei nun umgekehrt ein Block, der enthalt. Deniere L := Fix(Gfg). Wegen
G < Gfg < G ist L nach Galoistheorie ein Teilkorper von K . Damit haben wir
die gewunschte Bijektion gezeigt.
Die Gradaussage folgt wegen j j = j Gfg : G j = (K : L) = d. Somit ist nd = m
der Grad von L.
Im obigen Satz haben wir den Zusammenhang zwischen den Blocken und den
Teilkorpern gezeigt. Mit Hilfe dieser Aussage konnen wir zwei Korollare zeigen,
die uns eine gewisse Einsicht in die Teilkorperproblematik liefern.
Korollar 4.12. Sei f 2 Z[t] vom Grad n irreduzibel, normiert und sei Gal(f )
= Sn oder An (alternierende Gruppe). Dann ist K = Q () mit Nullstelle von
f primitiv, d.h. K besitzt keine echten Teilkorper.
Beweis: Sei G =Gal(f ) = Sn. Dann enthalt G eine Permutation vom Zykeltyp
[1; n 1]. O.E. sei im Zykel der Lange 1 enthalten. Es sei nun ein beliebiger


4. DER ZUSAMMENHANG ZWISCHEN BLOCKEN
UND TEILKORPERN
35
Block, der enthalt. Wegen 2 \ folgt k(; ) = 1. Damit kann nur
die Groe 1 oder n haben, d.h. ist ein trivialer Block. Somit besitzt K nach
obigen Satz keine echten Teilkorper.
Sei nun G =Gal(f ) = An. Falls n gerade ist, wahlen wir ein wie im ersten
Teil des Beweises. Sei also n ungerade. Wir wahlen nun ein 2 G, welches
vom Zykeltyp [1; 1; n 2] ist. Analog zum ersten Teil des Beweises konnen nur
Blocke der Groe 1; 2 oder n existieren. Da aber n ungerade ist, ist 2 keine gultige
Blockgroe. Damit hat G nur die trivialen Blocke und K ist wiederum primitiv.
2 Z[t] normiert und irreduzibel vom Grad n und eine
Nullstelle von f . Ferner gelte fur ein p 2 P zusatzlich, da f (t) mod pZ[t] irreduzibel ist. Dann besitzt K = Q () hochstens einen Teilkorper vom Grad m
(m j n).
Korollar 4.13. Sei f
Beweis: Da f (t) mod pZ[t] irreduzibel ist, enthalt G =Gal(f ) eine Permutation
vom Zykeltyp [n]. Sei nun ein m gegeben, so da n von m geteilt wird. Zu
einem Teilkorper vom Grad m mu nach obigen Satz ein Block der Groe mn
existieren, der enthalt. Da nur aus einem Zykel besteht, kann es hochstens
einen solchen Block geben. Damit ist die Behauptung gezeigt.
Im nachstem Schritt werden wir zeigen, wie man aus einem Block, der enthalt,
den zugehorigen Teilkorper berechnen kann.
Satz 4.14. Sei f 2 Z[t] normiert und irreduzibel vom Grad n, und sei eine
Nullstelle von f . Sei K = Q (), G = Gal(f ) und ein Block der Groe d, der
enthalt. Seien 2 ; : : :Q; m die zu = 1 konjugierten Blocke (m = nd ). Fur
i = 1; : : : ; m setze i = 2i . Weiterhin seien die i (i = 1; : : : ; m) paarweise
verschieden. Dann ist 1 primitives Element von L = Fix(Gfg ) und es gilt:
g(t) = Qmi=1(t i) ist ein Minimalpolynom von L.
Beweis: Da Gfg Elemente aus wieder auf Elemente aus uberfuhrt, bleibt
1 unter Gfg x. Damit ist gezeigt, da 1 2 L ist.
Aufgrund der Konstruktion ist L ein Teilkorper vom Grad m. Wegen der Blockeigenschaft der i (i = 1; : : : ; m) wird 1 durch jedes g 2 G auf ein j (j = 1; : : : ; m)
uberfuhrt. Da die j (j = 1; : : : ; m) paarweise verschieden sind, besitzt 1 somit
m verschiedene Konjugierte und hat somit Grad m. Deswegen ist 1 primitives
Element von L. Aufgrund der Konstruktion erkennen wir, da die i (1 i m)
die Konjugierten von 1 sind. Hieraus folgt die Darstellung von g.

4. IMPRIMITIVITA TSGEBIETE UND BLOCKE
36
In der Praxis kann es passieren, da die i (i = 1; : : : ; m) nicht paarweise verschieden sind. Damit der obige Satz angewendet werden kann, mu ein anderes
Minimalpolynom des Korpers K gefunden werden, welches die Voraussetzungen
des Satzes erfullt. Hierzu soll der folgende Satz einen Ansatz liefern.
Satz 4.15. Falls die i (i = 1; : : : ; m) nicht paarweise verschieden sind, substituiere t := t k in f . Es gibt hochstens n2d solcher Substitutionen, die wiederum
nicht paarweise verschiedene i (i = 1; : : : ; m) liefern.
2
Beweis: Fur i = 1; : : : ; m deniere i(x) := Q2i (x + ). Diese Polynome
sind alle verschieden, da sie verschiedene Nullstellen haben. Alle Polynome haben Grad d, so da hochstens
md Funktionswerte zweier Polynome ubereinstimmen
o
nnen.
Da
es
maximal
k
2 Paare von Polynomen gibt, existieren hochstens
m 1
n
ur die i(k) = j (k) mit i 6= j gilt. Wie man leicht
2 d < 2 mn = 2d Werte k , f
sieht, hat jedes andere k 2 Z die gewunschte Eigenschaft.
Bemerkung 4.16. Sei f~ das durch die Substitution t := t k aus f hervorgegangene Polynom. Dann gilt: disc(f ) = disc(f~).
Bemerkung 4.17. Die im vorangehenden Satz durchgefuhrte Substitution hat den
Nachteil, da die Koezenten des neuen Polynoms sehr gro werden konnen.
Bemerkung 4.18. Unter der Annahme, da die i paarweise verschieden sind,
lat sich ein primitives Element eines Teilkorpers vom Grad m durch das Produkt
von mn geeigneten Nullstellen des Minimalpolynoms von darstellen. Falls die
i (i = 1; : : : ; m) nicht paarweise verschieden sind, kann auf diese Art nur ein
Teilkorper des gesuchten Korpers dargestellt werden.
2
5. Berechnung von moglichen Blocken
Im bisherigen Teil dieses Kapitels haben wir Eigenschaften von Blocken einer transitiven (Galois-) Gruppe G angegeben und hergeleitet. Weiterhin haben wir den
Zusammenhang zwischen den Blocken und den Teilkorpern einer algebraischen Erweiterung aufgezeigt. So stellt sich uns nun die Frage, wie wir die Blocke einer
Galoisgruppe G =Gal(f ) berechnen konnen, wenn wir nur das Minimalpolynom
f kennen. Wir hatten schon erwahnt, da es viel zu kompliziert ist, zuerst die
Galoisgruppe zu berechnen und hiernach zu versuchen, Teilkorper zu bestimmen.
Daher konnen wir die Denition fur Blocke nicht verizieren und damit die Blocke
nicht direkt ausrechnen. Deswegen mussen wir einen anderen Weg nden. Wir
haben im zweiten Abschnitt dieses Kapitels einige Eigenschaften von Blocke hergeleitet, die wir nun fur unser Verfahren ausnutzen wollen. Wir werden Teilmengen


5. BERECHNUNG VON MOGLICHEN
BLOCKEN
37
berechnen, die die hergeleiteten Eigenschaften besitzen. Hierzu betrachten wir die
folgende Denition.
Definition 4.19. Mogliche Blocke und Blocksysteme
Im folgenden seien A , k 2 N und = 1 : : : r 2 G, wobei ni die Lange des
Zykels i (1 i r) ist, mit den folgenden Eigenschaften gegeben:
(1) jAj = d 2 N .
(2) Enthalt ein Zykel i Elemente der Menge A, so wird ni von k geteilt und
i enthalt exakt nki Elemente der Menge A.
Eine solche Teilmenge heit moglicher Block der Groe d mit k-Wert k. Seien weiterhin A1 ; : : : ; Am mogliche Blocke der Groe d mit k-Werten k1 ; : : : ; km. Dann
heit A1 ; : : : ; Am ein mogliches Blocksystem, falls
(1)
(2)
(3)
S A = .
i
1im
Ai \ Aj = ; fur i 6= j .
Fur jeden moglichen Block Ai ist Ai j fur 1 j < k auch ein moglicher
Block, der in der Menge fA1 ; : : : ; Am g enthalten ist.
gilt.
Bemerkung 4.20. Oensichtlich ist jeder Block ein moglicher Block und jedes
Blocksystem ein mogliches Blocksystem. Umgekehrt ist nicht jeder mogliche Block
ein Block und nicht jedes mogliche Blocksystem ein Blocksystem.
Bemerkung 4.21. Die Bezeichnungen moglicher Block bzw. mogliches Blocksystem sind abhangig von der Wahl der Permutation 2 G.
Da die Anzahl der moglichen Blocke stark von der gewahlten Permutation abhangt, sind wir daran interessiert, ein zu nden, fur das es moglichst wenig mogliche Blocke gibt.
Wir werden also im Algorithmus alle moglichen Blocke A von berechnen. In den
nachsten Kapiteln wird dann bei der Teilkorperberechnung bzw. bei der Einbettung erlautert werden, wie wir "falsche\ Blocke, d.h. mogliche Blocke, die keine
Blocke sind, erkennen konnen. Dieser Proze ist aber ofters sehr aufwendig, so
da wir daran interessiert sind, moglichst wenig "falsche\ Blocke zu berechnen.
Wir werden den folgenden Blockalgorithmus in zwei Varianten angeben. Im ersten
Fall sind wir nur an moglichen Blocken interessiert, die das primitive Element
38

4. IMPRIMITIVITA TSGEBIETE UND BLOCKE
von K enthalten. Da die Q (i ) (i = 1; : : : ; n) alle isomorph zueinander sind,
konnen wir o.E. davon ausgehen, da = 1 im ersten Zykel enthalten ist. In
der zweiten Variante sind wir an allen moglichen Blocksystemen interessiert. Hier
konnen wir im Prinzip den gleichen Algorithmus verwenden, wir mussen nur nach
Finden eines moglichen Blocks in den verbliebenen Zykeln nach weiteren moglichen
Blocken suchen.
Algorithmus 4.22. Berechnung von moglichen Blocken eines Korpers K .
Input:
Output:
Erzeugendes Polynom f 2 Z[t] von K = Q () vom Grad n,
gesuchte Blockgroe d 2 N ,
p 2 P, fur welches die Berechnung durchgefuhrt werden soll.
Mogliche Blocke des Korpers K , die enthalten.
Faktorisiere f mod p.
Falls die Faktorisierung einen doppelten Faktor enthalt, breche mit der Meldung "Algorithmus nicht durchfuhrbar\ ab.
(3) Bestimme aus der Faktorisierung den Zykeltyp [n1 ; : : : ; nu] von .
(4) Setze den k-Wert k auf 1 (vgl. 4.4).
(5) Bestimme alle Teilmengen A von f2; : : : ; ug, so da die folgenden beiden
Bedingungen erfullt sind:
(i) Fur alle a 2P A gilt: nka 2 N .
(ii) dk n1 = fna j a 2 Ag.
Gib diese Teilmengen aus.
(6) Falls k = d ist, terminiere den Algorithmus.
(7) Setze k auf den nachstgroeren Teiler von d.
(8) Gehe nach (5).
Bemerkung 4.23. Der obige Algorithmus geht davon aus, da das primitive Element des Korpers im ersten Zykel liegt. Dies ist o.E. moglich, da die Korper
Q (i ) (i = 1; : : : ; n) alle isomorph sind. Die i sind hierbei die Nullstellen des
Minimalpolynoms f .
Satz 4.24. Der Algorithmus 4.22 berechnet alle moglichen Blocke zu , die enthalten.
(1)
(2)
Beweis: In den Schritten (1){(3) wird mit Hilfe des van der Waerden-Kriteriums
2.28 eine zyklische Untergruppe H der Galoisgruppe G bestimmt. Der Satz ist
nicht anwendbar, wenn p die Diskriminante von f teilt, also f mod p doppelte
Faktoren enthalt. In den Schritten (4){(8) werden die moglichen Blocke berechnet. Der Algorithmus terminiert, da es nur endlich viele Teilmengen A gibt, die
untersucht werden mussen.


5. BERECHNUNG VON MOGLICHEN
BLOCKEN
39
Bemerkung 4.25. Im obigen Algorithmus ist die Durchfuhrung von Schritt (5)
oengeblieben. Dies ist ein kombinatorischer Algorithmus, der auf geschickte
Weise alle Moglichkeiten durchprobiert. Ein Problem dieses Algorithmus ist, da
wir nicht wissen, aus wievielen Zykeln ein Block zusammengesetzt ist. In der Praxis hat es sich als vorteilhaft erwiesen, zuerst die groen Zykel auszuprobieren. So
stellt man sehr oft fest, da bereits eine zweielementige Teilmenge zu gro ist, so
da man mehrelementige Mengen, die diese enthalten, erst gar nicht betrachten
mu. Weiterhin erweist es sich in diesem Schritt als sehr nutzlich, wenn man diesen Schritt vorzeitig abbricht, wenn schon klar ist, da dieser Zykel unbrauchbar
ist. Dies ist z.B. dann der Fall, wenn man wei, da es hochstens l Blocke vom
gegebenen Grad geben kann, man aber bereits erheblich mehr ausgerechnet hat.
Wir mochten an dieser Stelle allerdings verzichten, eine genaue Implementierung
von Schritt (5) anzugeben.
Zum Abschlu dieses Abschnitts wollen wir noch einen zweiten Algorithmus angeben, der die moglichen Blocksysteme der Galoisgruppe G berechnet. Dadurch,
da wir alle Blocke eines Blocksystems berechnen, haben wir naturlich noch mehr
Moglichkeiten, falsche Blocke zu berechnen. Wenn zum Beispiel ein Block in mehreren Blocksystemen enthalten ist, so wissen wir, da nur ein Blocksystem gultig
sein kann. Sollten wir in einem spateren Teil des Algorithmus bestatigen konnen,
da ein mogliches Blocksystem ein Blocksystem war, so brauchen wir die anderen
moglichen Blocksysteme, die einen Block aus dem richtigen Blocksystem enthalten,
nicht mehr betrachten. Nun wollen wir aber zum Algorithmus kommen.
Algorithmus 4.26. Berechnung von moglichen Blocksystemen eines Korpers K .
Input:
Output:
(1)
(2)
(3)
(4)
Erzeugendes Polynom f 2 Z[t] des Korpers K = Q (1 ) vom Grad n,
gesuchte Blockgroe d 2 N ,
Permutation samt Zerlegung in elementfremde Zykel 1 ; : : : ; u.
Z = f1 ; : : : ; u g.
Mogliche Blocksysteme des Korpers K .
Setze den k-Wert k auf 1 (vgl. 4.4).
Setze l auf die Anzahl der Elemente in Z und bestimme die Zykellangen
n1 ; : : : ; nl der in Z enthaltenden Zykel.
Bestimme alle Teilmengen A von f2; : : : ; lg, so da die folgenden beiden
Bedingungen erfullt sind:
(i) Fur alle a 2P A gilt: nka 2 N .
(ii) dk n1 = a2A na.
Fur jede dieser Teilmengen A tue folgendes:
40
(5)
(6)
(7)

4. IMPRIMITIVITA TSGEBIETE UND BLOCKE
(i) Entferne alle benutzten Zykel aus Z, d.h. setze Z=Z nA.
(ii) Falls Z die leere Menge ist, gib das mogliche Blocksystem aus.
(iii) Ansonsten rufe den Algorithmus erneut mit den verbleibenden Zykeln
in Z auf.
Falls k = d ist, terminiere den Algorithmus.
Setze k auf den nachstgroeren Teiler von d.
Gehe nach (3).
Beweis: Die Korrektheit dieses Algorithmus folgt unmittelbar aus dem Algorithmus 4.22 und den hergeleiteten Eigenschaften.
Bemerkung 4.27. Wie wir am 4. Schritt sehen, arbeitet dieser Algorithmus rekursiv. Im Prinzip wird das Verteilen der Zykel auf die moglichen Blocke sukzessive angewendet, bis keine Zykel mehr da sind. Bei hoheren k-Werten brauchen
die konjugierten Blocke, die aus den selben Zykeln bestehen, nicht beachtet werden,
da sie eindeutig feststehen. Deswegen kann man an dieser Stelle auch alle benutzten Zykel aus der Liste Z streichen. Bei der Ausgabe des moglichen Blocksystem
wird davon ausgegangen, da dem Algorithmus die vorher berechneten moglichen
Blocke zur Verfugung stehen.
6. Beispiele
Zum Abschlu wollen wir die Ergebnisse dieses Kapitels an zwei Beispielen demonstrieren. Der kurzeren Schreibweise wegen listen wir ein Blocksystem in der
Form ff: : : g; : : : ; f: : : gg auf.
Zuerst betrachten wir die verschiedenen Zykeltypen eines Korpers vom Grad 4 und
bestimmen die Anzahl seiner moglichen Blocke der Groe 2.
Zykeltyp [4], d.h. = (1 ; 2; 3; 4).
Fur k = 1 und k = 4 konnen wir keinen Block der Groe 2 bilden. Fur
k = 2 bilden ff1; 3 g; f2; 4gg ein Blocksystem.
(ii) Zykeltyp [1,3], d.h. = (1 )(2; 3; 4).
Da der erste Faktor Grad 1 hat, mu der zugehorige k-Wert 1 sein. Damit
lat sich aber nur ein Block der Groe 1 oder 4 bilden. Es existiert also
kein Block der Groe 2.
(iii) Zykeltyp [2,2], d.h. = (1 ; 2)(3; 4).
Fur k=1 erhalten wir das Blocksystem ff1; 2gf3; 4gg. Fur k=2 konnen
wir zwei weitere mogliche Blocksysteme bilden, namlich ff1; 3g; f2; 4gg
und ff1; 4g; f2; 3gg.
(i)
6. BEISPIELE
41
(iv) Zykeltyp [1,1,2], d.h. = (1 )(2)(34 ).
Die Nullstellen 1 und 2 mussen zu einem Block mit k-Wert 1 gehoren.
Sie bilden also einen Block. Damit ergibt sich der zweite Block mit f3; 4 g
automatisch.
(v) Zykeltyp [1,1,1,1], d.h. = id.
Die Identitat liefert alle Moglichkeiten
4 die Nullstellen in Blocke der Groe
2 zu gruppieren. Es ergeben sich 2 = 3 Moglichkeiten.
Als nachstes werden wir unsere U berlegungen an einem Beispiel vom Grad 6 demonstrieren. Hierzu betrachten wir den Korper K , der vom irreduziblen Polynom
f (t) = t6 + 108 erzeugt wird. Wir faktorisieren dieses Polynom modulo mehrerer
Primzahlen und erhalten die folgenden Faktorisierungen:
f (t) t6 mod 2
f (t) t6 mod 3
f (t) (t2 + 2)(t2 + t + 2)(t2 + 4t + 2) mod 5
f (t) (t3 + 2)(t3 + 5) mod 7
...
f (t) (t + 3)(t + 13)(t + 15)(t + 16)(t + 18)(t + 28) mod 31
Die Faktorisierungen modulo 2,3 sind fur uns uninteressant, da doppelte Faktoren auftreten. Auf die nachsten drei Faktorisierungen konnen wir das van der
Waerden-Kriterium anwenden und erhalten so Zykeltypen von Elementen der Galoisgruppe von f . Fur p = 5 erhalten wir so ein Element vom Zykeltyp [2,2,2],
d.h. es existiert ein 2Gal(f ) mit = (1 2)(3 4)(56 ): Hierbei sollen die
i passend numeriert sein. Analog erhalten wir fur p = 7 ein Element vom Zykeltyp [3,3] und fur p = 31 ein Element vom Zykeltyp [1,1,1,1,1,1], welches der
Identitat entspricht. Die Faktorisierungen modulo der anderen Primzahlen haben
keine neuen Zykeltypen ergeben. Wir mussen uns nun uberlegen, wieviele Blocke
der Groe 2 und 3 existieren konnen.
Wir starten mit p = 5, dem Zykeltyp [2,2,2] und der Blockgroe 2. Wir setzen
k = 1, d.h. fur jeden Block mussen alle Nullstellen eines Faktors verwendet
werden. Wir setzen also 1 = f1; 2 g. Nun mussen wir die verbleibenden Blocke
bestimmen. Hierzu setzen wir wieder k = 1 und erhalten 2 = f3 ; 4g und damit
3 = f5; 6g. Damit haben wir ein erstes mogliches komplettes Blocksystem
bestimmt. Fur das nachste Blocksystem gilt immer noch 1 = f1 ; 2g (Wir
kommen eine Rekursionsstufe zuruck.) Fur k = 1 konnen wir keine weiteren
42

4. IMPRIMITIVITA TSGEBIETE UND BLOCKE
Blocke bestimmen. Daher setzen wir k = 2 und erhalten die beiden Moglichkeiten
2 = f3; 5g und 3 = f4 ; 6g bzw. 2 = f3; 6g und 3 = f4; 5g. Da
bei allen 3 Blocksystemen der Block 1 identisch ist, kann nur eins ein gultiges
Blocksystem sein. Nun kommen wir zum Block 1 zuruck und stellen fest, da
mit k = 1 keine weitere Blockbildung moglich ist. Wir setzen also k = 2 und
erhalten die folgenden Blocksysteme:
ff1; 3g; f2; 4g; f5; 6gg ff1; 4g; f3; 4g; f5; 6gg
ff1; 5g; f2; 6g; f3; 4gg ff1; 6g; f2; 5g; f3; 4gg
Wir mussen also sieben mogliche Blocksysteme untersuchen, von denen aber nur
drei gultig sein konnen.
Fur die Blockgroe 3 stellen wir leicht fest, da alle Blocke k-Wert 2 haben mussen.
Wir erhalten so 4 verschiedene mogliche Blocksysteme.
Wir wechseln nun die Primzahl und betrachten p = 7. O.E. gehen wir davon aus,
da die Nullstellen nun so angeordnet sind, da = (1; 2; 3)(4 ; 5; 6) gilt.
Wir starten mit der Blockgroe 2 und stellen fest, da Blockbildung nur mit k=3
moglich ist. Dies bedeutet, da wir jeweils eine Nullstelle des ersten Faktors mit
einer Nullstelle des zweiten Faktors kombinieren mussen. Die Anzahl der moglichen Blocksysteme bleibt hier klein, da nach Bildung eines ersten Blocks, die
ubrigen Blocke eindeutig mit Hilfe des Frobeniusautomorphismus bestimmt sind.
Dieses wird im Kapitel uber die Berechnung der Teilkorper noch erlautert werden.
Wir erhalten also die drei moglichen Blocksysteme: ff1; 4gf2; 5 gf3; 6gg
ff1; 5gf2; 6gf3; 4gg ff1; 6gf2; 4gf3; 5gg
Fur die Blockgroe 3 erhalten wir fur k = 1 nur einen Blocksystem, wobei die
Blocke aus den Nullstellen der beiden Faktoren bestehen.
6
Die Identitat auszuwerten lohnt
sich
f
u
r
uns
nicht,
da
sie
ur
3 Moglichkeiten f
Blocke der Groe 2 und 62 Moglichkeiten fur Blocke der Groe 3 liefert. Wir
stellen also fest, da p = 7 fur unsere Berechnungen am besten geeignet ist.
KAPITEL 5
Zur Konstruktion von Teilkorpern
1. Einleitung
Im vorherigen Kapitel haben wir Methoden vorgestellt, um aus einem erzeugenden
Polynom f eines Korpers K mogliche Blocke zu berechnen. Im gunstigsten Fall
haben wir dabei festgestellt, da es keine Blocke und damit auch keine Teilkorper
geben kann. Falls dieser gunstige Fall nicht eintritt, mussen wir hier nun versuchen,
aus den moglichen Blocken erzeugende Polynome von Teilkorpern zu berechnen.
Dabei stellt sich uns das Problem, da wir nicht wissen, ob die moglichen Blocke
auch tatsachlich Blocke der Galoisgruppe unseres Polynoms sind. Dies zu berucksichtigen wird in den beiden in diesem Kapitel vorgestellten Verfahren noch einige
Probleme bereiten.
Ausgangspunkt fur beide Verfahren ist, da wir vom Blockalgorithmus eine "moglichst gunstige\ Primzahl p geliefert bekommen. Moglichst gunstig heit hierbei
unter anderem, da sie moglichst wenig Moglichkeiten fur verschiedene Blocke
zulat. Aber es spielen auch noch andere Punkte eine wichtige Rolle, die in den
beiden Verfahren herausgearbeitet werden sollen.
Der erste Algorithmus, den wir im Rahmen dieser Arbeit vorstellen wollen, entspricht im groben dem Verfahren, welches in [Dix1] prasentiert wird. Hier wird dem
Algorithmus ein moglicher Block und eine Primzahl p zur Verfugung gestellt.
Der Algorithmus ist nur durchfuhrbar, wenn der zugehorige k-Wert 1 ist. Im ersten
Schritt wird dann die modulo p-Faktorisierung von f mittels des Hensel-Liftings
bis zu einer genugenden p-Potenz geliftet. Hiernach kann ein primitives Element
des gesuchten Teilkorpers approximiert werden. Mit Hilfe des LLL-Algorithmus
kann dann das Minimalpolynom dieses primitiven Elements ausgerechnet werden.
Falls einer dieser Schritte scheitert, bedeutet dies, da kein Block war.
43
44

5. ZUR KONSTRUKTION VON TEILKORPERN
Der zweite Algorithmus hat den Vorteil, da er auch mit Primzahlen arbeiten kann,
bei denen die zugehorigen k-Werte ungleich 1 sind. Dieses Verfahren benotigt
neben der Primzahl p allerdings ein komplettes Blocksystem. Hiernach ist das
Minimalpolynom des Teilkorpers lediglich durch das Faktorisieren von Polynomen
uber endlichen Korpern und durch das Hensel-Lifting berechenbar.
2. Zur Abschatzung der Koezienten des gesuchten Minimalpolynoms
In diesem Abschnitt werden wir Schranken fur das zu berechnende erzeugende
Polynom des Teilkorpers L angeben. Dabei nutzen wir aus, da das erzeugende
Polynom mit Hilfe von 4.14 konstruiert wird. Wir mussen also die folgende Situation betrachten. Gegeben ist ein normiertes und irreduzibles Polynom f 2 Z[t]
mit Nullstellen 1; : : : ; n. Wir denieren einen algebraischen Zahlkorper durch
K = Q (1 ). Weiterhin nehmen wir an, da ein Teilkorper L vom Grad m existiert. Nach 4.11 existiert ein Blocksystem 1 ; : : : ; m , welches K=L eindeutig
zugeordnet ist. O.E. nehmen wir an, da die i so angeordnet sind, da fur
(j 1)d + 1 i jd gilt: i 2 j . Hierbei ist d die zugehorige Blockgroe; es gilt
also md = n. Nun wissen wir nach 4.14, da unser gesuchtes Minimalpolynom g
von L die Form
g ( t) =
m
Y
(t
j =1
Y
2j
) =
m
Y
(t
j =1
Yd
i=1
(j
1)d+i )
hat. Weiterhin wissen wir, da g 2 Z[t] ist.
Bevor wir mit den Abschatzungen beginnen, werden wir erstmal eine Polynomnorm denieren.
P
P
Definition 5.1. Sei f 2 Z[t] mit f (t) = ni=0 ci ti . Dann ist kf k2 := ( ni=0 c2i ) .
1
2
Das folgende Lemma wird uns zu einer Abschatzung unseres Problems fuhren.
P
Satz 5.2. Sei f 2 Z[t] normiert von der Form f (t) = ni=1 ai ti . Weiterhin seien
die Nullstellen 1 ; : : : ; n so angeordnet, da fur 1 i k gilt: jij 1. Fur
i > k soll dann jij < 1 gelten. Dann gilt fur die Koezienten von f folgende
Abschatzung:
!
!k
n
1
n
1 Y
jaj j j 1 jij + j :
i=1
Beweis: Wie allgemein bekannt ist, entsprechen die elementarsymmetrischen
Funktionen nj bis auf das Vorzeichen den Koezienten aj . Wir denieren fur

3. KONSTRUKTION VON TEILKORPERN
MIT HILFE DES LLL-ALGORITHMUS 45
1 i n : ~i := maxfjij; 1g. Die ~ni sind dann die elementarsymmetrischen
Funktionen bezogen auf die ~i. Deswegen gilt:
!
!Y
n
n
1
n
1
jaj j = jnj j j~nj j j 1 ~i + j :
i=1
Die letzte Ungleichung folgt nach Lemma 3.5.2 aus [Coh]. Die gesuchte Behauptung folgt, da fur i > k stets ~i = 1 gilt.
Mit Hilfe dieses Satzes konnen wir nun recht einfach Abschatzungen fur die Groe
der Koezienten unseres erzeugenden Polynoms g angeben. Das einzige Problem,
was wir losen mussen, ist die Bestimmung des Produktes der Nullstellen von g,
deren Betrag groer gleich 1 ist. Hierzu mussen wir zwei Falle unterscheiden.
Der einfache Fall ist, da bereits alle Nullstellen von f betraglich groer gleich
1 waren. Dann trit dies logischerweise auch fur die Nullstellen von g zu. Wir
konnen dann fur M einfach den Betrag des absoluten Glieds von f wahlen. Falls
einige Nullstellen von f betraglich kleiner als 1 sind, so konnen wir fur M den
Wert wahlen, den wir auch fur das Polynom f gewahlt hatten. Dieser Wert mu
zwar nicht optimal sein, reicht aber fur unsere Zwecke aus. Wenn man etwas
geschickter vorgehen will, so kann man sich uberlegen, ob Nullstellen von f , die
betraglich kleiner als 1 sind, in einem Block mit Nullstellen liegen, die betraglich
groer als 1 sind. Falls man solche Zusammenhange feststellen kann, kann man die
Abschatzung fur M verbessern. Diese U berlegungen fuhren zu folgendem Satz.
Satz 5.3. Sei f ein erzeugendes Polynom von K . Weiterhin
ein TeilPm b tj existiere
mittels
4.14
konkorper L von K , dessen erzeugendes Polynom
g
(
t
)
=
j =0 j
Q
k
struiert werden kann. Zusatzlich sei M = i=1 jij, wobei 1 ; : : : ; k gerade die
Nullstellen von f sind, deren Betrag groer gleich 1 sind. Dann gilt fur die Koefzienten von g die folgende Abschatzung:
!
!
m
1
m
1
jbj j j 1 M + j :
Durch diesen Satz konnen wir nun auch sehr leicht eine Abschatzung fur die k k2
des Minimalpolynoms unseres Teilkorpers bestimmen.
3. Konstruktion von Teilkorpern mit Hilfe des LLL-Algorithmus
Gegeben sei ein erzeugendes Polynom f des Zahlkorpers K . G sei die Galoisgruppe von f . Als Ausgangspunkt fur diesen Abschnitt sei ein moglicher Block
von G der Groe d und eine Primzahl p mit der zugehorigen Permutation 
5. ZUR KONSTRUKTION VON TEILKORPERN
46
gegeben, so da der zugehorige k-Wert 1 ist. Wie im vorigen Kapitel zerlegen wir
in elementfremde Zykel 1 : : : u. Dieser Zerlegung entspricht die Polynomfaktorisierung von f modulo pZ[t], d.h. der Zykel i operiert auf den Nullstellen von
fi (i = 1; : : : ; u). Da der k-Wert von bzgl. 1 ist, besteht nur aus kompletten
Zykeln von . Diese seien mit n ; : : : ; ns bezeichnet. Nach Satz 4.14 mussen
wir das Produkt der Wurzeln bilden, die in enthalten sind. Dieses Produkt
der Wurzeln entspricht bis auf das Vorzeichen gerade dem Produkt der absoluten
Glieder der zu n ; : : : ; ns gehorigen Polynome. Wenn wir dieses Produkt bilden,
erhalten wir eine modulo p-Approximation des gesuchten primitiven Elements.
Wenn wir vorher die Kongruenzfaktorisierung mittels des Hensel-Liftings zu einer modulo pk Z[t]-Faktorisierung liften (k 2 N ), so erhalten wir fur das primitive
Element sogar eine modulo pk -Approximation. Dabei mu das k genugend gro
gewahlt werden, damit die folgenden Schritte durchgefuhrt werden konnen. Diese
U berlegungen liefern den folgenden Algorithmus.
1
1
Algorithmus 5.4. Berechnung des Minimalpolynoms eines Teilkorpers L.
Input:
Output:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
Minimalpolynom f 2 Z[t] des Korpers K vom Grad n,
moglicher Block und Blockgroe d,
p 2 P, Faktorisierung von f modulo pZ[t].
Mogliches Minimalpolynom g eines Teilkorpers L.
Prufe, ob der zu gehorige k-Wert 1 ist. Falls nicht, breche mit der Fehlermeldung "Algorithmus nicht durchfuhrbar\ ab.
Berechne die Zykel n ; : : : ; ns , deren Wurzeln in enthalten sind.
Bestimme ein k, bis zu dem das Hensel-Lifting durchgefuhrt werden soll.
Lifte die Faktorisierung von f mittels des Hensel-Liftings:
f (t) f~1(t) : : : f~t(t) mod pk Z[t].
Berechne das Produkt der absoluten Glieder der zu n ; : : : ; ns gehorigen
Polynome f~i (modulo pk ).
Falls d ungerade ist, setze auf .
Bestimme mit Hilfe des LLL-Algorithmus ein mogliches Minimalpolynom g
des Teilkorpers L. Falls der Algorithmus scheitert, war kein Block gewesen.
1
1
Die ersten beiden Schritte des obigen Algorithmus sind selbsterklarend. Im 3.
Schritt mu ein k bestimmt werden, bis zu dem das Hensel-Lifting durchgefuhrt
werden soll. Dieses k hangt von dem gegebenen Polynom f ab. Hierbei mu
abgeschatzt werden, wie gro die Koezienten des gesuchten Minimalpolynoms

3. KONSTRUKTION VON TEILKORPERN
MIT HILFE DES LLL-ALGORITHMUS 47
von L werden konnen. Weiterhin mu das k so gro gewahlt werden, da das
gesuchte Minimalpolynom vom LLL-Algorithmus gefunden werden kann. Diese
Punkte werden in den nachsten Abschnitten beschrieben.
Die Schritte 4 und 5 des Algorithmus sind wiederum selbsterklarend. Im 6. Schritt
mu noch auf das Vorzeichen des approximierten Elements geachtet werden. Der
7. Schritt ist der Hauptteil des obigen Verfahrens. Hier mu mit Hilfe des LLLAlgorithmus aus dem approximierten primtiven Element das zugehorige Minimalpolynom berechnet werden. Dies wird in einem der folgenden Abschnitte erlautert
werden.
3.1. Bestimmung des Minimalpolynoms eines approximierten
primitiven Elements mit Hilfe des LLL-Algorithmus
Als Ausgangspunkt fur diesen Abschnitt erhalten wir ein approximiertes primitives
Element , den Grad m dieses Elements und ein M = pk bzgl. dem approximiert
ist. Gesucht wird also ein Minimalpolynom vom Grad m, welches modulo pk als Nullstelle hat. Damit die Eindeutigkeit dieses Polynoms gewahrleistet ist, mu
weiterhin eine Schranke B fur die Koezienten vorliegen.
Ein analoges Problem wird in [LLL] gelost. Im 2. Teil dieser Arbeit soll aus
einer modulo pk -Approximation ein Faktor eines gegebenen Polynoms bestimmt
werden. Wir mochten aus einer entsprechenden Approximation ein Minimalpolynom berechnen. Die Eigenschaft, da in [LLL] ein Faktor ausgerechnet werden
soll, wird nur in den Abschatzungen fur die Koezienten des gesuchten Polynoms
verwendet. Diesen Teil mussen wir also getrennt untersuchen. Das eigentliche
Verfahren verlauft allerdings vollig analog. Da wir nur mit einer Nullstelle , d.h.
mit einem linearen Polynom h(t) = t approximieren, werden einige Formeln
sogar einfacher.
In diesem Abschnitt
schreiben wir Z=pkZ fur den Ring der ganzen Zahlen
modulo
P
n
k
p . Fur f (t) = i=0 ai ti 2 Z[t] meinen wir mit f mod pk das Polynom Pni=0 (ai mod
pk )ti 2 Z=pkZ[t]. Zusatzlich sollen im weiteren die folgenden Voraussetzungen
gelten:
(1) f; g 2 Z[t] sind Polynome, wobei f von g geteilt wird.
(2) h(t) = t mit 2 Z und h mod pk teilt f mod pk in Z=pkZ[t].
(3) h2 mod p teilt nicht f mod p in F p [t].
2 Z[t], fur den
h mod p teilt h0 mod p gilt. Weiterhin ist dieser Faktor bis auf das Vorzeichen
Satz 5.5. Das Polynom f besitze einen irreduziblen Faktor h0
48

5. ZUR KONSTRUKTION VON TEILKORPERN
eindeutig bestimmt. Wenn nun g teilt f in Z[t] gilt, sind die drei folgenden Aussagen aquivalent:
(1)
(2)
(3)
h mod p teilt g mod p in F p [t].
h mod pk teilt g mod pk in Z=pkZ[t].
h0 teilt g in Z[t].
Weiterhin gilt dann: h mod pk teilt ho mod pk Z[t] in Z=pkZ[t].
Der Beweis dieses Satzes kann in [LLL] (Proposition (2.5)) entnommen werden.
Damit wir mit den Bezeichnungen von [LLL] konform bleiben, soll f in diesem
Abschnitt das gesuchte erzeugende Polynom eines Teilkorpers vom Grad m sein.
Wenn dieses existiert, wissen wir aus unseren Voruberlegungen, da f mod pk von
h mod pk in Z=pkZ[t] geteilt wird. Wir betrachten also im folgenden ein Gitter ,
welches alle Polynome in Z[t] enthalt, die modulo pk durch h mod pk teilbar sind.
Dies ist eine Teilmenge des (m + 1)-dimensionalen reellen Vektorraums R P
+R t+
: : : + R tm . Dieser Vektorraum wird auf den R m+1 abgebildet, wenn wir mi=0 aiti
auf (a0 ; a1; : : : ; am) abbilden. Da h normiert ist, ist ein Gitter vom Grad m + 1.
Die Basis von ist gegeben durch fpk g[fh(t)tj : 0 j < mg. Aus der Denition
der Gitterdiskriminante folgt direkt, da d() = pk ist. Im folgenden schreiben
wir fur k k2 abkurzend j j.
Satz 5.6. Seien p; f; m; h; h0 und g wie oben deniert. Nun gelte fur ein b 2 :
pk > jf jmjbjm. Dann ist b in Z[t] durch f teilbar und damit gilt ggT(f; b) = f 6= 1.
Beweis: Der Beweis ist ahnlich wie der Beweis von (2.7) in [LLL] Fur die Bezeichnungen setze hierzu h0 = f; l = 1; n = m; L = .
Sei b 6= 0 und setze g = ggT(f; b). Nach 5.5 ist h mod p teilt g mod p in Z=pZ[t]
zu zeigen. Nehmen wir an, da dies nicht gilt. Dann existieren 3; 3; 3 2 Z[t],
so da
3 h + 3g = 1 p3
gilt. Aus dieser Gleichung werden wir einen Widerspruch folgern. Setze e = deg(g)
und m0 = deg(b). Es gilt also 0 e m0 m. Deniere
M = ff + b : ; 2 Z[t]; deg() < m0 e; deg() < m eg
Z + Zt + : : : + Ztm+m0 e 1:
Sei M 0 die Projektion von M auf Zte + Zte+1 + : : : + Ztm+m0 e 1. Wenn nun ein
f + b 2 M auf 0 in M 0 projeziert wird, dann gilt: deg(f + b) < e. Da g aber
f + g teilt, folgt f + g = 0 (in M ). Hiermit gilt f = b, woraus fg = gb

3. KONSTRUKTION VON TEILKORPERN
MIT HILFE DES LLL-ALGORITHMUS 49
folgt. Wegen ggT( fg ; gb ) = 1, folgt fg teilt . Da aber deg() < m e = deg( fg )
gilt, folgt = 0 und damit auch = 0. Damit sind die Projektionen von
ftif : 0 i < m0 eg [ ftj b : 0 j < m eg
auf M 0 linear unabhangig. Da diese Projektionen M 0 aufspannen, ist M 0 ein
Gitter vom Rang m + m0 2e. Wegen Hadamards Ungleichung (2-1) und der
Voraussetzung erhalten wir:
d(M 0 ) jf jm0 ejbjm e jf jmjbjm < pk :
Wir brauchen im weiteren die Aussage des folgenden Lemmata.
Lemma 5.7. Gelte 3 h + 3g = 1 p3 . Dann gilt: f 2 M : deg( ) eg pk Z[t].
Wahle nun eine Basis be ; be+1; : : : ; bm+m0 e 1 von M 0 mit der Eigenschaft deg(bj ) =
j (Chapter I, Theorem I.A in [Cas1]). Dann ist der Leitkoezent von be wegen
obigen Lemmas durch pk teilbar. Man beachte hierbei, da e m + m0 e 1
wegen g teilt b und hQmod p teilt fg mod p gilt.
Nun gilt: d(M 0 ) = ejm+m0 e 1 j l(bj ) j, wobei mit l(bj ) der Leitkoezient
von bj bezeichnet werde. Hieraus folgt nun, da d(M 0 ) pk gilt, was zu einem
Widerspruch fuhrt.
Es bleibt noch das Lemma zu zeigen.
Beweis: Sei 2 M mit deg( ) e. Dann gilt oensichtlich g teilt . Aus der
Voraussetzung folgt nun:
3h + 3 g = 1 p3
Diese Gleichung multiplizieren wir mit g und erhalten:
3 hg + 3 = g (1 p3 )
Durch Erweitern mit 1 + p3 + p2 32 + : : : + pk 13k 1 und (g j ) erhalten wir:
4h + 4 = g (1 pk 3k ) mit 4 ; 4 2 Z[t]
Damit gilt die folgende Kongruenz:
50

5. ZUR KONSTRUKTION VON TEILKORPERN
4h + 4 g mod pk Z[t]
Wegen 2 M und b; f 2 folgt nun:
h mod pk Z[t] j mod pk Z[t] und damit:
5 h g mod pk Z[t] und hieraus
h j g mod pk Z[t]
Da aber deg(h) = 1 ist und der Grad von g e e = 0 ist, folgt g 0 mod pk Z[t],
also 0 mod pk Z[t].
Mit dem folgenden Satz treen wir eine Aussage daruber, wann das erste Basiselement einer LLL-reduzierten Basis das gesuchte erzeugende Polynom eines
Teilkorpers ist. Der analoge Satz zur Bestimmung von Faktoren eines ganzzahligen Polynoms kann wieder [LLL] entnommen werden. Wie im vorangegangenen
Satz soll f wieder das gesuchte erzeugende Polynom eines Teilkorpers sein.
Satz 5.8. Seien ; p; f; k und m wie oben deniert. Weiterhin haben wir eine
LLL-reduzierte Basis b1 ; : : : ; bm von ausgerechnet. Zusatzlich wurden p und k
so bestimmt, da pk > 2 m jf j2m gilt. Dann sind die beiden folgenden Aussagen
aquivalent:
2
2
(1)
(2)
deg(f ) m
jb1 j < ( jfpjkm ) m
1
Beweis: Es sei nun (2) erfullt. Dann folgt direkt, da pk > jf jmjb1jm gilt. Damit
sind die Voraussetzungen von 5.6 erfullt, wodurch (1) gezeigt ist.
Gelte nun (1). Dies bedeutet, da f 2 ist. Aus dem Minimumkriterium der
LLL-Abschatzung folgt nun:
jb1j 2 m jf j
2
Nun potenzieren wir beide Seiten mit m und multiplizieren diese mit jf jm.

3. KONSTRUKTION VON TEILKORPERN
MIT HILFE DES LLL-ALGORITHMUS 51
jb1jmjf jm 2 m jf j2m
2
2
Durch Einsetzen der Voraussetzung erhalten wir:
jb1jmjf jm < pk
Hieraus folgt dann (2), womit der Satz gezeigt ist.
In den vorangegangenen Satzen sind wir davon ausgegangen, da das Minimalpolynom des Teilkorpers nur durch ein lineares Polynom h approximiert wurde.
Sollten uns mehrere Blocke eines Blocksystems und damit mehrere approximierte
Nullstellen i des Minimalpolynoms bekannt sein, so konnen wir obige Satze dahingehend modizieren, da wir das Minimalpolynom mit allen bekannten Nullstellen
approximieren. Sei hierzu l die Anzahl der bekannten Blocke. Weiterhin gehen wir
davon aus, da die approximierten Nullstellen 1 ; : : : ; l bereits berechnet wurden.
Hiernach bilden wir das Polynom h mittels h(t) = Q1il (t i ). Analog zu oben
konnen wir nun ein Gitter vom Rang m + 1 aufbauen, welches alle Polynome
vom Grad kleiner als m enthalt, die modulo pk Z[t] von h geteilt werden. Eine
Basis von hat dann folgende Form:
fpk ti : 0 i < lg [ fhtj : 0 j m lg:
Mit diesen Bezeichnungen konnen die beiden folgenden Satze analog zu 5.6 und
5.8 bewiesen werden.
Satz 5.9. Seien p; f; m; l; h; h0 und g wie oben deniert. Nun gelte fur ein b 2 :
pkl > jf jmjbjm. Dann ist b in Z[t] durch f teilbar und damit gilt ggT(f; b) = f 6= 1.
Satz 5.10. Seien ; p; f; k; l und m wie oben deniert. Weiterhin haben wir eine
LLL-reduzierte Basis b1 ; : : : ; bm von ausgerechnet. Zusatzlich wurden p und k
so bestimmt, da pkl > 2 m jf j2m gilt. Dann sind die beiden folgenden Aussagen
aquivalent:
2
2
(1)
(2)
deg(f ) m
jb1 j < ( jfpkljm ) m
1
Wie wir an diesen beiden Aussagen sehen, ist es fur die Bestimmung von k (in
Abhangigkeit von p) von groer Bedeutung, wenn l > 1 ist. Einerseits mu dann
das Hensel-Lifting nicht so weit durchgefuhrt werden, andererseits kann der LLLAlgorithmus mit wesentlich kleineren Zahlen arbeiten, was in der Laufzeit Groenordnungen ausmacht. Aufgrund dieser Beobachtung ist man geneigt zu versuchen,
52

5. ZUR KONSTRUKTION VON TEILKORPERN
moglichst viele Blocke eines Blocksystems zu bestimmen. Dies scheitert jedoch
meistens daran, da nicht alle Blocke k-Wert 1 haben. Dieses Problem werden wir
dann im nachsten Abschnitt losen, wo wir auch Approximationen von primitiven
Elementen von Blocken bestimmen werden, deren k-Wert groer 1 ist.
4. Ein zweites Verfahren zur Berechnung von Teilkorpern
In diesem Abschnitt untersuchen wir ein zweites Verfahren zur Teilkorperberechnung. Grundlage dieses Verfahrens ist die Kenntnis eines kompletten Blocksystems
von Blocken der Groe d der Galoisgruppe von f . Wie in den vorangegangenen
Abschnitten ist f ein erzeugendes Polynom eines Zahlkorpers K vom Grad n. Zur
Bestimmung des Blocksystems wurde f modulo einer Primzahl p faktorisiert. Das
folgende Verfahren ist auch dann durchfuhrbar, wenn die zugehorigen k-Werte ungleich 1 sind. Falls ein k-Wert groer als 1 ist, so bedeutet dies, da Elemente
aus einem Zykel in k Blocken enthalten sind. Weiterhin mussen wir das Problem
losen, wie wir das Produkt der Nullstellen berechnen konnen, die in einem Block
liegen. Im vorherigen Verfahren haben wir dieses Produkt derart berechnet, da
wir das Produkt der absoluten Glieder der zugehorigen Faktoren gebildet haben.
Hierbei muten wir allerdings auf das Vorzeichen achten. Diese Moglichkeit haben wir bei einem k-Wert, der groer als 1 ist, nicht mehr. Hier mussen wir uns
eine andere Moglichkeit ausdenken. Die Hauptidee des folgenden Verfahrens besteht darin, das Polynom f nicht nur modulo p in F p [t], sondern sogar in F q [t] mit
q = pk zu faktorisieren. Die zugehorigen Polynome fi, die Nullstellen von einem
Block enthalten, zerfallen dann in k Faktoren gleicher Lange. Hiernach konnen
wir dann wieder das Produkt der Nullstellen als Produkt der absoluten Glieder
der zugehorigen Faktoren ausrechnen.
4.1. Berechnung von Teilkorpern im Spezialfall Cn G
Wir wollen unser Verfahren zuerst fur einen Spezialfall herleiten, damit die Ideen
klarer sind. So werden wir unser Verfahren fur den Spezialfall herleiten, da die
zyklische Gruppe Cn Untergruppe der Galoisgruppe von f ist. Dies bedeutet, da
eine Primzahl p existiert, fur die f mod p irreduzibel ist. Wir gehen im weiteren
davon aus, da eine solche Primzahl bereits gefunden wurde. Dieser Spezialfall ist
fur uns sehr vorteilhaft, da nach 4.13 nur ein Teilkorper vom vorgegebenen Grad
m existieren kann. Wir werden nun versuchen, einen Teilkorper vom Grad m zu
bestimmen bzw. zeigen, da ein solcher nicht existiert.
Sei nun d die zugehorige Blockgroe (md = n). Wir betrachten nun die Korpe-

4. EIN ZWEITES VERFAHREN ZUR BERECHNUNG VON TEILKORPERN
53
rerweiterung F q =F p , wobei q = pm gilt. Diese Korpererweiterung kann von einem
beliebigen irreduziblen Polynom erzeugt werden. Sei nun f auf kanonische Weise
in F q [t] eingebettet. Da f in F p [t] irreduzibel und m ein Teiler von n ist, faktorisiert
f in F q [t] in m Faktoren fi (1 i m) vom Grad d.
F pn
Fq
=
oE =pE
oE
Fp
=
Zp =p
Zp
Seien nun die a~i 2 F q die absoluten Glieder der Polynome fi . Wir denieren nun:
ai := ( 1)d a~i (1 i m). Die ai 's sind in gewisser Weise die Approximationen
fur die Nullstellen eines gesuchten Minimalpolynoms g des Teilkorpers vom Grad
m. Wir bilden daher das Polynom g1 mittels
m
Y
g1(t) = (t ai):
i=1
Im folgenden Satz werden wir zeigen, da g1 2 F p [t] gilt.
Satz 5.11. Sei g1 2 F q [t] wie oben deniert. Dann gilt sogar g1 2 F p [t].
Beweis: Deniere Mengen 1 ; : : : ; m derart, da i die Nullstellen von fi
(dargestellt in F pn ) enthalt. Wenn wir zeigen konnen, da die i (1 i m)
Blocke der Galoisgruppe G von F pn =F p sind, folgt die Behauptung mit 4.14. Sei
hierzu ein beliebiges g 2 G gegeben. Sei H1 die Galoisgruppe von F pn =F q und H2
die Galoisgruppe von F q =F p . Dann lat sich g auf eindeutige Weise als Produkt
g = h1 h2 mit h1 2 H1 und h2 2 H2 schreiben. O.E. reicht es, wenn wir zeigen, da
1 ein Block ist. Wir wollen dies mit der Denition 4.1 tun. Die Koezienten
54

5. ZUR KONSTRUKTION VON TEILKORPERN
des Polynoms f1 liegen alle in F q . Dies bedeutet, da sie von allen Elementen aus
H1 und damit auch von h1 invariant gelassen werden. Damit gilt h = . Da
die fi 2 F q [t] (1 i m) sind, wird f1 von h2 auf ein fj (1 j m) abgebildet.
Damit geht dann 1 auf j uber. Insgesamt gilt also: g \ 2 f;; g. Damit
ist die Behauptung gezeigt.
Das soeben berechnete Polynom g1 ist eine modulo p-Approximation des gesuchten
Minimalpolynoms g. Dies bedeutet, da
g1(t) g(t) mod pZ[t]
gilt. Diese Aussage ist ein Spezialfall von Satz 5.15, der im folgenden noch bewiesen wird. Wenn man wei, da der Betrag der Koezienten von g stets kleiner als
p
2 ist, ware man an dieser Stelle fertig. I.allg. gilt diese Beziehung nicht. Ziel ist es
also, im folgenden zu einer modulo pk -Approximation zu kommen. Dazu werden
wir die zugehorigen p-adischen Korper Q p und E = KP, wobei P das eindeutige
Primideal in K ist, welches uber p = pZ liegt. Hierbei ist P eindeutig bestimmt,
da f mod p irreduzibel ist. Weiterhin bezeichnen wir mit oE die Maximalordnung
von E . Da p unverzweigt in K ist, konnen wir eine Gleichungsordnung von E
angeben, die bereits Maximalordnung ist. Sei hierzu h 2 F p [t], welches die Korpererweiterung (E =P)=(Z=pZ) erzeugt. Wahle nun ein h 2 Zp[t] mit h h mod p.
Die von diesem Polynom h erzeugte Gleichungsordnung ist wegen 3.19 bereits die
Maximalordnung. Dies vereinfacht das Rechnen in dieser Struktur sehr, wie das
folgende Korollar zeigt. Hierzu sei eine Nullstelle von h.
P 1 x i (x 2 Z ). Dann gilt
Korollar 5.12. Sei k 2 N und x 2 oE , d.h. x = m
i
p
i=0 i
x 2 Pk genau dann, wenn xi 2 pk (0 i < m) gilt.
1
Beweis: Wegen P = poE folgt Pk = pk oE . Damit folgt die Behauptung.
Wir werden nun erlautern, wie wir zu einer modulo pk -Approximation unseres
gesuchten erzeugenden Polynoms kommen. Hierzu stellen wir zuerst einmal fest,
da die Galoisgruppen von F q =F p und E =Q p gleich sind (vgl. 3.18). Sei nun
f = f^1 : : : f^m
(5-1)
die Faktorisierung von f in irreduzible Faktoren f^i in oE [t]. Diese Faktoren haben
alle Grad d. Analog zu oben denieren wir bi := ( 1)db~i (1 i m), wobei die
b~i die absoluten Glieder der Polynome f^i sind. Setzen wir abschlieend
g~(t) :=
so gilt der folgende Satz.
m
Y
i=1
(t bi) 2 oE [t];

4. EIN ZWEITES VERFAHREN ZUR BERECHNUNG VON TEILKORPERN
55
Satz 5.13. Sei g~ 2 oE [t] wie oben deniert. Dann gilt sogar g~ 2 Zp[t].
Beweis: Der Beweis verlauft vollig analog zum Satz 5.11.
Anhand dieses Satzes sieht man, auf welche Weise man versuchen kann, ein erzeugendes Polynom des gesuchten Teilkorpers zu berechnen. Der Vorteil der padischen Korper liegt darin, da wir mit Hilfe des van der Waerden-Kriteriums
2.28 sogar die Nullstellen identizieren konnen, die in den einzelnen Zykeln liegen.
Dies konnten wir bei den algebraischen Zahlkorpern nicht.
Das weitere Ziel dieses Abschnitts wird es sein, den folgenden Satz zu beweisen.
Er wird schlielich eine direkte Folgerung von Satz 5.15 sein.
Satz 5.14. Seien f; g~; m; n; d wie oben deniert. Weiterhin nehmen wir an, da K
tatsachlich einen TeilkoQrper L vom Grad m besitzt. Sei 1 ; : : : ; m das
zugehorige
Blocksysten und i := i 2i i (1 i m). Zusatzlich gelte g(t) = Qmi=1 (t i ).
Dann sind die Polynome g und g~ identisch, wenn man Z auf kanonische Weise in
Zp einbettet.
Im folgenden mussen wir zeigen, wie wir das Polynom g~ hinreichend genau bedes zu berechnen konnen. Dazu mussen wir eine Schranke B der Koezienten
rechnenden Polynoms g kennen. Hierzu habe g die Form g(t) = Pmi=0 citi. Die
Schranke soll so gewahlt sein, da fur alle Koezienten gilt: jcij < B (0 i m).
Wenn eine solche Schranke bekannt ist, bestimmen wir zum gegebenen p ein minimales k 2 N derart, da pk > 2B gilt. Wir wollen nun ein Polynom gk 2 Z[t]
bestimmen, so da gk g mod pk Z[t] gilt. Wenn wir nun gk in einem geeigneten
Restsystem (symmetrisch zur 0) darstellen, gilt wegen der gefundenen Schranke
B : g = gk .
Um dieses Verfahren zu beschreiben, werden wir von der Faktorisierung
f (t) = f1(t) : : : fm(t) in F q [t]
ausgehen. Da P trage ist, ist oE =P = F q . Damit ist die Voraussetzung (1)
des Hensel-Lemmas 2.24 erfullt. Die ai0 (0 i 2), die in Voraussetzung (2)
benotigt werden, konnen im euklidischen Ring F q [t] einfach berechnet werden.
Die Konstruktivitat dieser Berechnungen wird im nachsten Abschnitt beschrieben.
Damit sind alle Voraussetzungen des Hensel-Liftings erfullt. Wir konnen also im
folgenden eine Kongruenzfaktorisierung der Form
f (t) f~1(t) : : : f~m(t) mod Pk [t]
56

5. ZUR KONSTRUKTION VON TEILKORPERN
berechnen. Analog zu oben werden die d~i (1 i m) als die absoluten Glieder
der Polynome f~i deniert. Wir setzen weiterhin di := ( 1)d d~i (1 i m). Da
die f~i modulo Pk [t] berechnet worden sind, gilt:
bi di mod Pk fur 1 i m.
Nun konnen wir das Polynom gk durch gk (t) = Qmi=1(t di) denieren. Nach
Konstruktion ist es klar, da
gk (t) g~(t) mod pk [t]
gilt. Nachdem wir nun beschrieben haben, wie wir das Polynom in der Praxis
konstruieren wollen, werden wir im folgenden Satz die Korrektheit des gesamten
Verfahrens beweisen. Der Beweis dieses Satz ist allerdings nicht konstruktiv, da
man in der Praxis weder im Zerfallungskorper von K noch in den zugehorigen
Vervollstandigungen rechnet.
Satz 5.15. Das Polynom gk ist modulo pk kongruent zum gesuchten Minimalpolynom g. Dabei soll gk auf kanonische Weise in Z[t] eingebettet werden.
Beweis: Zuerst uberlegen wir uns, wie wir das Polynom g in der Theorie berechnen konnen. Sei hierzu 1 ; : : : ; m das zugehorige Blocksystem der Korpererweiterung K=L (vgl. 4.11). Nehmen wir nun o.E. an, da die Nullstellen i von f so
angeordnet sind, da fur (j 1)d + 1 i dj gilt: i 2 j . Dann konnen wir
das Polynom g auf folgende Weise schreiben:
g ( t) =
m
Y
j =1
(t
Y
2j
) =
m
Y
j =1
(t
jd
Y
i=(j 1)d+1
i ):
Da wir alle Nullstellen von f bei der Berechnung von g benutzen, konnen wir i.allg.
die Berechnungen nicht in K = Q (1 ) durchfuhren, da K nicht notwendigerweise
normal ist. Deswegen fuhren wir die Berechnungen im Zerfallungskorper M =
Q (1 ; : : : ; n ) durch. Wir bezeichnen mit oK und oM die Maximalordnungen
von K und M . Da f mod p irreduzibel ist, existiert in K genau ein Primideal
pK , welches uber pZ liegt. Dieses ist klarerweise unverzweigt. Damit ist dann
nach 2.19 auch jedes Primideal in M unverzweigt, welches uber pZ liegt. Da M
zudem eine normale Erweiterung ist, haben alle Primideale in M , welche uber p
liegen, den selben Tragheitsgrad f . Nehmen wir nun an, da genau r Primideale
P1; : : : ; Pr uber p liegen. Wenn wir nun die zugehorigen p-adischen Zahlkorper
MPi (i = 1; : : : ; r) betrachten, so sind sie alle isomorph, da sie alle unverzweigt
sind und den selben Grad uber Q p haben. Deswegen reicht es aus, nur den padischen Zahlkorper MP = MP zu betrachten. Wie wir oben gezeigt haben,
konnen wir in diesem Korper ein Polynom g~ berechnen, welches sogar in Zp[t]
1
5. ZUM HENSEL-LIFTING U BER DEM RING oE
57
liegt. Wenn wir nun M auf kanonische Weise in MP einbetten, erhalten wir fur
jedes k 2 N , da g~ g mod pk ist. Damit ist die Behauptung des Satzes gezeigt.
5. Zum Hensel-Lifting uber dem Ring oE
Im vorherigen Abschnitt haben wir gezeigt, da die Voraussetzungen des HenselLemmas 2.24 erfullt sind und damit das Verfahren durchfuhrbar ist. Wenn wir
dieses Problem jedoch aus konstruktiver Sicht betrachten, so ist die Implementierung bis jetzt nicht vollstandig erklart worden. Auf diese Punkte soll in diesem
Abschnitt eingegangen werden.
Ein erstes Problem ist die Darstellung des p-adischen Korpers E bzw. die Darstellung seiner Maximalordnung oE . Sei hierzu pE das Primideal und m der Grad von
E . Wir sind wir nicht an einer vollstandigen Darstellung von oE , sondern lediglich an Elementen modulo pkE interessiert. Sei also h 2 Z [t] vom Grad m, welche
modulo pZ[t] irreduzibel ist. Wenn wir h auf kanonische Weise in Zp[t] einbetten,
ist die von h erzeugte Gleichungsordnung bereits oE . Wir erzeugen mit h einen
algebraischen Zahlkorper als Korpererweiterung von Q und betrachten seine Gleichungsordnung O. Da h mod p irreduzibel ist, ist das Ideal pZ trage in O. Wir
mochten nun Elemente von oE modulo pkE darstellen. Nach 5.12 konnen wir solche
Elemente in O darstellen, wobei wir die einzelnen Koezienten der Gleichungsordnung modulo pk bestimmen. Somit konnen wir alle Berechnungen, die wir
benotigen, in O machen. Dies ist eine Ordnung eines algebraischen Zahlkorpers.
Die Arithmetik in solchen Ordnungen wird zum Beispiel in [Poh] erlautert und
ist ein fester Bestandteil des Programmierpakets KANT (vgl. [Poh]). Ich mochte
daher an dieser Stelle nicht mehr weiter darauf eingehen. Wenn wir nun den
Algorithmus 2.25 betrachten, stellen wir fest, da die meisten Schritte nur aus
Additionen und Multiplikationen bestehen. Diese Operationen bereiten uns, wie
bereits gesagt, keine Probleme. Lediglich in den Schritten 6 und 10 taucht die Division mit Rest auf. Hier mussen wir noch zeigen, da diese Operation uberhaupt
durchfuhrbar ist. Die Division mit Rest wird jeweils modulo fji (i 2 N ; j = 1; 2)
durchgefuhrt. Diese Polynome haben die folgende Eigenschaft.
Bemerkung 5.16. Die Polynome fji (i 2 N ; j = 1; 2) aus 2.25 sind alle normiert.
Beweis: Am Anfang sind die Polynome fj0 (j = 1; 2) normierte Polynome. Die
neuen fji werden jeweils im 7. Schritt durch fj(i+1) = fji + dji berechnet. Dabei
hat das dji wegen Schritt 6 stets einen kleineren Grad als fji. Deswegen ist auch
fj(i+1) normiert, wenn fji normiert war.
58

5. ZUR KONSTRUKTION VON TEILKORPERN
Wenn wir uns nun den Algorithmus der Division mit Rest betrachten, so stellen
wir fest, da im ersten Schritt jeweils ein Monom durch den Leitkoezienten von
fji geteilt wird. Da dieser 1 ist, ist dieser Schritt trivial. Hiernach werden nur
Additionen bzw. Multiplikationen benotigt, die uns keine Probleme bereiten. Mittels dieser U berlegungen sind wir nun in der Lage, das Hensel-Lifting fur unseren
Spezialfall auf dem Rechner zu implementieren.
6. Der allgemeine Fall
In diesem Abschnitt werden wir das Verfahren beschreiben, wie wir Teilkorper berechnen konnen, wenn wir nicht das Gluck haben, eine Primzahl p zu nden, fur die
f mod p irreduzibel ist. Wie bisher sei K = Q (1 ) ein algebraischer Zahlkorper,
wobei 1; : : : ; n die Nullstellen des irreduziblen, normierten Polynoms f 2 Z[t]
sind. Wie bisher gehen wir davon aus, da ein Teilkorper L vom Grad m existiert.
Hierzu sei 1; : : : ; m das zugehorige Blocksystem.
Am Anfang des Verfahrens xieren wir eine Primzahl p, die uns fur die Durchfuhrung des Verfahrens gunstig erscheint. Welche Kriterien wir dafur ansetzen, wird
an anderer Stelle erortert werden. Wir faktorisieren dann f modulo p und erhalten
dann folgende Kongruenzfaktorisierung:
f f1 : : : fu mod pZ[t]:
Aus dieser Faktorisierung konnen wir dann mittels 2.28 den Zykeltyp [n1 ; : : : ; nu]
eines Elements der Galoisgruppe von f bestimmen. Wir gehen an dieser Stelle
davon aus, da bereits die k-Werte k1; : : : ; km der Blocke 1 ; : : : ; m bestimmt
worden sind. Wir wissen auerdem, aus welchen Zykeln die einzelnen Blocke
zusammengesetzt sind. Wir mussen im folgenden die Nullstellen identizieren, die
in den einzelnen Blocken liegen. Falls der k-Wert eines Blocks 1 ist, so bereitet dies
keine Probleme, da alle Nullstellen eines Zykels verwendet werden. Was machen
wir also, wenn k-Werte einzelner Blocke groer als 1 sind?
Das Hauptproblem besteht darin, die Nullstellen eines Zykels auf die k verschiedenen Blocke aufzuteilen. Aufgrund von 2.28 kennen wir die Aktion von einem
Element . Wir kennen hiermit die komplette zyklische Untergruppe, die von erzeugt wird. Die Nullstellen, auf denen operiert, konnen wir aber nur in der
zugehorigen p-adischen Vervollstandigung bzw. dem zugehorigen endlichen Restklassenkorper identizieren. An dieser Stelle wollen wir uns noch einmal erinnern,
was der k-Wert uberhaupt bedeutet. Wenn der zugehorige Block ist, so war k
die kleinste naturliche Zahl groer gleich 1, fur die k = gilt. Diese Gleichheit
6. DER ALLGEMEINE FALL
59
bedeutet, da sich unser gesuchter Block aus kompletten Zykeln von k zusammensetzt. Dabei brauchen nur Zykel beachtet werden, die aus einem Zykel von entstanden sind, dessen Lange durch k teilbar ist. Unser Problem ist es nun, die
Aktionen von k zu bestimmen. Dazu faktorisieren wir f uber der unverzweigten
Erweiterung F vom Grad k uber Q p . Die Faktoren dieser Faktorisierung liefern
uns analog zu 2.28 die gewunschte Aktion. Hiernach konnen wir die Nullstellen in
einer passenden Erweiterung von Zp bestimmen, die zum gesuchten Block gehoren.
Dieses Verfahren konnen wir dann sukzessive fur die anderen Blocke wiederholen.
Wichtig ist, da wir die Nullstellen, die zu den einzelnen Blocken gehoren, identiziert haben. Im nachsten Schritt bilden wir das kleinste gemeinsame Vielfache
der verschiedenen k-Werte und bezeichnen dieses mit l. Wir gehen dann in eine
unverzweigte Erweiterung vom Grad l uber Q p und faktorisieren f uber dem zugehorigen endlichen Restklassenkorper. Hiernach konnen wir das Hensel-Lifting
bis zur geforderten Genauigkeit anwenden. Insgesamt fuhren wir den folgenden
Algorithmus durch:
Algorithmus 5.17. Berechnung eines Teilkorpers im allgemeinen Fall
Input:
Output:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
Ein erzeugendes Polynom f eines Zahlkorpers K .
Eine Primzahl p und ein mogliches Blocksystem 1 ; : : : ; m.
Ein erzeugendes Polynom g eines moglichen Teilkorpers L.
Faktorisiere f modulo p und bestimme die k-Werte der Blocke 1 ; : : : ; m .
Fur i = 1; : : : ; m tue folgendes:
(a) Bestimme die Zykel und die zugehorigen Polynome, die Elemente im
Block i haben.
(b) Faktorisiere diese Polynome in einer Erweiterung vom Grad ki und
ermittle dann die Nullstellen, die zum Block i gehoren.
Bestimme l =kgV(k1 ; : : : ; km).
Faktorisiere f in einer Erweiterung vom Grad l.
Wende auf diese Faktorisierung das Hensel-Lifting bis zu einer genugenden
Genauigkeit an.
Fur i = 1; : : : ; m berechne das Produkt i der Nullstellen, die im Block i
liegen.
Q
Berechne das Polynom g(t) = mi=1 (t i ).
Bis auf die angesprochenen A nderungen funktioniert dieser Algorithmus ahnlich
zu dem vorher besprochenen. Er sollte daher selbsterklarend sein. Zum Abschlu
dieses Abschnitts verbleibt uns die Korrektheit dieses Verfahrens zu zeigen. Diese
folgt aus den beiden folgenden Satzen.
60

5. ZUR KONSTRUKTION VON TEILKORPERN
Hierzu sei l das kleinste gemeinsame Vielfache der im Algorithmus berechneten
k-Werte. E sei die unverzweigte Erweiterung vom Grad l uber Q p . Weiterhin ist
i fur i = 1; : : : ; m das Produkt der Nullstellen, die in i liegen. Dabei konnen die
Nullstellen naturlich in einer passenden Erweiterung von E liegen. Wir denieren
dann das Polynom
g~ =
m
Y
(t i ):
i=1
Satz 5.18. Sei g~ 2 oE [t] wie oben deniert. Dann gilt sogar g~ 2 Zp[t].
Beweis: Der Beweis verlauft ahnlich zum Beweis des Satzes 5.11. Dort wird die
Behauptung gezeigt, wenn f mod p irreduzibel ist. Als ersten Schritt faktorisieren
wir f mod p und erhalten:
f f1 : : : fu mod p:
Jedem dieser Faktoren fj ist ein k-Wert zugeordnet. Hiermit ist der k-Wert eines
Blockes gemeint, der Nullstellen von fj enthalt. Falls dieser k-Wert 1 ist, so
ist bereits i 2 Zp. Interessant ist der Fall, da der zugehorige k-Wert > 1 ist.
Nach 4.7 existieren dann k konjugierte Blocke, die Nullstellen der selben Polynome
enthalten wie . O.E. bezeichnen wir diese Blocke mit 1; : : : ; k .
Wir betrachten nun das folgende Polynom:
h(t) =
Yk
(t i) 2 E~ [t]:
i=1
Hierbei ist E~ die eindeutige unverzweigte Erweiterung von Q p vom Grad k. Wir
wollen nun zeigen, da bereits h 2 Zp[t] gilt. Damit ware dann auch g~ 2 Zp[t]
gezeigt. Seien nun o.E. f1; : : : ; fr die Polynome, die Nullstellen von 1; : : : ; k
besitzen. Diese Polynome faktorisieren wir dann in E~ [t] und erhalten:
fj =
Yk
i=1
fi;j fur j = 1; : : : ; r.
Hierbei sollen die fi;j so angeordnet werden, da die Nullstellen von fi;j in i liegen.
Das Produkt der Nullstellen eines Polynoms fi;j bezeichnen wir mit i;j . Sei ~ Q p (Frobeniusautomorphismus).
der Erzeuger der zyklischen Galoisgruppe von E=
Dann konnen wir o.E. davon ausgehen, da die Faktoren fi;j von fj so angordnet
7. BEISPIELE
61
sind, da fi;j = i (f1;j ) gilt. Wir erhalten:
h(t) =
=
Yk
i=1
Yk
i=1
(t i)
(t
Yr
j =1
i;j )
Hieraus folgt:
(h(t)) =
=
=
=
Yk
(t
Yr
i=1
Yk
j =1
Yr
i=1
Yk
j =1
(t
(i;j ))
(i+1;j )) mit k+1;j = 1;j
(t i+1 ) mit k+1 = 1
i=1
Yk
(t i) = h(t)
i=1
Damit ist gezeigt, da h 2 Zp[t] gilt. Hieraus folgt dann die Behauptung des
Satzes.
Satz 5.19. Es gelten die Bezeichnungen vom Algorithmus 5.17. Wir nehmen an,
da das Hensel-Lifting bis zu einer Genauigkeit modulo pk durchgefuhrt wurde.
Dann ist das so berechnete Polynom g modulo pk kongruent zum gesuchten erzeugenden Polynom.
Beweis: Der Beweis dieses Satzes verlauft vollkommen analog zum Beweis des
Satzes 5.15. Wir gehen wieder von K zu einer normalen Hulle N uber. Analog
erhalten wir, da das Ideal pZ in r Ideale vom Tragheitsgrad f zerfallt. Wiederum
bleibt pZ unverzweigt. Somit konnen wir alle Schritte dieses Beweises analog
durchfuhren.
7. Beispiele
Zum Abschlu dieses Kapitels wollen wir unsere Methoden an einem Beispiel
erlautern. Dazu knupfen wir an das Beispiel des letzten Kapitels an und wahlen
wieder den Korper K , der von f (t) = t6 + 108 erzeugt wird. Hierbei sind wir
62

5. ZUR KONSTRUKTION VON TEILKORPERN
an Teilkorper vom Grad 3 interessiert. Die moglichen Blocksysteme haben wir
bereits am Ende des 3. Kapitels ausgerechnet. Wir hatten uns entschlossen, die
Berechnungen mit p = 7 durchzufuhren. Es gilt:
f (t) (t3 + 2)(t3 + 5) mod 7:
Alle moglichen Blocke wurden mit k-Wert 3 konstruiert. Deswegen mussen wir
f in F q [t] mit q = 73 = 343 faktorisieren. Sei nun im folgenden w ein geeigneter
Erzeuger von F q . Damit gilt dann:
t3 + 2 = (t + w38)(t + w152)(t + w266 ) in F q [t].
t3 + 5 = (t + w95)(t + w209)(t + w323 ) in F q [t].
Wir wissen, da diese Nullstellen in zwei Zykeln der Lange 3 liegen. Momentan
wissen wir aber noch nichts uber die Reihenfolge. Hier hilft uns der Frobeniusautomorphismus weiter. Wegen (w38)7 = w266 und (w95)7 = w323 gilt,
= ( w38 w266 w152)( w95 w323 w209) = (w209w95 w323)(w266w152 w38):
Wir sortieren also die Faktoren entsprechend um und konnen diese Darstellung
dann in dem zugehorigen unverzweigten p-adischen Koerper E liften. Aufgrund
unserer Abschatzungen fur die Koezienten des Minimalpolynoms liften wir diese
Darstellung modulo p4. Im folgenden erzeugen wir E mit !(t) = t3 + 6t2 + 4.
Dabei ist p das maximale Ideal in E und eine Nullstelle von !. Im folgenden
meinen wir mit [a; b; c] das Element a + b + c 2. Wir erhalten:
f (t) (t + [204; 408; 51])(t + [101; 202; 575])
(t + [ 101; 202; 575])(t + [103; 206; 626])
(t + [ 103; 206; 626])(t + [ 204; 408; 51]) mod p4:
Die Faktoren sind bereits so angeordnet, da die jeweils in einer Zeile stehenden
zu einem Block geh
oren. Wir konnen nun 1; 2 und 3 berechnen und bilden
Q
das Polynom g~ = 3i=1(t i) = t3 108: Dieses Polynom ist aufgrund unserer
U berlegungen modulo 74 = 2401 kongruent zum gesuchten erzeugenden Polynoms
unseres Teilkorpers. Aufgrund unserer Abschatzung wissen wir, da die Koezienten unseres erzeugenden Polynoms betraglich kleiner als 217 sein mussen. Wenn
unser Blocksystem gultig war, so erzeugt g(t) = g~(t) = t3 108 unseren Teilkorper.
Ob unsere Vermutung richtig war, wird sich zeigen, wenn wir die Einbettung ausrechnen.
7. BEISPIELE
63
Fur die beiden nachsten Blocksysteme mussen wir das Hensel-Lifting nicht erneut
durchfuhren. Wir ordnen lediglich die bereits gelifteten Faktoren um und erhalten:
f (t) (t + [204; 408; 51])(t + [103; 206; 626])
(t + [ 101; 202; 575])(t + [ 204; 408; 51])
(t + [ 103; 206; 626])(t + [101; 202; 575]) mod p4 :
f (t) (t + [204; 408; 51])(t + [ 204; 408; 51])
(t + [ 101; 202; 575])(t + [101; 202; 575])
(t + [ 103; 206; 626])(t + [103; 206; 626]) mod p4:
Bei beiden Blocksystemen konnen wir wieder analog das mogliche Minimalpolynom des zugehorigen Teilkorpers ausrechnen und erhalten jeweils g(t) = t3 108.
Wir stellen also fest, da die so berechneten drei Korper isomorph zueinander sind.
Bei der Berechnung der Einbettung werden wir feststellen, da sie verschieden eingebettet werden und somit verschiedene Teilkorper erzeugen. Dazu werden wir im
nachsten Kapitel mehr erfahren.
64

5. ZUR KONSTRUKTION VON TEILKORPERN
KAPITEL 6
Zur Einbettung von Teilkorpern
1. Einleitung
In diesem Kapitel der Arbeit als Ergebnis ein Verfahren zur Einbettung von einem Teilkorper L in den Korper K . Dieser Einbettungsalgorithmus ist allerdings
davon abhangig, da der Teilkorper mit einem der beiden vorgestellten Verfahren
konstruiert worden ist. Allgemeine Einbettungsverfahren beruhen entweder auf
dem Faktorisieren von Polynomen uber Zahlkorpern oder auf Algorithmen, die
den LLL-Algorithmus verwenden. Diese Verfahren konnen z.B. in [Coh] nachgelesen werden. Sie sind aber in der Praxis fur groere Korpergrade (z.B. Einbettung
von Grad 10 in 20) erheblich zu langsam.
Wie in den vorherigen Kapiteln sei f 2 Z[t] normiert und irreduzibel vom Grad
n. Eine Nullstelle von f erzeuge den algebraischen Zahlkorper K . Weiterhin
seien f = 1; 2 : : : ; ng die Nullstellen von f . Der berechnete Teilkorper L vom
Grad m sei von einem erzeugt, dessen Minimalpolynom ein g 2 Z[t] ist. Analog
seien f = 1; 2; : : : ; mg die Nullstellen von g. Zusatzlich sei d die zugehorige
Blockgroe.
Unsere Berechnung beruht darauf, da wir wissen, da das erzeugende Polynom
des Teilkorpers L mit Hilfe von Satz 4.14 konstruiert worden ist. Dies bedeutet,
da die Nullstellen j das Produkt von d passenden Nullstellen i sind. Diesen
Umstand wollen wir fur eine eziente Berechnung der Einbettung ausnutzen.
Nach Satz 2.4 wollen wir ein Polynom ! 2 Q [t] derart berechnen, da g Minimalpolynom zu !() ist, d.h. !() = gilt. Aufgrund dieser Anforderung konnen
wir noch weitere Eigenschaften von ! herleiten, wie der folgende Satz zeigt.
Satz 6.1. Sei 1 ; : : : ; m das zugehorige Blocksystem zum Teilkorper L von K .
65

6. ZUR EINBETTUNG VON TEILKORPERN
66
Weiterhin seien die Nullstellen i o.E. so angeordnet, da die i mit (j 1)d +1 i jd in j liegen. Weiterhin habe ! 2 Q [t] die Eigenschaft !(1) = 1 . Dann
gilt fur 1 i n sogar ! (i) = j , wenn i 2 j ist.
Beweis:Q Es sei ein i xiert, so da i 2 j ist. Nach Voraussetzung ist !(1) =
1 = dk=1 k . Da G = Gal(f ) transitiv auf f1; : : : ; ng operiert, existiert ein
2 G, welches 1 auf i abbildet. Wegen der Blockeigenschaft bildet dieses jedes
Element von 1 auf ein Element von j ab. Damit gilt die folgende Gleichung:
!(i) = !((1)) = (!(1)) = (1) = (
Yd
k=1
k ) =
jd
Y
k = j
k=(j 1)d+1
Mittels dieses Satzes haben wir ein Kriterium gefunden, wie wir das Polynom
! ezient berechnen konnen. Durch die Gleichung !(i) = j (1 i n; j
passend) haben wir n Funktionswerte eines Polynoms gegeben, welches hochstens
Grad n 1 hat. Damit ist dieses Polynom durch die vorgegebenen Funktionswerte
eindeutig berechenbar. Um diese Werte berechnen zu konnen, benotigen wir wie
in den vergangenen Kapiteln eine Einteilung der Nullstellen i (1 i n) in
Blocke. Diese Einteilung kennen wir nur in einer passenden endlichen Erweiterung
von F p . Deswegen werden wir versuchen, dieses Polynom ! erst modulo p zu
berechnen, um danach das Ergebnis bis zu einer genugenden Genauigkeit zu liften.
Hiernach soll dann aus dieser Approximation das Polynom ! 2 Q [t] bestimmt
werden. Interessant an diesem Teil des Algorithmus ist, da wir mit modulo pApproximationen Elemente aus Q bestimmen konnen. Auf dieses Phanomen wird
in einem der folgenden Abschnitte noch genauer eingegangen werden.
Wir wollen im folgenden den Algorithmus skizzieren.
Algorithmus 6.2. Berechnung der Einbettung eines Teilkorpers
Input:
Output:
(1)
(2)
(3)
Erzeugendes Polynom f eines Korpers K .
Konstruiertes Erzeugendes Polynom g eines Teilkorpers L.
Einbettungspolynom ! 2 Q [t], falls L Teilkorper von K ist.
Fixiere ungerades p 2 P mit p 6 j disc(f ) disc(g).
Berechne das zugehorige Blocksystem. Falls dieses nicht eindeutig bestimmbar ist, fuhre die folgenden Schritte mit allen moglichen Blocksystemen
durch.
Bestimme aus dem Blocksystem ein !0 2 F p [t] mit der Eigenschaft !0(i ) j mod p (vgl. 6.1).
2. ZUR ABSCHA TZUNG DER KOEFFIZIENTEN DES EINBETTUNGSPOLYNOMS 67
(4)
(5)
(6)
Bestimme ein k 2 N derart, da p2k "gro genug\ ist.
Lifte !0 mittels des Newton-Liftings zu !k 2 Z=p2k Z[t], so da folgendes
gilt:
(a) !k !o mod p.
(b) g(!k) 0 mod (f; p2k ).
Berechne aus !k das Polynom ! 2 Q [t], welches g(! ) 0 mod f erfullt.
Falls dieser Schritt scheitert, wurde in (2) kein Blocksystem berechnet.
Wir wollen nun die einzelnen Schritte dieses Algorithmus kurz erlautern. Im ersten
Schritt mu eine Primzahl p xiert werden, bezuglich derer die approximativen Berechnungen durchgefuhrt werden sollen. Diese Primzahl darf nicht 2 sein, da fur
p = 2 das Newton-Lifting nicht durchfuhrbar ist. Im 2. Schritt soll das zugehorige
Blocksystem bestimmt werden. Falls das Minimalpolynom g mit dem 2. Algorithmus berechnet wurde, liegt dieses bereits vor. Ansonsten wurde bisher nur ein
Block bestimmt. Falls es nun noch mehrere Moglichkeiten fur konjugierte Blocke
gibt, so mussen diese einzeln durchprobiert werden, bis man eine Losung ndet.
Im 3. Schritt wird dann das Einbettungspolynom modulo p approximiert. Falls
dieser Schritt nicht gelingt, so war in Schritt 2 kein Blocksystem gefunden worden.
Im 4. Schritt mu eine Schranke bestimmt werden, bis zu der das Newton-Lifting
durchzufuhren ist. Auf die Berechnung dieser Schranke wird in den nachsten Abschnitten eingegangen werden. Im 5. Schritt wird das Newton-Lifting angewendet,
um ein Polynom !k mit den geforderten Eigenschaften zu berechnen. Auf dieses
Verfahren wird genauer in einem der nachsten Abschnitte eingegangen. Im letzten Schritt mussen wir probieren aus der modulo p2k -Approximation ein Polynom
! 2 Q [t] zu berechnen. Dabei wird in diesem Verfahren fur jeden Koezienten
einzeln das zugehorige Element aus Q bestimmt. Auch dieses Verfahren wird noch
genauer erlautert werden.
2. Zur Abschatzung der Koezienten des Einbettungspolynoms
Wie wir in der Einleitung dieses Kapitels bereits erwahnt haben, benotigen wir
Abschatzungen fur die Koezienten des Einbettungspolynoms. Leider liegt das
Einbettungspolynom ! i.allg. nicht in Z[t]. Dies liegt daran, da die Gleichungsordnung O, die von f erzeugt wird, nicht notwendigerweise Maximalordnung ist.
So kann es passieren, da die ganzalgebraische Zahl , welche primitives Element
von L ist, zwar in der Maximalordnung von K , aber nicht in der Gleichungsordnung O liegt. Man konnte zwar probieren, das Problem dadurch zu losen, da
man die Maximalordnung von K ausrechnet, um dadurch nur ganze Koezienten
fur ! zu erhalten. Diese Moglichkeit ist jedoch nicht praktikabel, da einerseits
68

6. ZUR EINBETTUNG VON TEILKORPERN
die Berechnung der Maximalordnung sehr aufwendig ist und andererseits unser
Einbettungsverfahren auf einer Potenzbasis von K beruht. So gibt es Korper, fur
die kein Element existiert, dessen Potenzbasis die Maximalordnung des Korpers
erzeugt. Deshalb werden wir uns in diesem Abschnitt mit den Abschatzungen fur
den Zahler und Nenner der Koezienten des zu berechnenden Einbettungspolynoms ! beschaftigen.
Wie in den vorangegangenen Abschnitten seien f; g 2 Z[t] normierte und irreduzible Polynome. Ferner seien f1; : : : ; ng die Nullstellen von f und f1; : : : ; m g
seien die Nullstellen von g. Weiterhin sei K = Q (1 ) und L = Q (1 ), wobei gilt,
da L ein Teilkorper von K ist. Zusatzlich bezeichnen wir mit 1 ; : : : ; m das
zugehorige Blocksystem.
Zur Losung unseres Problems betrachten wir zuerst die Diskriminante von f . Es
gelte disc(f ) = D12 D2, wobei D1 ; D2 2 Z und D2 quadratfrei ist. Dann ist es
eine bekannte Tatsache, da alle ganzalgebraischen Zahlen von K in D1 1Z[1]
liegen. Nehmen wir also an, da ! das gesuchte Einbettungspolynom mit der
Eigenschaft g(!(1)) = 0 ist. Dann ist D1 ! 2 Z[t] und hat die Form D1!(t) =
u0 + u1t + : : : + un 1tn 1 . Gema Satz 6.1 gilt dann die folgende Gleichung:
u0 + u1i + : : : + un 1in 1 = D1v(i) (i = 1; : : : ; n);
wobei i 2 v(i) ist. Wir denieren nun A durch die folgende n n Matrix:
0 1
1 1 1
BB 11 21 n1 CC
BB 2 2 2 CC
2
n C
BB .1
.
.
.
.
.
.
.
. . C
A
@ .
.
1n 1 1n 1 nn 1
Nach bekannten Formeln gilt dann disc(f ) = (det(A))2 = D12D2 . Wir konnen also
die ui (i = 0; 1; : : : ; n 1) bestimmen, indem wir das folgende Gleichungssystem
losen:
(u0; u1; : : : ; un 1) = D1 (v(1) ; v(2) ; : : : ; v(n) A 1):
Wir erhalten: D1 A 1 = jD2j Adj(A), wobei jj = 1 gilt. Falls fur alle 1 i n
eine Schranke c0 existiert mit jij c0, so gibt Hadamards Determinantenungleichung die folgende Abschatzung fur die ui (0 i < n):
1
2
n (n
juij jD2j n n c0
1)
+d
:
Um diese Abschatzung zu beweisen, mussen wir uns zuerst uberlegen, wie die
Matrix Adj(A) aussieht. Jedes Element dieser Matrix entspricht bis auf das Vorzeichen dem Wert einer (n 1) (n 1) Determinante, die dadurch entsteht,
1
2
2
1
2
3. DAS VERALLGEMEINERTE NEWTON-LIFTING
69
da wir eine Zeile und eine Spalte von A streichen. Fur die Berechnung dieser
werden wir die Hadamard'sche Determinantenungleichung benutzen. Allerdings
werden wir nicht das Produkt der Spalten, sondern da Produkt der Zeilen bilden.
Zuerst werden wir nun die euklidische Norm einer Zeile berechnen. Dabei ist es
unwichtig, welche Spalte gestrichen wird, da wir qalle i durch c0 abschatzen. Die
p
Zeilennorm der j -Zeile konnen wir dann durch nc2(0 j 1) = nc0j 1 abschatzen.
Den kleinsten Wert erhalten wir hier fur j = 1, da stets c0 1 gilt. Wenn wir also
jedes Element von Adj(A) nach oben abschatzen wollen, so konnen wir stets die
1. Zeile streichen. Wir erhalten also fur ein Element b von Adj(A) die folgende
Abschatzung:
jbj nY1 p
j =1
n (n
ncj0 = n n c0
2
1
2
1)
:
Da wir jedes Element b von Adj(A) so abschatzen konnen, erhalten wir so durch
einfaches Ausrechnen die gewunschte Formel.
Zum Abschlu wollen wir bemerken, da diese Schranken den Zahler und Nenner
nur ziemlich grob abschatzen. Wir benotigen an dieser Stelle nur die Existenz von
solchen Schranken. In der Praxis ist es erheblich schneller, wenn man mehrere
Schranken "durchprobiert\, bis man eine Losung ndet.
3. Das verallgemeinerte Newton-Lifting
In diesem Abschnitt werden wir das verallgemeinerte Newton-Lifting untersuchen.
Die Verallgemeinerung besteht darin, da das Newton-Lifting normalerweise uber
einem Korper durchgefuhrt wird, wie es zum Beispiel in [Lan] (Seite 308-311) beschrieben wird. John Dixon beschreibt in [Dix1], wie man diese Methode uber dem
Ring Zp[t] durchfuhren kann. Der entscheidene Unterschied in der Voraussetzung
liegt darin, da wir im Ring keine Division durchfuhren konnen. Betrachten wir
nun die Iteration, die beim "normalen\ Newton-Lifting durchgefuhrt wird. Diese
wird in [Lan] auf Seite 311 in Proposition 21 beschrieben. Dort wird
i+1 = i ff0((i))
i
gesetzt. Hierbei sind die i Elemente des Korpers. Bei uns entsprechen die i
dann den Polynomen !k aus dem Ring. Wie bereits gesagt konnen wir die Division, die in diesem Iterationsschritt durchgefuhrt wird, nicht berechnen. Deswegen
mussen wir uns fur diesen Teil einen Ersatz ausdenken. Dies wird in dem folgenden Satz deutlich werden. Der Beweis zu diesem Satz ist konstruktiv, so da wir
70

6. ZUR EINBETTUNG VON TEILKORPERN
einen Algorithmus sofort aus diesem herleiten konnen. Vorher werden wir aus
beweistechnischen Grunden noch zwei Lemmata zeigen.
Lemma 6.3. Sei a 2k Z und gelte a 1 mod p2k mit p 2 P und k 2 N . Dann gilt:
2a a2 1 mod p2 .
+1
Beweis: Wegen a 1 mod p2k gilt a 1 + bp2k mod p2k . Damit gilt:
2a a2 2(1 + bp2k ) (1 + bp2k )2 mod p2k
2 + 2bp2k 1 2bp2k (b2 p2k )2 mod p2k
1 mod p2k
+1
+1
+1
+1
Bezeichnung 6.4. Seien f; g; h 2 Zp[t]; p 2 P und k 2 N . Dann ist
g h mod (f; pk ) eine Schreibweise fur f j (g h) mod pk :
Lemma 6.5. Seien f; g und h 2 Zp[t] normiert und es gelte fur dieses p 2 P : p 6
j disc(f ) disc(g). Zusatzlich soll die Bedingung g(h) 0 mod (f; p) erfullt sein.
Dann gilt die folgende Beziehung: ggT(g 0(h); f ) 1 mod p.
Beweis: Die Polynome f; g und h seien auf kanonische Weise in F p [t] eingebettet.
Sei nun ! = ggT(g0(h); f ) in F p [t]. Hieraus folgt wegen f j g(h), da ! j g(h)
und ! j g0(h) gilt. Nehmen wir nun an, da ! 6 1 ist. Dann existiert in einem
passenden Erweiterungskorper von F p eine Nullstelle von ! (! ist normiert!).
Diese ist dann gleichzeitig auch Nullstelle von g(h) und von g0(h). Hiermit ist
dann h( ) Nullstelle von g und g0 und damit ware disc(g) = 0 (in F p [t]). Dies ist
aber ein Widerspruch!
Satz 6.6. Sei p 2 P und f 2 Zp[t]. Existiere weiterhin ein g 2 Zp[t] und ein
!0 2 Zp[t], so da folgendes gilt:
p 6 j disc(f ) disc(g)
g(!0) 0 mod (f; p)
Dann existiert ein ! 2 Zp[t], so da folgendes gilt:
! !0 mod p
g(!) 0 mod f
Weiterhin kann fur alle k 2 N ein !k bestimmt werden, fur welches !k ! mod
p2k gilt.
3. DAS VERALLGEMEINERTE NEWTON-LIFTING
71
Beweis: Nach Lemma 6.5 folgt ggT(g0(!0 ); f ) 1 mod p. Also existiert ein
h0 mit h0g0(!0) 1 mod (f; p). Wir konstruieren nun Folgen (!k ) und (hk ) mit
folgenden Eigenschaften (k 2 N ):
!k+1 !k mod (f; p2k )
(6-1)
k
2
hk+1 hk mod (f; p )
(6-2)
k
2
g(!k ) 0 mod (f; p )
(6-3)
k
hk g0(!k ) 1 mod (f; p2 )
(6-4)
Dazu fuhren wir folgende doppelte Iteration durch:
!k+1 !k hk g(!k ) mod (f; p2k )
(6-5)
k
hk+1 hk [2 hk g0(!k+1)] mod (f; p2 )
(6-6)
Wir zeigen nun, da die Eigenschaften durch die Iteration gewahrt bleiben:
zu (6-1):
(6-5)
!k+1 !k hk g(!k ) mod (f; p2k )
!k hk g| ({z!k )} mod(f; p2k )
+1
+1
+1
0 mod (f;p2k )
!k mod (f; p2k )
zu (6-2):
hk+1
(6-6)
hk [2 hk g0(!k+1)] mod (f; p2k )
hk [2 h| k g0({z!k+1)} ] mod (f; p2k )
k
+1
1 mod (f;p2 )
hk mod (f; p2k )
zu (6-3): Fur k = 0 gilt die Behauptung nach Voraussetzung.
(6-5)
g(!k+1) g(!k hk g(!k )) mod (f; p2k )
Taylor
g(!k ) hk g(!k )g0(!k ) mod (f; p2k )
0
2k
|g({z!k)} [1 |hk g{z(!k )} ] mod (f; p )
+1
+1
+1
0 mod(f;p2k )
1 mod(f;p2k )
0 mod (f; p2k )
+1

6. ZUR EINBETTUNG VON TEILKORPERN
72
zu (6-4): Fur k = 0 gilt die Behauptung nach Konstruktion von h0.
(6-6)
hk+1g0(!k+1) hk [2 hk g0(!k+1)]g0(!k+1) mod (f; p2k )
2( |hk g0({z!k+1)} ( h| k g0{z(!k+1} )2 mod (f; p2k )
+1
+1
6:3
1 mod(f;p2k )
1 mod (f; p2k )
1 mod(f;p2k )
+1
Damit ist gezeigt, da (!k ) eine Cauchyfolge in Zp[t] ist. Da Zp vollstandig ist,
konvergiert !k gegen ein ! 2 Zp[t]. Die Eindeutigkeit von ! folgt aus der Tatsache,
da f mod p und g mod p keine doppelten Nullstellen haben. Nehmen wir an, es
existiert ein 2 Zp[t] hochstens vom Grad n 1 mit den geforderten Eigenschaften.
Dann gelten fur alle i (i = 1; : : : ; n), die Nullstelle von f sind, da sowohl (i ) als
auch !(i) Nullstelle von g ist. Zusatzlich gilt wegen !0 mod p fur 1 i n:
(i) !(i) mod p. Da g mod p separabel ist, folgt hieraus (i ) = !(i) und
hiermit = !.
Aus dem Beweis dieses Satzes konnen wir den folgenden Algorithmus zusammenfassen.
Algorithmus 6.7. Verallgemeinertes Newton-Lifting
Input:
Output:
(1)
(2)
Polynome f , g und !0 2 Zp[t],
p 2 P mit p 6 j disc(f ) disc(g),
so da gilt: g(!0) 0 mod (f; p).
k 2 N.
Ein Polynom !k 2 Zp[t],
so da g(!k ) 0 mod (f; p2k ) und
!k !0 mod p gilt.
Berechne mit dem Euklidischen Algorithmus ein Polynom h0 2
das h0 g0(!0 ) 1 mod (f; p) gilt.
Fur i = 0; : : : ; k 1 tue folgendes:
Zp[t],
fur
!i+1 !i hig(!i) mod (f; p2i )
hi+1 hi (2 hi g(!i+1)) mod (f; p2i )
+1
+1
Die Korrektheit des obigen Algorithmus wird vollstandig in 6.6 gezeigt. Zur Implementierung von Schritt (1) wollen wir noch erwahnen, da der Euklidische
Algorithmus in F p [t] durchgefuhrt wird.
4. BESTIMMUNG DES EINBETTUNGSPOLYNOMS AUS DER APPROXIMATION 73
4. Bestimmung des Einbettungspolynoms aus der Approximation
Im vorigenk Abschnitt haben wir beschrieben, wie wir unser gesuchtes Polynom !
modulo p2 bestimmen konnen. Dabei konnten wir das k beliebig gro wahlen.
Jetzt mussen wir untersuchen, wie wir auf die rationalen Koezienten von !
zuruckschlieen konnen. Dies werden wir fur jeden Koezienten einzeln tun. Voraussetzung fur dieses Verfahren ist, da wir Abschatzungen fur den Zahler und
Nenner jedes einzelnen Koezienten besitzen. Wie wir diese erhalten, wurde bereits in einem fruheren Abschnitt beschrieben. Der folgende Satz, der in [Dix2]
beschrieben ist, ist Grundlage des nachfolgenden Algorithmus.
Satz 6.8. Seien s; h 2 N >1 . Weiterhin nehmen wir an, da a; b 2 Z existieren
mit
p
bs a mod h und jaj; jbj h;
wobei = 0; 618::: eine Nullstelle von 2 + 1 ist. Seien wvii (i = 1; 2; : : : )
die Naherungsbruche (convergents) der Kettenbruchentwicklung
fur hs und setze
p
ui = vi s wih. Sei k die kleinste ganze Zahl mit juk j < h. Dann gilt: ab = uvkk .
Beweis: Der Beweis dieses Satzes setzt Kenntnisse uber die Kettenbruchentwicklung voraus. Diese konnen [Khi] entnommen werden. So ist bekannt, da die
Folgen (wi) und (vj ) monoton steigend, wahrend die Folge der (ui) alternierend
und betraglich monoton fallend ist. Setze a = bs th. Dann gilt
2
j hs bt j = j hbab2 j hbh2 < 21b2
und so gilt nach 2.39, da bt einem Naherungsbruch von hs entspricht. Dieser
p sei
w
j
mit vj bezeichnet. Wegen a = bs th = vj s wj h = uj gilt juj j = jaj h <
p
h. Damit gilt nach der Denition von k, da j k gilt. Andererseits gilt
uj vk uk vj 0 mod h wegen uj = vj s wj h und uk = vk s wk h. Da zusatzlich
j k gilt, folgt
jvj j>jvk j
p p
juj vk uk vj j (juj j + juk j)jvj j h h < ( + 1)h = h:
Diese Ungleichung gilt, da bt = wvjj gilt. Da beide Bruche zusatzlich gekurzt sind,
p
gilt jvj j = jbj h. Wegen juj vk uk vj j < h gilt sogar uj vk = uk vj und somit
j = k. Damit ist gezeigt, da ab = uvkk gilt.
Wie wir dem Beweis dieses Satzes entnehmen konnen, liegt seine Schwierigkeit
in der Theorie der Kettenbruchentwicklung. Im folgenden werden wir die Frage
beantworten, wie wir die Naherungsbruche berechnen konnen. Dies braucht man

6. ZUR EINBETTUNG VON TEILKORPERN
74
nicht mit der Denition zu tun, sondern man kann eine Modikation des Euklidischen Algorithmus anwenden.
Algorithmus 6.9. Berechnung einer rationalen Zahl aus einer Approximation
Input:
Output:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
Ganze Zahlen s und h mit s; h > 1.
Ganze Zahlen apund b (falls existent) fur die bs a mod h
und jaj; jbj < h gilt.
Setze u 1 = h und u0 = s.
Setze v 1 = 0 und v0 = 1.
Setze i = 0p
.
Falls ui < h gib ( 1)i uvii aus und terminiere.
Setze qi = uui i .
Setze ui+1 = ui 1 qi ui.
Setze vi+1 = vi 1 + qi vi .
Setze i = i + 1 und gehe nach (4).
1
Falls die Zahlen a und b mit den geforderten Bedingungen nicht existieren, so gibt
der Algorithmus 0 aus. Falls 0 tatsachlich die gesuchte Losung war, so erkennt
man das daran, da bereits s 0 mod h war. In dem Algorithmus wird ein
Verfahren benutzt, welches auf den ersten Blick nicht viel mit der Berechnung
von Naherungsbruchen zu tun hat. Deswegen werden wir die Korrektheit des
Algorithmus beweisen.
Beweis: In 6.8 haben wir die Abhangigkeit der gesuchten Losung mit dem k-ten
Naherungsbruch der Kettenbruchentwicklung von hs bewiesen. Wenn nun wvkk der
k-te Naherungsbruch ist und uk = vk s wk ist, so ist uvkk = ab . Wir mussen nun
zeigen, da die ui und vi , die im Algorithmus berechnet werden, den ui und vi aus
dem Satz entsprechen. Dabei mussen wir zusatzlich beachten, da im Algorithmus
die ui nur dem Betrage nach bestimmt werden, d.h. wir mussen die erhaltenen ui
noch mit ( 1)i multiplizieren.
Als ersten Schritt wollen wir zeigen, da die qi aus dem Algorithmus gerade den
ai+1 entsprechen, wenn wir mit [a0 ; a1; a2 ; : : : ; an] die Kettenbruchentwicklung von
s
ur alle 0 i < n :
h bezeichnen. Wir setzen ri = [ai ; ai +1; : : : ; an ]. Nach 2.38 gilt f
s = wiri+1 + wi 1 :
h
viri+1 + vi 1
Durch einfache A quivalenzumformungen erhalten wir:
4. BESTIMMUNG DES EINBETTUNGSPOLYNOMS AUS DER APPROXIMATION 75
ri+1(vi s wih) =
(vi 1 s wi 1h)
Wegen ui = vis wih gilt:
ri+1 ui =
ui 1 :
Hieraus folgt: (Die ui sind aus Satz 6.8!)
ui 1 :
ui
Da die ui alternierend sind, ist der Bruch stets positiv. Damit folgt:
ri+1 =
ai+1 = qi :
Die letzte Gleichheit gilt, da ai+1 stets der groten ganzen Zahl entspricht, die
kleiner als ri+1 ist. Damit haben wir die Behauptung gezeigt, da die qi aus dem
Algorithmus den ai+1 der Kettenbruchentwicklung entsprechen.
Wenn wir
i
wi = vis (h 1) ui
setzen, wobei die ui aus dem Algorithmus kommen, so mussen wir zeigen, da die
so berechneten vi und wi denen aus dem Satz entsprechen. Falls uns dieses gelingt,
so ist die Korrektheit des Algorithmus bewiesen. Diesen Beweis wollen wir mit
vollstandiger Induktion fuhren. Aus v0 = 1 und u0 = s folgt direkt w0 = 0, womit
w = 0 = a ist. Aus v = 0 und u = h folgt dann w = 1. Hiermit ist
0
1
1
1
v
die Induktionsvoraussetzung fur i = 1 und i = 0 erfullt, wenn man den 1-ten
Naherungsbruch formal mit " 10\ bezeichnet.
Nach Satz 1 von [Khi] gilt fur Zahler und Nenner der Naherungsbruche folgender
Zusammenhang: (1 i n)
0
0
wi = ai wi 1 + wi 2 und vi = ai vi 1 + vi
2
Der Induktionsschritt fur die vi ist nach dieser Formel trivialerweise erfullt. Sei
76

6. ZUR EINBETTUNG VON TEILKORPERN
also nun i 1 und sei der Beweis fur alle wj mit j < i gefuhrt. Dann gilt:
v
i s ( 1)i ui
wi =
h
i
(
v
+
= i 2 qi 1 vi 1)s ( 1) (ui 2 qi 1ui 1)
h
i
1
i 2
= qi 1(vi 1 s ( 1) ui 1) + (vi 2s ( 1) ui 2)
h
= qi 1wi 1 + wi 2
= aiwi 1 + wi 2
Damit ist die Behauptung gezeigt.
5. Beispiele
In diesem Abschnitt wollen wir unser Beispiel aus den vergangenen Kapiteln zu
Ende rechnen. Wir hatten einen Korper K durch f (t) = t6 + 108 gegeben. Wir
haben bereits drei Teilkorper vom Grad 3 bestimmt, die alle durch g(t) = t3 108
erzeugt werden. Zum Abschlu des Algorithmus mussen wir die Einbettung dieser
Teilkorper in K bestimmen.
Als erstes bestimmen wir das Einbettungspolynom h modulo p, d.h. es gilt
f j g(h) mod p. Hierzu gruppieren wir die Nullstellen von f in das zugehorige
und bereits berechnete Blocksystem. In jedem Block i berechnen wir das Produkt i der Nullstellen. Diese Berechnungen werden alle uber dem endlichen
Korper F 7 durchgefuhrt. Wir mussen nun ein Polynom h bestimmen, fur welches h(i ) = j fur i 2 j und 1 i n gilt. Da h maximal Grad n 1 = 5
hat, wird h durch diese Gleichungen eindeutig bestimmt. Wir erhalten auf diese
Weise h(t) = 4t5 + 4t2 mod 7. Aufgrund unserer Abschatzung konnen wir den
Zahler der Koezienten des Einbettungspolynoms mit 64134065 und den Nenner
mit 15116544 abschatzen. Damit wir auf die Koezienten in Q zuruckschlieen
konnen, mussen wir unsere Einbettung bis mindestens 7 1015 liften. Wir liften
dann unser Einbettungspolynom bis 732 1027 und erhalten:
h(t) 1012392034723593925779857601 t5
+ 552213837121960323152649601 t2 mod 732:
Mit Hilfe von Algorithmus 6.9 konnen wir dann fur jeden Koezienten einzeln auf
die Koezienten aus Q zuruckschlieen. Wir erhalten: h(t) = 121 t5 + 12 t2 .
5. BEISPIELE
77
Zum Abschlu mussen wir testen, ob f j g(h) gilt. Wir stellen fest, da diese
Bedingung erfullt ist und konnen uns nun sicher sein, da wir einen Teilkorper
samt Einbettung berechnet haben.
Fur die beiden anderen Teilkorper erhalten wir auf diese Weise:
h(t) 1012392034723593925779857601 t5
+ 552213837121960323152649601 t2 mod 732:
Hieraus folgt: h(t) = 121 t5 + 12 t2.
Fur den letzten Teilkorper gilt:
h(t) 1104427674243920646305299200 t2 mod 732 :
Hieraus folgt: h(t) = t2 .
Beide erfullen die Bedingung f j g(h), so da wir insgesamt 3 Teilkorper vom Grad
3 berechnet haben.
78

6. ZUR EINBETTUNG VON TEILKORPERN
KAPITEL 7
Beispiele
Die in dieser Arbeit vorgestellten Algorithmen wurden in dem Computeralgebrasystem KANT (vgl. [Poh]) implementiert. Wir werden nun im folgenden einige
der berechneten Beispiele tabellarisch auisten. Die angegebenen Rechenzeiten
wurden auf einer HP 9000/735 ermittelt.
Olivier hat fur die Galoisgruppenberechnung Korpertabellen von imprimitiven
Korpern 9. Grades aufgestellt. Von diesen Korpern haben wir samtliche Teilkorper
berechnet. Da es sich um insgesamt 1112 Korper handelt, werden wir sie an dieser
Stelle nicht alle angeben. Im folgenden sei r1 die Anzahl der reellen Nullstellen.
r1 Anzahl
Anzahl Gesamtlaufzeit DurchschnittslaufKorper Teilkorper
zeit pro Korper
1
485
486
36:43 min
4,5 sek
3
423
446
31:25 min
4,5 sek
5
154
154
9:38 min
3,8 sek
7
23
23
1:30 min
3,9 sek
9
27
31
1:39 min
3,7 sek
Wir geben nun die Ergebnisse der Korper mit r1 = 9 an. In der folgenden Tabelle
gibt jeweils die erste Zeile ein erzeugendes Polynom des gegebenen Korpers an. In
der zweiten Zeile steht an der ersten Stelle die evtll. durchgefuhrte Substitution
und an der zweiten Stelle das berechnete erzeugende Polynom des Teilkorpers. In
der dritten Zeile schlielich steht die ermittelte Einbettung des Teilkorpers bezogen
auf das substituierte Polynom. Falls ein Korper mehrere Teilkorper besitzt, so
wird das erzeugende Minimalpolynom nicht wiederholt, sondern es werden nur die
zweite und dritte Zeile angegeben.
79
80
7. BEISPIELE
Erzeugendes Polynom des gegebenen Korpers
Durchgefuhrte Substitution
Erzeugendes Polynom des Teilkorpers
Einbettung des Teilkorpers
x9 + 2x8 14x7 32x6 + 16x5 + 61x4 + 15x3 18x2 5x + 1
x=x
x3 + 5x2 8x + 1
415 x8 827 x7 + 1898 x6 + 4325 x5 5111 x4 7047 x3 7271 x2 + 695 x + 200
669
669
223
223
669
223
669
669
669
x9 + x8 12x7 10x6 + 38x5 + 34x4 23x3 27x2 4x + 1
x=x
x3 + 8x2 + 6x + 1
2 8
25 7
11 6 247 5 189 4 571 x3 511 x2
15
13
101 x
101 x
101 x + 101 x + 101 x
101
101
101 x 101
x9 + x8 8x7 7x6 + 21x5 + 15x4 20x3 10x2 + 5x + 1
x=x
x3 5x2 + 2x + 1
x5 4x3 + x2 + 2x
x9 + 4x8 6x7 36x6 16x5 + 70x4 + 99x3 + 52x2 + 12x + 1
x=x
x3 4x2 + 3x + 1
5x8 20x7 + 31x6 + 183x5 + 71x4 377x3 483x2 199x 24
x =x+1
x3 + 22x2 + 138x + 181
8x8 + 95x7 + 389x6 + 505x5 637x4 2119x3 827x2 + 1681x + 1267
x9 + x8 13x7 18x6 + 28x5 + 48x4 + 6x3 17x2 8x 1
x=x
x3 5x2 + 6x 1
98 x8 37 x7 + 1294 x6 + 958 x5 3301 x4 2629 x3 + 953 x2 + 343 x + 184
9
9
9
9
9
9
9
3
9
x9 + 3x8 12x7 32x6 + 51x5 + 105x4 100x3 114x2 + 78x + 19
x=x
x3 21x2 + 54x + 19
447 8 17882 7 32343 6 188297 x5 260039 x4 + 577033 x3 + 507545 x2 540384 x
31051 x + 31051 x + 31051 x
31051
31051
31051
31051
31051
9
8
7
6
5
4
3
2
x 3x 11x + 39x + 11x 86x 15x + 64x + 28x + 1
x=x
x3 + 12x2 15x + 1
42 x8 129 x7 435 x6 + 1509 x5 + 123 x4 1860 x3 426 x2 + 15 x + 7
83
83
83
83
83
83
83
83
83
131841
31051
7. BEISPIELE
81
Erzeugendes Polynom des gegebenen Korpers
Durchgefuhrte Substitution
Erzeugendes Polynom des Teilkorpers
Einbettung des Teilkorpers
x9 + 2x8 12x7 22x6 + 34x5 + 70x4 + x3 30x2 4x + 1
x=x
x3 11x2 4x + 1
318 x8 + 269 x7 3832 x6 1807 x5 + 10956 x4 + 5173 x3 4678 x2 1411 x + 89
307
307
307
307
307
307
307
307
307
9
7
5
3
x 9x + 27x 30x + 9x + 1
x=x
x3 3x + 1
x3 3x
x9 15x7 7x6 + 66x5 + 48x4 70x3 30x2 + 27x 1
x=x
x3 6x2 45x 1
640 x8 1777 x7 6695 x6 + 16227 x5 + 21889 x4 39560 x3 18867 x2 + 20208 x 769
647
647
647
647
647
647
647
647
647
9
7
6
5
4
3
2
x 17x 6x + 87x + 47x 143x 69x + 72x + 27
x=x
x3 + 15x2 + 54x + 27
683 7 3556 6 11464 5 12999 x4 47824 x3 8160 x2 + 28678 x + 7257
212 8
3191 x
3191 x + 3191 x + 3191 x
3191
3191
3191
3191
3191
x9 15x7 + 4x6 + 61x5 19x4 80x3 + 16x2 + 34x 1
x=x
x3 10x2 + 17x 1
1383 x8 + 2476 x7 + 20204 x6 40294 x5 65783 x4 + 142626 x3 + 36511 x2 x + 3066
2087
2087
2087
2087
2087
2087
2087
2087
9
7
6
5
4
3
2
x 15x + 2x + 60x 15x 83x + 30x + 36x 17
x=x
x3 + 9x2 + 15x 17
3410 x8 + 2166 x7 49726 x6 24864 x5 + 188240 x4 + 69860 x3 238030 x2 52896 x + 88791
613
613
613
613
613
613
613
613
613
x9 + 2x8 12x7 11x6 + 44x5 + 16x4 62x3 + 28x 7
x=x
x3 7x 7
41 8
6 7 591 6 570 x5 1618 x4 + 1976 x3 + 952 x2 1667 x + 189
139 x + 139 x + 139 x
139
139
139
139
139
139
9
8
7
6
5
4
3
2
x + 2x 9x 10x + 27x + 11x 25x 3x + 6x 1
x=x
x3 3x2 4x 1
x7 + 2x6 8x5 7x4 + 22x3 14x + 3
82
7. BEISPIELE
Erzeugendes Polynom des gegebenen Korpers
Durchgefuhrte Substitution
Erzeugendes Polynom des Teilkorpers
Einbettung des Teilkorpers
x9 14x7 2x6 + 63x5 + 7x4 106x3 + 7x2 + 56x 13
x=x
x3 2x2 15x 13
168 x8 345 x7 1631 x6 + 3101 x5 + 3953 x4 7455 x3 308 x2 + 2159 x 1222
701
701
701
701
701
701
701
701
701
9
8
7
6
5
4
3
2
x + 2x 9x 15x + 25x + 37x 20x 31x 4x + 1
x=x
x3 8x2 + 5x + 1
2x8 + 5x7 12x6 28x5 + 14x4 + 38x3 + 9x2 3x
x9 11x7 + 38x5 48x3 + 7x2 + 21x 7
x=x
x3 7x 7
2x8 + 4x7 22x6 39x5 + 73x4 + 105x3 71x2 62x + 28
x9 + x8 15x7 6x6 + 76x5 24x4 130x3 + 133x2 38x + 1
x=x
x3 + 13x2 + 26x + 1
48 x8 + 99 x7 602 x6 22x5 + 2541 x4 + 1371 x3 4381 x2 + 1783 x 50
41
41
41
41
41
41
41
41
x9 + 2x8 13x7 15x6 + 57x5 + 27x4 78x3 27x2 + 32x + 13
x=x
x3 + 2x2 29x + 13
644 x8 1747 x7 + 6314 x6 + 11556 x5 21714 x4 15610 x3 + 18237 x2 + 5033 x 1794
547
547
547
547
547
547
547
547
547
9
7
6
5
4
3
2
x 11x + 3x + 35x 10x 42x + 7x + 17x + 1
x=x
x3 + 3x2 13x + 1
3x8 3x7 + 29x6 + 20x5 75x4 47x3 + 54x2 + 35x + 2
x9 2x8 8x7 + 18x6 + 10x5 36x4 + 10x3 + 12x2 7x + 1
x =x+2
x3 + 5x2 x 13
2x7 26x6 126x5 278x4 262x3 50x2 + 48x + 13
x9 15x7 3x6 + 68x5 + 16x4 122x3 26x2 + 76x + 13
x=x
x3 3x2 18x + 13
51 x8 + 99 x7 345 x6 1455 x5 + 2145 x4 + 4929 x3 1473 x2 4623 x 715
4
4
2
4
4
4
4
4
4
7. BEISPIELE
83
Erzeugendes Polynom des gegebenen Korpers
Durchgefuhrte Substitution
Erzeugendes Polynom des Teilkorpers
Einbettung des Teilkorpers
x9 + 4x8 8x7 38x6 2x5 + 79x4 + 45x3 20x2 11x 1
x=x
x3 17x2 + 10x 1
4281 x8 + 10709 x7 49586 x6 86523 x5 + 114257 x4 + 156419 x3 24015 x2 34749 x 3174
4319
4319
4319
4319
4319
4319
4319
4319
4319
9
8
7
6
5
4
3
2
x 2x 14x + 26x + 31x 42x 32x + 10x + 8x + 1
x=x
x3 + 3x2 4x + 1
527 8
843 7 7562 x6 + 10652 x5 + 18313 x4 14626 x3 17076 x2 1017 x + 1319
1471 x
1471 x
1471
1471
1471
1471
1471
1471
1471
x9 + 2x8 14x7 10x6 + 71x5 18x4 117x3 + 109x2 24x + 1
x=x
x3 + 6x2 + 5x + 1
16x8 55x7 + 145x6 + 368x5 609x4 583x3 + 1039x2 263x + 11
x9 15x7 + 4x6 + 54x5 12x4 38x3 + 9x2 + 6x 1
x =x+2
x3 + 33x2 + 279x + 127
3 x8 + 47 x7 + 138x6 + 367x5 + 376x4 104x3 377x2 131 x + 127
2
2
2
2
3
2
x =x+1
x + 6x 51x + 8
260 x8 2113 x7 3602 x6 + 7642 x5 + 22228 x4 + 1452 x3 25520 x2 15120 x 2360
127
127
127
127
127
127
127
127
127
3
2
x =x+1
x 12x + 12x + 8
194 x8 + 1603 x7 + 2969 x6 4987 x5 17623 x4 5673 x3 + 19247 x2 + 17583 x + 3832
127
127
127
127
127
127
127
127
127
3
2
x =x+1
x 8x + 12x + 8
711 x8 5979 x7 11547 x6 + 17847 x5 + 67221 x4 + 22583 x3 71751 x2 31752 x 6480
254
254
254
254
254
254
254
127
127
Beim Betrachten der Tabelle stellt man fest, da insgesamt 6 Teilkorper nur nach
einer Substitution berechnet werden konnten. Besonders interessant ist hier der
letzte Korper, wo alle Teilkorper teils erst nach zweifacher Substitution berechnet
werden konnten.
Als nachstes betrachten wir ein Beispiel eines Korpers vom Grad 12, der die A4
als Galoisgruppe hat. Ein erzeugendes Polynom fur diesen Korper ist:
x12 +x11 28x10 40x9 +180x8 +426x7 +89x6 444x5 390x4 75x3 +27x2 +11x+1:
84
7. BEISPIELE
Bekanntermaen gibt es 3 Teilkorper vom Grad 6, 4 Teilkorper vom Grad 4 und
einen vom Grad 3. Diese Korper haben wir mit unserem Verfahren berechnet.
Die Berechnungen haben 6:46 min benotigt. In der folgenden Tabelle steht jeweils
in der ersten Zeile ein erzeugendes Polynom des Teilkorpers und in der zweiten
Zeile seine Einbettung. Beim dritten und siebten Korper mute das erzeugende
Polynom vor der Berechnung mit x = x + 1 substituiert werden.
7. BEISPIELE
x6 6x5 2x4 + 48x3 45x2 22x + 1
197 x11 + 215 x10 1416 x9 8255 x8 + 9815 x7 + 21422 x6 1200 x5 102279 x4 52471 x3 +
196
196
49
196
49
49
49
196
196
1823 x2 + 4797 x + 279
98
196
98
x6 3x5 11x4 + 27x3 3x2 11x + 1
433 x11 443 x10 + 3050 x9 + 17603 x8 19991 x7 93677 x6 12949 x5 + 211713 x4 +
196
196
49
196
49
98
98
196
158845 x3 + 2497 x2 16091 x 655
196
49
196
49
x6 24x5 + 211x4 816x3 + 1282x2 528x 241
3473 x11 + 20273 x10 + 116829 x9 307383 x8 164015 x7 823842 x6 + 2548557 x5 + 21948643 x4 +
196
98
196
196
14
49
98
196
1971527 x3 + 14431917 x2 + 1621177 x 164603
14
196
196
49
x4 24x3 + 38x2 + 16x + 1
83 x11 + 29 x10 + 2287 x9 + 229 x8 7652 x7 14599 6 + 12655 x5 + 9698 x4 + 2775 x3
14
14
14
14
7
14x
14
7
7
444 x2 47x 81
7
14
x4 7x3 + 5x2 + 6x + 1
953 x11 629 x10 + 6771 x9 + 46419 x8 178833 x7 462883 x6 83043 x5 + 129868 x4 +
196
98
49
196
196
196
196
49
389689 x3 + 23745 x2 9657 x 3163
196
196
49
98
x4 28x3 15x2 + 3x + 1
64 x11 + 61 x10 7207 x9 4953 x8 + 11834 x7 + 107223 x6 + 12041 x5 120443 x4 88903 x3
49
49
196
98
49
196
196
196
196
3439 x2 + 8709 x + 1525
98
196
196
x4 10x3 32x2 + 410x 241
4x11 +46x10 +128x9 362x8 2560x7 3524x6 +5848x5 +24142x4 +30082x3 +
15750x2 + 1804x 723
x3 + 14x2 + 11x 1
335 x11 + 165 x10 4721 x9 3142 x8 + 130059 x7 + 187423 x6 81449 x5 236127 x4
98
196
49
49
196
196
196
196
21074 x3 + 11769 x2 + 8375 x + 443
49
196
196
98
85
86
7. BEISPIELE
Literaturverzeichnis
[Cas1] J.W.S. Cassels, An Introduction to the geometry of numbers, Springer-Verlag, Berlin Heidelberg - New York, 1971.
[Cas2] J.W.S. Cassels, Local Fields, Cambridge University Press, 1986.
[Coh] H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, Berlin
- Heidelberg - New York - London - Paris - Tokyo - Hong Kong - Barcelona - Budapest,
1993.
[Ded] R. Dedekind, Gesammelte mathematische Werke, 3 Bande, Vieweg, Braunschweig, 19301932.
[Dix1] J. Dixon, Computing Subelds in Algebraic Number Fields, J. Austral. Math. Soc. (Series
A) 49, (1990), 434{448.
[Dix2] J. Dixon, Exact Solution of Linear Equations Using p-adic Expansions, Numer. Math.
40, (1982), 137{141.
[Hil] D. Hilbert, Gesammelte Abhandlungen, Springer-Verlag, Berlin - Heidelberg - New York,
1970.
[Hup] B. Huppert, Endliche Gruppen I, Springer-Verlag, Berlin - Heidelberg - New York, 1967.
[Khi] A. Khintchine, Kettenbruche, Teubner Verlagsgesellschaft, Leipzig, 1956.
[Lan] S. Lang, Algebra, Addison-Wesley, Amsterdam - London - Manila - Singapore - Sydney Tokyo, 1974.
[LLL] A.K. Lenstra, H.W. Lenstra und L. Lovasz, Factoring Polynomials with Rational Coecients, Math.Ann. 261, (1982), 515{534.
[Mar] D.A. Marcus, Number Fields, Springer Verlag, New York - Heidelberg - Berlin, 1977.
[Nar] W. Narkiewicz, Elementary and Analytic Theory of Algebraic Numbers, Springer-Verlag,
Berlin - Heidelberg - New York - London - Paris - Tokyo - Hong Kong, 1990.
[Poh] M. Pohst, Computational Algebraic Number Theory, DMV Seminar Band 21, BirkhauserVerlag, Basel - Boston - Berlin, 1993.
[PoZa] M. Pohst und H. Zassenhaus, Algorithmic Algebraic Number Theory, Cambridge Univ.
Press, New York - Port Chester - Melbourne - Sydney, 1989.
[Wae] B.L. van der Waerden, Algebra I, Springer-Verlag, Berlin - Heidelberg - New York, 1971.
87
88
LITERATURVERZEICHNIS
Bezeichnungen
Wir vereinbaren die folgenden Bezeichnungen, falls sie nicht im Zusammenhang
erklart werden.
Menge der ganzen Zahlen
N
Menge der naturlichen Zahlen
Q
Menge der rationalen Zahlen
R
Menge der reellen Zahlen
C
Menge der komplexen Zahlen
P
Menge der Primzahlen
Sn
symmetrische Gruppe mit n! Elementen
An
alternierende Gruppe mit n2! Elementen
Gal(f ) Galoisgruppe des von f erzeugten Zerfallungskorpers
Fix(H ) der zu H gehorige Fixkorper
disc(f ) Polynomdiskriminante von f
p
Primzahl
Fp ; Fq
endliche Korper mit p bzw. q Elementen
Z
89
90
p; P
p(a)
BEZEICHNUNGEN
Primideale
Exponent von p in der Primidealzerlegung von a
Qp
Korper der p-adischen Zahlen
Zp
Ring der ganzen p-adischen Zahlen
Kp
p-adische Vervollstandigung des Zahlkorpers K
K
der gegebene algebraische Zahlkorper
oK
Ring der ganz algebraischen Zahlen von K
G
Die Galoisgruppe des Zerfallungskorpers von K .
L
ein Teilkorper von K
ein Block von G
f mod p
Ein f~ mit f f~ mod pZ[t]
a mod p
Ein a~ mit a a~ mod p
g h mod ! (g h) j ! in Q [t]
= 1 : : : u Element von G, zerlegt in elementfremde Zykel
[n1 ; : : : ; nu]
Zykeltyp von , d.h. die Langen der i
Hiermit versichere ich, da ich die vorliegende Arbeit selbststandig verfat und
keine anderen als die angegebenen Quellen und Hilfsmittel benutzt habe.
Berlin, den 22.12.94
Ich danke Herrn Professor M. Pohst fur die U berlassung dieses interessanten Themas sowie fur seine standige Diskussionsbereitschaft und seine Ratschlage. Weiterhin danke ich allen Mitarbeitern des Softwarepakets KANT, durch das die Implementierung der Algorithmen erst ermoglicht wurde.

¨Ubungen zur Linearen Algebra II Blatt 6

Nachklausur Einführung in die Algebra: Galois Theorie

Blatt 2 - FA - Bergische Universität Wuppertal

Klausur Einführung in die Algebra: Galois Theorie

1 括弧内の語句を用いてそれぞれの日本語に 1

103-H7823-1711 - RTA

ElGamal Verschlüsselung

Rezept downloaden (PDF)

RSA-Verschlüsselung

Musterlösung