Zur Klassengruppenberechnung
in algebraischen Zahlkorpern

DiplomarbeitvonFlorian He

Angefertigt am Fachbereich Mathematik
der Technischen Universitat Berlin
Berlin 1996

Inhaltsverzeichnis
1 Einleitung
2 Grundlagen35

3 Das Verfahren

19

4 Faktorbasis und Relationensuche

45

2.1
2.2
2.3
2.4
2.5

3.1
3.2
3.3
3.4
3.5
3.6
3.7

Moduln : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5
Algebraische Zahlkorper : : : : : : : : : : : : : : : : : : : : : : : 8
Gitter : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10
Einheiten : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12
Klassengruppe : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14

Klassengruppenberechnung als S -Einheitenberechnung : : : : : :S -Einheitengitter : : : : : : : : : : : : : : : : : : : : : : : : : : :Abbruchbedingungen : : : : : : : : : : : : : : : : : : : : : : : :Konvergenzverhalten des Eulerprodukts : : : : : : : : : : : : : : :Berechnung der Klassengruppenstruktur : : : : : : : : : : : : : :Veri kation der S -Einheiten : : : : : : : : : : : : : : : : : : : : :Zusammenfassung : : : : : : : : : : : : : : : : : : : : : : : : : : :4.1 Grundideen der Relationensuche : : : : : : : : : : : : : : : : : : :4.2 Smoothness-Eigenschaften : : : : : : : : : : : : : : : : : : : : : :4.3 Die Faktorbasis : : : : : : : : : : : : : : : : : : : : : : : : : : : :4.3.1 Reduktion einer Faktorbasis : : : : : : : : : : : : : : : : :4.3.2 Nachweis der Vollstandigkeit : : : : : : : : : : : : : : : : :4.3.3 Vorgehensweise in der Praxis : : : : : : : : : : : : : : : : :4.4 Relationensuche : : : : : : : : : : : : : : : : : : : : : : : : : : : :4.4.1 Test auf S -Einheit : : : : : : : : : : : : : : : : : : : : : :4.4.2 Schnelle Relationen : : : : : : : : : : : : : : : : : : : : : :4.4.3 Gute Relationen : : : : : : : : : : : : : : : : : : : : : : : :4.4.4 Gezielte Relationen : : : : : : : : : : : : : : : : : : : : : :4.4.5 Kombination der verschiedenen Strategien : : : : : : : : :4.4.6 Relationen aus dem Number Field Sieve : : : : : : : : : :4.5 Ausnahmeprimideale : : : : : : : : : : : : : : : : : : : : : : : : :
1

19
21
25
28
37
38
44

45
47
53
54
56
60
61
61
62
64
65
66
68
69

INHALTSVERZEICHNIS

2

4.5.1 Verbindung zur Methode der reduzierten Ideale : : : : : : 73

5 Anwendungen75

6 Beispiele
Symbolverzeichnis
Literaturverzeichnis

79
85
87

5.1 Die Klasse eines Ideals : : : : : : : : : : : : : : : : : : : : : : : : 75
5.2 S -Einheitenberechnung : : : : : : : : : : : : : : : : : : : : : : : : 78

Kapitel 1
Einleitung
Die Klassengruppe ist eine der wichtigen Invarianten eines algebraischen Zahlkorpers K . Sie ist ein Ausdruck dafur, wie weit der Ring der ganzalgebraischen Zahlen von K , der ein Dedekindring ist, von einem faktoriellen Ring oder auch einem
Hauptidealring entfernt ist. Ihre Kenntnis hilft bei vielen Fragestellungen weiter,
beispielsweise bei der Faktorisierung groer ganzer Zahlen oder bei der Frage nachder Losbarkeit nicht-linearer diophantischer Gleichungen. Allerdings ist uber die
Klassengruppe im allgemeinen, auer da sie abelsch und endlich ist, nur wenig bekannt. Eine der Aufgaben der konstruktiven algebraischen Zahlentheorie
besteht daher in der algorithmischen Bestimmung der Klassengruppe. Hierzu
wurden Verfahren zuerst von Pohst und Zassenhaus [17] und spater durch Buchmann [3] ausgehend von Hafner und McCurley [7] entwickelt. Verbesserungenstammen von v. Schmettow [21] und von Scheid [20]. Diese Verfahren basieren
alle auf der Relationenmethode. Die Idee hierbei ist, da jede (abelsche) Gruppe
als Faktorgruppe einer freien (abelschen) Gruppe nach einem von sogenannten
Relationen erzeugten Normalteiler dargestellt werden kann. Bei diesem Vorgehen
ergeben sich allgemein folgende Fragen: Welche und wieviele Erzeuger werden fur
die freie (abelsche) Gruppe benotigt? Wie ndet man die Relationen? Wann sindgenugend Relationen gefunden worden? Im Kontext einer Klassengruppenberechnung mu zur Beantwortung der ersten Frage eine geeignete endliche Menge vonPrimidealen, genannt Faktorbasis, angegeben werden. Diese Primideale erzeugen
mit der Idealmultiplikation eine freie abelsche Gruppe, deren Hauptideale die zu
ndenden Relationen darstellen.
In dieser Arbeit wird ein kombiniertes Verfahren zur Klassengruppenberechnungbasierend auf der Relationenmethode vorgestellt, in welches teilweise verbesserte
Techniken der bekannten Verfahren unter Berucksichtigung ihrer Ezienz aus
praktischer Sicht eingehen. Zusatzlich wurden auch neue Methoden integriert.
Die Schwierigkeit einer Klassengruppenberechnung kann in erster Linie an derGroe des Korpergrads und der Groe der Korperdiskriminante im Verhaltnis
zum Korpergrad abgelesen werden. Durch das hier dargestellte kombinierte Verfahren konnten (mit Hilfe einer Approximation des Eulerprodukts) Klassengrup3

4

KAPITEL 1. EINLEITUNG

pen eines Korper vom Grad 4 mit 36-stelliger Diskriminante und eines Korpers
vom Grad 46 mit 76-stelliger Diskriminante in relativ kurzer Zeit berechnet werden.
In Kapitel 2 werden die grundlegenden De nitionen und Satze zusammengestellt,
die fur die folgenden Kapitel benotigt werden. Kapitel 3 beschreibt die zugrundeliegenden Ideen des Verfahrens. Alle Schritte auer der Berechnung der Faktorbasis und der Relationensuche werden genau erlautert. Die gleichzeitige Berechnung
der Klassengruppe und der Einheitengruppe wird als Berechnung der S -Einheiten
von K aufgefat. Dies ermoglicht den Einsatz des Eulerprodukts, zu dem auch
Konvergenzbetrachtungen angestellt werden. Kapitel 4 ist ganz der Berechnung
einer Faktorbasis und der Relationensuche gewidmet. Durch Betrachtung vonSmoothnesswahrscheinlichkeiten wird gezeigt, wie die Relationensuche durch die
Wahl der Faktorbasis beein ut wird. Es wird beschrieben, wie eine Faktorbasis
reduziert und wie ihre Vollstandigkeit algorithmisch bewiesen werden kann. Danach werden verschiedene Methoden der Relationensuche diskutiert. Zum Schlu
wird die Methode der Ausnahmeprimideale beschrieben, mit der die zwei wesentlichen Arten der Relationensuche in Verbindung gesetzt werden konnen. Kapitel
5 zeigt zwei Anwendungsmoglichkeiten der wahrend einer Klassengruppenberechnung erhaltenen Daten. Es wird erlautert, wie die Klasse eines Ideals und wie
beliebige S -Einheiten bestimmt werden konnen. Im Kapitel 6 wird das Verhalten
des Klassengruppenverfahrens an einigen nichttrivialen Beispielen demonstriert.

Kapitel 2
GrundlagenIn den folgenden Abschnitten dieses Kapitels werden einige grundlegende Begri e
aus der algebraischen Zahlentheorie, auf die wir uns in dieser Arbeit meist stillschweigend beziehen wollen, kurz aufgelistet. Ausfuhrlichere Darstellungen mit
Beweisen konnen beispielsweise in [13, 16] gefunden werden.

2.1 Moduln
Wir wollen zuerst kurz auf Moduln und zwei damit in Verbindung stehende Matrixnormalformen eingehen. Mehr uber Moduln kann in [11] nachgelesen werden.
Unter einem R Modul versteht man einen kommutativen Ring (R; +; ) mit 1
zusammen mit einer abelschen Gruppe (M; +) und einer aueren Verknupfung
 : R  M ! M , welche R und M multiplikativ verbindet: Fur beliebige
r; r ; r 2 R und m; m ; m 2 M gelten die Gleichungen(r r )  m = r (r  m);(r + r )  m = r  m + r  m;r  (m + m ) = r  m + r  m ;1  m = m:A hnlich wie in R wird das Symbol  meist fortgelassen.
Ein Modul ist demnach sozusagen ein "Vektorraum\ uber R. Viele Begri e werden daher wortwortlich von Vektorraumenubernommen: Fur Moduln wird die lineare Unabhangigkeit von Elementen analog wie fur Vektorraume de niert. Eine
Basis eines Moduls ist ein linear unabhangiges Erzeugendensystem.
Man sagt, ein Modul sei frei vom Rang n, wenn er eine Basis bestehend aus n
Elementen besitzt. Mit obiger De nition ist der Rang stets eindeutig, je zwei
Basen haben gleiche Lange. Allerdings existiert nicht fur jeden Modul eine Basis.
In unseren Anwendungen werden wir es ausschlielich mit Z-Moduln zu tun haben. Der Ring Z ist ein Hauptidealring, und wir wollen dies nun fur R voraussetzen. Schnell sei noch bemerkt, da die Z-Moduln nichts anderes sind als abelsche
1

2

1

2

1 2

1

1

2

1

2

1

2

2

1

5

2

KAPITEL 2. GRUNDLAGEN

6

Gruppen (M; +) | schlielich ist jedes x 2 Z abgesehen vom Vorzeichen Summevon Einsen. Folglich werden wir dann spater nicht mehr explizit von Z-Moduln
reden.

Satz 2.1.1 Sei R ein Hauptidealring und M ein freier R-Modul vom Rang n.
Jeder Untermodul U von M ist dann frei vom Rang k mit k  n.
Einen U berblick uber die Struktur endlich erzeugter Moduln uber Hauptidealringen liefert

Satz 2.1.2 Sei R ein Hauptidealring und M ein endlich erzeugter R-Modul.
Dann gibt es Zahlen k; m 2  und c ; : : : ; ck 2  , so daM ' ( =c )  : : :  ( =ck )  m;
wobei m eindeutig bestimmt ist. Unter der Bedingung c j : : : j ck werden auch k
Z

Z

0

Z

1

1Z

Z

Z

2

Z

1

und die ci eindeutig durch M bestimmt.

Beweis: Die Beweise nden sich in [11].

In enger Verbindung zu diesen Satzen stehen die Hermite Normalform (HNF)
und Smith Normalform fur Matrizen uber R = Z. Wir befassen uns zuerst mit
der Hermite Normalform, die mit Satz 2.1.1 korrespondiert, und beschranken uns
speziell auf die Spaltenversion. Wir vereinbaren: max ; = 1 und min ; = 1.

De nition 2.1.3 Sei B = (bij ) 2 nm und Ij = f i j bij 6= 0 und 1  i  ng:
Wir setzen m = maxf j j Ij =6 ; und 1  j  mg, fj = min Ij und de nieren:Z

0

B ist in unterer Hermite Normalform, wenn f > : : : > fm0 und fur jedes j =1; : : : ; m gilt:
bij > 0fur i = fj ;0  bfk j < bfk k fur j < k  m :Die Matrix B ist in oberer HNF, wenn Be = (bn i;n j ) in unterer HNF ist.
100

Bei der Hermite Normalform handelt es sich also um eine spezielle Spaltenstufenform. Eine beispielsweise nur aus Nullen bestehende Matrix ist in oberer undunterer HNF. Diese De nition unterscheidet sich fur n 6= m von der De nitionin [16, 15]. Wenn nichts anderes gesagt ist, so meinen wir im folgenden mit einer
Hermite Normalform stets eine untere Hermite Normalform.

Satz 2.1.4 Sei A 2 nm. Dann gibt es invertierbare Matrizen T ; T 2 mm,
Z

Z

so da B = AT1 in unterer HNF und Be = AT2 in oberer HNF ist. B und Be sindeindeutig durch A bestimmt.
12

2.1. MODULN

7

Beweis: Zum Beweis verweisen wir auf [16, 5]. Dort nden sich auch Algo-rithmen zur Berechnung der Hermite Normalform einer Matrix. Die Eindeutigkeit kommt durch folgende U berlegungen zustande: Seien B und B zwei
Hermite Normalformen zu A. Die Spalten dieser drei Matrizen erzeugen wegen
der unimodularen Transformationen alle denselben Modul M  Zn. Fur v 2 M
schreiben wir vi fur die i-te Komponente und de nieren f (v) = minf i j vi 6= 0
und 1  i  ng. O enbar ist ff (v) j v 2 M nf0gg endlich und stimmt mit
ff ; : : : ; fm0 g fur B und ff ; : : : ; fm0 g fur B aus der De nition der HNF uberein. Folglich haben B und B dieselbe Stufengestalt. Zusatzlich stimmen auchdie Stufenelemente uberein. Wir bezeichnen mit Hj die j -te Spalte einer Matrix
H . Betrachte v = B ;j B ;j fur 1  j  m . Wir wollen annehmen, da die
Gleichheit der k-ten Spalten von B und B fur j < k  m gezeigt ist. Es ist
nicht moglich, da f (v) = fj , da die fj -ten Komponenten von B ;j und B ;j gleichsind. Nehmen wir an, da f (v) = fk fur j < k  m . Die fk -te Komponente vonv ist durch die fk -ten Komponenten von B ;k bzw. B ;k | die gleich sind | teilbar und daher wegen der Reduktionseigenschaft im Widerspruch zur Annahme
gleich Null. Es folgt v = 0.
Die Matrix B bezeichnet man als (untere) Hermite Normalform, Be als obere
Hermite Normalform von A.
Invertierbare Matrizen T 2 Zmm heien unimodular. Es gilt
T invertierbar in Zmm , det(T ) invertierbar in Z:
Folglich sind die unimodularen Matrizen uber Z genau die Matrizen mit Determinantenbetrag gleich 1.
Wir wenden die Hermite Normalform auf die Situation eines freien Z-Moduls M
vom Rang n mit Untermodul U vom Rang k an. Sei v ; : : : ; vn eine Basis von M
und u ; : : : ; um ein Erzeugendensystem von U . Wir nehmen an, da wir die ui
explizit durch die vi ausdrucken konnen und wollen eine Basis von U ermitteln.
Es gibt also eine Matrix A 2 Znm mit(v ; : : : ; vn) A = (u ; : : : ; um):
Wir konnen von rechts mit einem geeigneten unimodularen T 2 Zmm multiplizieren, welches A in eine HNF B uberfuhrt, und erhalten(v ; : : : ; vn) B = (ue ; : : : ; uek ; 0; : : : ; 0)
mit m k vielen Nullen. Die uei bilden aufgrund der Gestalt von B und der Invertierbarkeit von T eine Basis von U . Hat U den Rang k = n, so ist B eine untere
Dreiecksmatrix ohne Nullen auf der Diagonalen mit m k hinteren Nullspalten.
Wir schneiden diese Nullspalten ab und folgern fur den Index abelscher Gruppen:(M : U ) = j det B j:
Nun zur Smith Normalform (SNF), die mit Satz 2.1.2 in Verbindung steht.
1

1

1

1

1

2

2

2

1

2

0

1

2

0

1

0

1

2

1

1

1

1

1

1

2

KAPITEL 2. GRUNDLAGEN

8

De nition 2.1.5 Eine Matrix B = (bij ) 2 nm vom Rang k ist in Smith Normalform, wenn gilt:
bij = 0 fur i =6 j;Zbii = 0 fur i > k;bii > 0 fur i  k;
und b j : : : j bkk :11Satz 2.1.6 Sei A 2 nm. Dann gibt es unimodulare Matrizen T 2 nn und
T 2 mm, so da B = T AT in Smith Normalform ist. B ist eindeutig durch
Z

2

Z

1

1

A bestimmt.

Z

2

Beweis und Algorithmen siehe [16, 5]. Wir bezeichnen B als Smith Normalformvon A.
Wahrend wir bei der obigen Anwendung der Hermite Normalform nur Basiswechsel im Untermodul U zulassen, soll dies nun auch in M geschehen durfen. Wirwollen im Hinblick auf die spatere Anwendung gleich annehmen, da der Rangvon U mit dem Rang von M ubereinstimmt. Nach Bildung der Smith Normalform B von A erhalt man eine Diagonalmatrix ohne Nullen auf der Diagonalen
mit m n angehangten Nullspalten. Durch das Abschneiden dieser uber ussigen
Nullspalten erhalten wir eine Transformationsmatrix C = (cij ) einer Basis vonM auf eine Basis von U . Wir folgern, da

M=U ' ( =c )  : : :  ( =cnn )
Z

11 Z

Z

Z

und erhalten damit die eindeutige Darstellung von M aus Satz 2.1.2. Tatsachlichkann dieser Satz mit Hilfe der Smith Normalform und Satz 2.1.1 bewiesen werden.
Wir werden spater genau wie hier dargestellt die Hermite Normalform und Smith
Normalform dazu verwenden, aus einem M und U die Struktur von M=U zu
bestimmen.

2.2 Algebraische Zahlkorper
Es sei f (t) ein normiertes und irreduzibles Polynom aus Z[t]. Ein algebraischer
Zahlkorper K wird durch Adjunktion einer Nullstelle  = t + f (t)Q [t] von f (t)zu Q de niert:
K = Q [t]=f (t)Q [t] = Q ():Der Grad der Korpererweiterung stimmt mit dem Grad des Polynoms uberein
und wird mit n bezeichnet. Die r reellen und 2r komplexen Nullstellen von f (t)numerieren wir wie folgt:
1  ;:::; r 2 ,
(1)

( 1)

R

2


2.2. ALGEBRAISCHE ZAHLKORPER9  r ;:::; r r 2 n ,  r r i =  r i fur 1  i  r .
( 1 +1)( 1+ 2)( 1+ 2+ )( 1+ )CR

2

Man erhalt damit die n Q -linearen Einbettungen von K in C

i : K ! ; i () =  i( )Cfur 1  i  n. Das Element  i wird auch als i-te Konjugierte von  bezeichnet.
Unter der Signatur von K verstehen wir das Tupel (r ; r ).
Ein Element x 2 K heit ganzalgebraisch, wenn es einer Ganzheitsgleichunggenugt, wenn also ein normiertes Polynom g(t) aus Z[t] mit g(x) = 0 existiert.
Die ganzalgebraischen Zahlen von K bilden einen Ring, der Maximalordnung
genannt und mit oK bezeichnet wird. Die Maximalordnung tragt die Struktureines freien Z-Moduls vom Rang n, dessen Basen Ganzheitsbasen von K heien.
Wir wahlen stets eine Ganzheitsbasis ! ; : : : ; !n 2 oK derart, da ! = 1 ist; dies
ist immer moglich.
Die Norm und die Spur eines Elements x 2 K werden de niert durch
( )

1

1

NK=Q (x) =und

TrK=Q (x) =

2

1

n
Y
i=1

xi

( )

n
X
xi:
( )

i=1

Stets sind NK=Q (x), TrK=Q (x) 2 und fur ein ganzalgebraisches Element x gilt
NK=Q (x), TrK=Q (x) 2 .
Mit Hilfe einer Ganzheitsbasis de nieren wir die Korperdiskriminante DK durch
QZ

DK = det((TrK=Q (!i!j )) i;jn):1Diese De nition ist von der Wahl der Ganzheitsbasis unabhangig, da sich Diskriminanten bei Basiswechsel um das Quadrat der Determinante der Transformationsmatrix andern und je zwei Ganzheitsbasen durch unimodulare Transformation ineinander ubergehen. Bei DK handelt es sich stets um einen ganzrationalen Zahl, und nach einem Resultat von Minkowski gilt fur von Q verschiedene Zahlkorper jDK j > 0. Schlielich betrachten wir die GleichungsordnungZ[]. Z[] ist ein Untermodul von oK und ebenfalls frei vom Rang n. Der Index(oK : Z[]) ist endlich.
Zur Arithmetik in einem Zahlkorper und zur Berechnung von Ganzheitsbasen,
Diskriminanten, Norm usw. siehe [16, 15, 5].

KAPITEL 2. GRUNDLAGEN

10

2.3 Gitter

Sei   R m ein freier Z-Modul vom Rang k. Enthalt  k uber R linear unabhangige Vektoren, so sprechen wir von einem Gitter der Dimension k im R m .
Die Gitterdeterminante d() eines Gitters  der Dimension k im R m wird deniert als das k-dimensionale Volumen des von einer Z-Basis v ; : : : ; vk von aufgespannten Parallelotops:
1d() = j det((vit vj ) i;jk )j 21 :1

Ist k = m, so nennen wir das Gitter vollstandig. Gitter sind diskrete Teilmengen des R m , jede Kugel (endlichen Durchmessers) enthalt nur endlich viele
Gitterpunkte.
Fur uns wird es wichtig sein, Elemente x 2 oK mit kleinen ganzen Normbetragenzu bestimmen. Die Norm von x ist das Produkt uber die n Konjugierten von x;
es mussen also alle Konjugierten berucksichtigt werden. Dies geschieht in Konjugiertengittern zu freien Z-Untermoduln M von oK vom Rang n. Wir de nieren
diese fur einen beliebigen freien Z-Untermodul M von K vom Rang n mit Basis; : : : ; n 2 M wie folgt:
Auf dem Q -Vektorraum K ist ein inneres Produkt gegeben durch
1< ; > : K  K ! ; (x; y) 7 !
R

n
X
xiyi:
( )

( )

i=1

Wir de nieren hiermit eine positiv de nite quadratische Form, die T -Norm,durch
T : K ! R  ; x 7 !<x; x> :Mit Hilfe der ; : : : ; n, die eine Q -Basis von K bilden, und unter Beachtung
der Matrix
B = ( ji ) i;jn 2 C nnerhalten wir die Grammatrix des inneren Produkts von K durch die positiv denite Matrix
A = (< i; j >) i;jn = B t B 2 R nn :Ist also x = Pni xi i mit xi 2 Q , so gilt fur die T -Norm
2

0

2

1

( )

1

1

2

=1

0 1
BB x.. CC
T (x) = (x ; : : : ; xn)A @ . A :xn
Wir de nieren nun ein zu M als -Modul isomorphes Gitter (M ) im n , in dem
1

2

1

Z

R

das euklidische Skalarprodukt bezuglich der Bilder der i unter dem Isomorphismus ebenfalls die Grammatrix A besitzt. Dann fallen o enbar das Quadrat der2.3. GITTER

11

euklidischen Norm und die T -Norm unter Identi zierung von Gitterpunkten mit
den Elementen von M zusammen. Wir de nieren (M ) als das Bild des Monomorphismus M ! R n , der ein x 2 M auf
2

p

p

p

p

(x ; : : : ; x r1 ; 2 Re x r1 ; 2 Im x r1 ; : : : ; 2 Re x r1 r2 ; 2 Im x r1 r2 )t
(1)

(

)

(

+1)

(

+1)

(

+

)

(

+

)

aus R n abbildet. Q -linear unabhangige Elemente werden hierdurch in R -linear unabhangige Vektoren uberfuhrt. Daher handelt es sich bei (M ) um ein vollstandiges Gitter im R n , welches wir das Konjugiertengitter zu M nennen. Gehen wir
von B uber zu einer Matrix Be 2 R n , deren Spalten die Bilder der ; : : : ; nunter obigem Monomorphismus sind, so gilt
1

A = Be t Be

und fur die Gitterdeterminante von (M ) erhalten wird((M )) = j det Aj 21 :Ist M  oK , so gilt d((M )) 2 Z. Um den Bezug zur Diskriminante DK
herzustellen, nehmen wir an, da2( ; : : : ; n) = (! ; : : : ; !n) TM
11

mit einer Transformationsmatrix TM 2 Znn gilt. Unter dieser Voraussetzung
folgt die Gleichheitd((M )) = jDK j det(TM ) :Wir wollten das Konjugiertengitter (M ) fur M  oK zur Bestimmung ganzalgebraischer Zahlen x 2 oK kleinen Normbetrags nutzen. Dies geschieht vermoge
des folgenden Zusammenhangs von Norm und T -Norm, der eine Konsequenz derUngleichung zwischen arithmetischen und geometrischen Mittel ist:
2

2

2

!n
T
(x) 2
jNK=Q (x)j  n:
Ist die T -Norm klein, so auch der Normbetrag. Umgekehrtes gilt jedoch nicht.
Die Bestimmung T -Norm beschrankter Elemente entspricht dem Auszahlen einer
Kugel beschrankten Durchmessers in (M ) und erfolgt mit dem Auszahlalgorithmus von Fincke und Pohst fur positiv de nite quadratische Formen angewendet
auf die Grammatrix A, siehe [16, 15]. Hiermit konnen wir sukzessive alle Elemente dieser beschrankten Kugel in (M ) bestimmen.
Fur manche Gitter mit schlecht konditionierten Basen mu allerdings vorher eine
LLL-Reduktion durchgefuhrt werden. Der LLL-Algorithmus und die Eigenschaften LLL-reduzierter Basen werden eingehend in [16] beschrieben. Wir erwahnen
nur kurz, da die Elemente einer LLL-reduzierten Basis Kandidaten fur kurze
222

KAPITEL 2. GRUNDLAGEN

12

Vektoren im Gitter sind. Insbesondere das erste Basiselement stellt im allgemeinen eine gute Approximation eines kurzesten Vektors im Gitter dar.
Gegeben seien linear unabhangige Vektoren b ; : : : ; bk eines Gitters  im R m undein Vektor v 2 nf0g. Wir wollen das von den bi und v erzeugte Teilgitter bestimmen. Sind v; b ; : : : ; bk linear unabhangig, so bilden sie bereits eine Basis dieses Teilgitters. Andernfalls wird eine modi zierte Version des LLL-Algorithmus,
der MLLL-Algorithmus, verwendet. Auch er ist in [16] beschrieben. Seine Ausgabe besteht aus einer Basis des gesuchten Teilgitters bzw. einer Transformationsmatrix,
die v und die bi in diese Basis uberfuhrt, und aus einer RelationPkv = i i bi mit ; i 2 Z und  6= 0. Dieser Algorithmus lat sich ubrigens so
durchfuhren, da nicht im voraus die Abhangigkeit von v und b ; : : : ; bk feststehenmu. Sind diese Elemente unabhangig, so werden sie dann einfach LLL-reduziert.
Wir bemerken, da diese Aufgabe der Berechnung einer Basis ahnlich der aus
Abschnitt 2.1 ist. Dort konnte eine Basis des Untermoduls U eines freien Moduls
M aus einem Erzeugendensystem von U mit Hilfe einer Hermite Normalform berechnet werden. Die Erzeuger von U lieen sich namlich durch die Basiselemente
von M darstellen. Da uns ein solches M hier fehlt, konnen wir diesen Weg nichtbeschreiten.
1

1

=1

1

2.4 Einheiten

Unter einer Einheit von K versteht man eine ganzalgebraische Zahl " 2 oK , fur dieauch " 2 oK ist. Ein " 2 oK ist genau dann eine Einheit, wenn jNK=Q (")j = 1
ist.
Wir kommen zur Einheitengruppe UK der Maximalordnung eines algebraischen
Zahlkorpers K . Mit TUK werde die endliche zyklische Gruppe der Torsionseinheiten, also der Einheitswurzeln, bezeichnet. Ihre Ordnung sei wK . U ber die
Struktur von UK besagt der folgende Satz:
1

Satz 2.4.1 (Dirichletscher Einheitensatz) Die Einheitengruppe UK ist die

direkte Summe der Gruppe TUK und einer freien abelschen Gruppe vom Rang
r1 + r2 1.

Die Zahl r + r 1 heit Einheitenrang von K und wird mit r bezeichnet. Es gibt
also Einheiten " ; : : : ; "r 2 UK so da sich jede weitere Einheit " 2 UK eindeutig
als ein Potenzprodukt der Form121

" =  "k1    "kr r1

mit  2 TUK und k ; : : : ; kr 2 Z darstellen lat. Solche Einheiten " ; : : : ; "rheien Fundamentaleinheiten.
112.4. EINHEITEN

13

In Abschnitt 2.1 wurde erwahnt, da jede abelsche Gruppe als Z-Modul aufgefat werden kann. Dies wollen wir speziell fur Untergruppen der multiplikativen
Gruppe K  tun. Der Addition im Modul entspricht dann die Multiplikation inK , der Multiplikation mit Zahlen aus Z die Potenzbildung mit diesen Zahlen
als Exponenten.

De nition 2.4.2 Eine Menge von algebraischen Zahlen ; : : : ; m 2 K  heit1

unabhangig, wenn

1    m = 1
m1)  = : : : = m = 0
1

gilt.

O enbar sind Fundamentaleinheiten nach dem oben Gesagten immer unabhangig,
Torsionseinheiten sind dagegen schon jede fur sich genommen abhangig.
Mit Hilfe der folgenden Abbildung konnen wir die multiplikative Struktur vonUntergruppen von K  in die additive Struktur des R r uberfuhren. Unter Beachtung von ci = 1 fur 1  i  r und ci = 2 fur r < i  r wird de niert:
10c
log j jCC
B...
L : K  ! Rr ; 7 ! BA:@r
cr log j jDiese Abbildung ist ein Homomorphismus der beteiligten Z-Moduln. Wir konnten nun das Bild einer Untergruppe von K  mit Methoden der linearen Algebra uber R untersuchen, um Ruckschlusse auf die Untergruppe selbst zu ziehen. L weist allerdings eine Schwache auf: Unabhangige Elemente von K werden nicht unbedingt auf R -linear unabhangige Vektoren abgebildet. Jedochsind Einheiten " ; : : : ; "m 2 UK genau dann unabhangig, wenn die Vektoren
L(" ); : : : ; L("m) 2 R r linear unabhangig uber R sind. Wir werden L also zur
Untersuchung von UK heranziehen.
Sei U eine Untergruppe der Einheitengruppe mit endlichem Index (UK : U ).
Das Bild von U unter L ist ein vollstandiges Gitter im R r . Zu einer Basis von
L(U ) gehorende Einheiten " ; : : : ; "r 2 U sind unabhangig und erzeugen U modulo Torsioneinheiten. Die Gitterdeterminante von L(U ) bezeichnen wir als den
Regulator von U :
1

1

1

(1)

( )

1

1

1

Reg(U ) = j det(L(" ); : : : ; L("r ))j = d(L(U )):1

Der Regulator des Zahlkorpers K wird als Regulator der gesamten Einheitengruppe UK de niert und mit RK bezeichnet. Diese De nitionen sind, aus ahnlichen Grunden wie schon oben die De nition der Diskriminante, unabhangig
von der Wahl der Einheiten " ; : : : ; "r . Sie sind aber auch unabhangig von derAnordnung der Konjugierten.
1

KAPITEL 2. GRUNDLAGEN

14

Wir bemerken unter Berucksichtigung der Ergebnisse des Abschnitts 2.1, da derRegulator von U ein ganzzahliges Vielfaches von RK ist. Mit der Bezeichnung U 0
fur das Erzeugnis von TUK und U gilt:
Reg(U ) = (U : U 0 ):
(2.1)
K
RK
Zur Berechnung der Einheiten eines Zahlkorpers siehe [16, 15, 22].

2.5 Klassengruppe
Die Maximalordnung von Q ist Z. In diesem Ring gilt der Satz von der eindeutigen Zerlegung in Primfaktoren. Mehr noch, Z ist ein Hauptidealring. Diese
beiden Eigenschaften sind fur Maximalordnungen beliebiger Zahlkorper aquivalent, tre en allerdings im allgemeinen nicht zu. Erhalten bleibt nur die Faktorisierbarkeit in irreduzible
p Beispiel hierfur ist
p Elemente. Ein hau g genanntes
der Zahlkorper K = Q ( 5) mit Maximalordnung Z[ 5]. Hierin bestehen
beispielsweise folgende verschiedene Zerlegungen der Zahl 6 in irreduzible, abernicht prime Elemente:
6 = 2  3 = (1 +

p

5)(1

p

5):

Eine eindeutige Zerlegung in Primfaktoren wird jedoch moglich, wenn man vonElementen zu Idealen ubergeht.
Sprechen wir im folgenden von Idealen von oK , so schlieen wir das Nullideal,
das nur aus dem Nullelement besteht, aus. Wir lassen oK als Ideal von oK zu.
Ein Primideal p von oK ist ein echtes Ideal von oK , also p 6= oK , fur das oK =pnullteilerfrei ist. Wir de nieren Addition und Multiplikation von Idealen a; b
durch
a + b = fa + b j a 2 a; b 2 bg
undkX
ur 1  i  kg:
ab = f ai bi j k 2 Z und ai 2 a; bi 2 b f0

i=1

Man sieht leicht, da beide Verknupfungen assoziativ und kommutativ sind undda oK neutrales Element der Multiplikation ist. Die Ideale von oK bilden mit
der Idealmultiplikation daher einen Monoid, ganz ahnlich wie die ganzen Zahlen
mit ihrer Multiplikation.
Jedes Ideal a einer Maximalordnung oK lat sich nun eindeutig bis auf die Reihenfolge als ein Potenzprodukt mit positiven Exponenten von paarweise verschiedenen Primidealen p ; : : : ; pk von oK schreiben:
11
a = pm   pmk k :1

2.5. KLASSENGRUPPE

15

Wir fassen hierbei oK als das "leere\ Produkt auf. Man sagt, die MaximalordnungoK sei ein Dedekindring. Auf den Fall des obigen Beispiels bezogen ndet man
mitpp 5)o ;
p = 2oK + (1 + p 5)oK = 2oK + (1K
p = 3oK + (1 + p 5)oK ;p = 3oK + (15)oK
die eindeutigen Zerlegungen123

2oK = p ; 3oK = p p ; (1 +2
1

und schlielich

2

3

p

5)oK = p p ; (112p5)oK = p p

1 3

6oK = p p p :Die Primzahlzerlegung in Z lat sich unter Hinzunahme negativer Potenzen auf
Zahlen aus Q ausdehnen. Analog kann man die Primidealzerlegung fur die Ideale
von K de nieren. Diese sind die Elemente der Menge
2
1

2

3

IK = fa  K j xa ist ein Ideal von oK fur ein x 2 K g;
die mit der oben de nierten Idealmultiplikation angewendet auf diese verallgemeinerten Ideale eine abelsche Gruppe mit Einselement oK wird. Da IK eine
Gruppe ist, liegt keineswegs auf der Hand. Diese Eigenschaft ist aquivalent zur
Primidealzerlegung in oK und nur der Ring aller ganzalgebraischen Zahlen von
K erfullt diese Eigenschaft. In der Gleichungsordnung Z[] ist sie beispielsweise
im allgemeinen nicht erfullt.
Unter einem Hauptideal von K verstehen wir ein Ideal a 2 IK , fur das ein x 2 K 
mit a = xoK existiert. Die Hauptideale bilden eine Untergruppe von IK , die mit
HK bezeichnet wird. Wir betrachten die Abbildung

I : K  ! HK ; x 7 ! xoK :Der Kern von I ist UK und daher besteht die Isomorphie

K =UK ' HK :Da man die Elemente von K  in Faktorisierungsfragen nur modulo Einheiten
betrachtet, bedeutet der U bergang zu HK keine wesentliche Veranderung, undwir schreiben fur x 2 K  statt xoK hau g einfach x, wenn moglich.
Jedes Ideal aus IK besitzt eine eindeutige Zerlegung in ein Potenzprodukt mit
ganzrationalen Exponenten von Primidealen von oK . Genauer gesagt gibt es furjedes Primideal p einen eindeutigen Homomorphismus

p : IK ! ;Z

KAPITEL 2. GRUNDLAGEN

16

so da mit der Bezeichnung PK fur die Menge der Primideale von oK fur beliebige
Ideale a 2 IK die GleichungY p a
a=
p
( )

p2PK

gilt. Bei diesem Produkt sind nur endlich viele Exponenten ungleich Null. Wir
nennen einen solchen Homomorphismus p exponentielle Bewertung von p. Aufgrund dieser Eigenschaft handelt es sich bei IK , ahnlich wie bei K  im vorigen
Abschnitt, um einen freien Z-Modul. Der Rang ist nicht endlich, denn eine Basiswird o enbar durch die Menge der Primideale PK gegeben. Wir ubernehmen den
Begri der Unabhangigkeit aus 2.4.2 auch fur Ideale.
Wie aus dem Beispiel folgt, liegen im allgemeinen nicht alle Primideale in HK |sonst ware eine eindeutige Zerlegung in prime Elemente moglich gewesen. Einstruktureller Ausdruck dieses Mangels ist die Klassengruppe
ClK = IK =HK ;ein "quantitativer\ die Klassenzahl
hK = j ClK j:
Die Klassenzahl ist stets endlich. Dies bedeutet allerdings nicht, da etwa nur
endlich viele Primideale von oK in HK fehlen. Vielmehr verteilen sich die Primideale in gewissem Sinne gleichmaig auf die Elemente von ClK , die Idealklassen,
so da im Fall hK = 1 alle Primideale in HK liegen, fur hK > 1 aber gleich
unendlich viele in HK fehlen. Auf solche Verteilungsfragen wollen wir aber nicht
eingehen. Wichtig fur uns ist dagegen die Tatsache, da die Klassengruppe vonden Idealklassen endlich vieler Primideale erzeugt wird. Um diesen Sachverhalt
genauer zu beleuchten, und auch fur die spatere Anwendung, seien ein paar Begri e im Zusammenhang mit Idealen kurz erlautert:
Ein Ideal a 2 IK heit ganz, wenn a  oK , ansonsten gebrochen. Es ist genau
dann ganz, wenn in seiner Zerlegung in Primidealpotenzen nur nicht negative
Potenzen auftreten, d. h. p(a)  0 fur alle p 2 PK . Man sagt, ein Ideal a teile
ein Ideal b, wenn es ein ganzes Ideal c gibt, so da ac = b, und schreibt a j b. Fur
zwei Ideale a; b gilt:a j b , b  a:
Bei der bereits oben verwendeten Addition von Idealen erhalt man somit den
groten gemeinsamen Teiler (ggT) und entsprechend mit dem Schnitt das kleinste
gemeinsame Vielfache (kgV) dieser Ideale.
Jedes Ideal von K , als Untergruppe der additiven Struktur von K betrachtet,
ist ein freier Z-Modul vom Rang n. Wir de nieren damit die Norm eines Idealsa von K als Absolutbetrag der Determinante der Transformationsmatrix einer
Ganzheitsbasis von K auf eine Z-Basis von a und schreiben hierfur N (a). Die
Idealnorm hat die folgenden Eigenschaften:

2.5. KLASSENGRUPPE

17(i) N (a) = (oK : a) fur a 2 IK ganz,(ii) N (xoK ) = jNK=Q (x)j fur x 2 K  ,(iii) N (ab) = N (a)N (b) fur a; b 2 IK .
Der Schnitt eines ganzen Ideals mit Z ist ein Ideal von Z. Fur ein Primideal p ist
daher p \ Z = pZ mit einer eindeutig bestimmten Primzahl p 2 Z. Man sagt, pliegt uber p. Das Ideal poK besitzt eine Zerlegung in Potenzen von verschiedenen
Primidealen p ; : : : ; pg der Form1

poK = pe1    pegg
mit e ; : : : ; eg 2  . Der Exponent ei heit der Verzweigungsindex von pi uber p
und wird mit e(pi j p) bezeichnet. Der Faktorring oK =pi ist ein endlicher Korper
der Charakteristik p und fur seine Elementanzahl gilt:
joK =pij = N (pi) = pfi mit fi 2  :Der Exponent fi heit Tragheits- oder Restklassengrad von pi und wird mitf (pi j p) bezeichnet. Ist fur ein Primideal p uber p der Verzweigungsindex e(p j p)
ungleich eins, so heit das Primideal verzweigt. Verzweigung tritt genau dannauf, wenn p die Korperdiskriminante DK teilt. Da jDK j > 1 fur Zahlkorper vom
Grad n > 1, existieren in diesem Fall stets verzweigte Primideale.
Wir kommen auf die Erzeuger der Klassengruppe zuruck. Mit gittertheoretischen
Methoden, angewendet auf das Konjugiertengitter eines beliebigen Ideals a, kanndie Existenz einer Konstanten CK 2  gezeigt werden, die nur vom Zahlkorper
K abhangt, so da a ein Element 2 a besitzt, dessen Norm beschrankt ist:jN ( )j  CK N (a):(2.2)
Dies hat wichtige Konsequenzen fur die Klassengruppe.
1

1

Z

1

Z

Z

1

1

Satz 2.5.1 Die Klassengruppe ClK ist endlich und wird von den Klassen endlich
vieler Primideale erzeugt.

Beweis: Sei aHK eine beliebige Idealklasse aus ClK . Wir wahlen ein ganzes

Ideal b der inversen Klasse a HK ; dies ist immer moglich. Zu diesem b existiertalso nach dem oben gesagten ein 2 b mit beschrankter Norm. Fur die Normdes ganzen Ideals ae = =b gilt daher
1

N (ae)  CK :O enbar gilt aeHK = aHK und wir folgern daraus, da jede Idealklasse ein ganzes
Ideal besitzt, dessen Norm durch CK beschrankt ist. Weil sich jedes ganze Ideal
als Potenzprodukt von Primidealen mit positiven Exponenten darstellen lat, die

18

KAPITEL 2. GRUNDLAGEN

Norm multiplikativ und fur Primideale eine Primzahlpotenz ungleich eins ist,mu die Klassengruppe endlich sein und von den Primidealen mit Norm kleiner
gleich CK erzeugt werden.
Fur den minimalen Wert einer solchen Idealschranke CK eines Zahlkorpers gibt
es verschiedene obere Abschatzungen, die sich aus der Signatur und der Diskriminante berechnen. Eine beruhmte obere Abschatzung ist die Minkowskischranken!  4 r2 q
MK = n n 
jDK j;
die sowohl fur spezielle Signaturen als auch asymptotisch verbessert wurde. Unter
der Voraussetzung einiger spezieller Signaturen kann man sogar bestmogliche
Abschatzungen in dem Sinne, da sie fur einen Korper dieser Signatur scharfsind, angeben. Siehe hierzu [25, 21].

Kapitel 3
Das Verfahren der
Klassengruppenberechnung
Im wesentlichen teilt sich das Verfahren der Klassengruppenberechnung in drei
Hauptarbeitsschritte auf: Zuerst mu eine Menge von Primidealen konstruiert
werden. Zweitens mussen dazu geeignete algebraische Zahlen bestimmt werden.
Drittens mu die in diesen Zahlen enthaltene Information uber die Klassengruppe
ausgewertet werden. In diesem Kapitel werden die Ideen des gesamten Verfahrens
allgemein und die Methoden des dritten Schritts im Detail besprochen. Das
nachfolgende Kapitel beschaftigt sich dann mit der Berechnung der Menge vonPrimidealen und der Berechnung der geeigneten algebraischen Zahlen.
Man startet mit einem beliebigem Zahlkorper K und einer Ganzheitsbasis von K .
Als Ergebnis erwarten wir eine Darstellung der Klassengruppe ClK als direktes
Produkt endlicher zyklischer Gruppen Z=c Z; : : :; Z=cmZ mit ci 2 Z und cijcifur 1  i < m. Dies ist nach Satz 2.1.2 stets eindeutig moglich. Ferner sindganze Ideale a ; : : : ; am und algebraische Zahlen ; : : : ; m zu bestimmen, so daaci i = i oK f
ur 1  i  m und
ClK ' < a HK >      < amHK >
(3.1)
gilt.
1

1

1

+1

1

1

3.1 Klassengruppenberechnung als S -Einheitenberechnung
Die Klassengruppe wird, wie schon im vorigen Kapitel erwahnt, von den Klassen
endlich vieler Primideale erzeugt. Wir de nieren:
De nition 3.1.1 Unter einer Faktorbasis S versteht man eine endliche Menge
von Primidealen von oK . Wir nennen eine Faktorbasis S vollstandig, wenn durch
die Klassen ihrer Ideale die ganze Klassengruppe ClK erzeugt wird.
19

KAPITEL 3. DAS VERFAHREN

20

Naturlich wird es sich bei S meist um eine vollstandige Faktorbasis handeln. Diessoll aber nicht unbedingt immer vorausgesetzt werden. Wie man eine vollstandige
Faktorbasis erhalt, wird im nachsten Kapitel behandelt.
Sei S eine beliebige Faktorbasis. Die Ableitung der Klassengruppenstruktur geschieht mittels folgender allgemeiner U berlegungen. Die von den Idealen aus S
erzeugte Untergruppe IKS von IK ist frei vom Rang s = jS j. Durch die Inklusion
IKS  IK und die Restklassenabbildung IK ! ClK wird ein Homomorphismus
IKS ! ClK induziert, dessen Kern wir mit HKS bezeichnen. HKS ist eine Untergruppe von HK und hat endlichen Index in IKS , denn die Klassengruppe ist
endlich. Folglich handelt es sich bei HKS ebenfalls um eine freie Gruppe vom Rangs. Das Urbild von HKS unter x 7! xoK bezeichnen wir mit UKS . Man sieht, da
UK eine Untergruppe von UKS ist.

De nition 3.1.2 Die Elemente von UKS werden S -Einheiten genannt. Eine S -Einheit, die keine Einheit ist, heie S -Relation oder kurz auch nur Relation. Die
Faktorgruppe IKS =HKS nennen wir S -Klassengruppe ClKS von K . Ihre Ordnung ist
die S -Klassenzahl hSK .

Wir merken an, da die De nition der S -Klassengruppe kein Standard ist und
an anderer Stelle mit anderer Bedeutung verwendet werden kann.
O enbar ist ClKS eine Untergruppe von ClK , und im Falle einer vollstandigen
Faktorbasis gilt
ClKS ' ClK :Wir nahern uns IKS , HKS und der gesuchten Darstellung von ClKS mit Hilfe derfolgenden Abbildung, wobei S = fp ; : : : ; psg:
110
p1 (a)B .. CCS : IK ! s; a 7 ! B@ . A:
ps (a)Diese Abbildung ist ganz analog dem bereits de nierten L ein Homomorphismus
der multiplikativen Struktur von IK in die additive von s. Weil die Primideale
aus S eine Basis von IKS bilden, gilt o enbar
Z

Z

IKS ' sZunter S , und unabhangige Ideale aus IKS werden auf R -linear unabhangige Vektoren abgebildet. Wir mussen zur Ermittlung von ClKS noch HKS , sprich eine
Basis von HKS , bestimmen. Dies geschieht mit der Suche nach S -Relationen, die
im nachsten Kapitel genau beschrieben wird. Ziel ist es, durch die gefundenen
Relationen ganz HKS zu erzeugen. Seien ; : : : ; m S -Relationen. Das Erzeugnis
H der i in HKS kann nun, wie in Abschnitt 2.1 beschrieben, mit der Hermite
13.2. S -EINHEITENGITTER

21

Normalform der Matrix (S ( i)) im 2 Zsm berechnet werden. Hat diese Hermite Normalform den Rang s, so ist ihre Determinante bereits ein Vielfaches
der S -Klassenzahl (die m s hinteren Nullspalten werden abgeschnitten). Wenn
H = HKS berechnen wir die Smith Normalform dieser Matrix, um die gesuchte
Darstellung von ClKS zu erhalten. Wann jedoch gilt H = HKS ? Hierzu gibt es
zwei verschiedene Methoden, auf die im Abschnitt 3.3 eingegangen wird. Fur die
Methode, die wir verwenden werden, mu die Vollstandigkeit von S vorausgesetzt
werden.
Wir wollen die S -Einheitengruppe UKS etwas genauer betrachten. Wahlt maneine Basis oK ; : : : ; soK von HKS , so sind die i unabhangige Nichteinheiten in
UKS . Jedes 2 UKS lat sich o enbar bis auf eine Einheit durch die i eindeutig
darstellen. Daraus ergibt sich die Isomorphie
UKS ' HKS  UK
(3.2)
und mit dem Einheitensatz folgt:
Satz 3.1.3 Die S -Einheitengruppe UKS wird von s + r + 1 algebraischen Zahlen
erzeugt und ist modulo Torsionseinheiten sogar frei vom Rang s + r.
Wir haben m S -Relationen ; : : : ; m vorliegen. Aufgrund der genannten Rangzahlen konnen davon hochstens s Relationen modulo Einheiten unabhangig sein.
Fur m > s lassen sich also S -Einheiten kombinieren, die oK in HKS entsprechen,folglich Einheiten sind. Bezeichnen wir mit U S das Erzeugnis der gefundenen
Relationen in UKS , so ist die Einheitengruppe, die wir daraus ableiten konnen,
gleich U = U S \ UK . Zur Bestimmung von U und U S verwenden wir das S Einheitengitter aus dem nachsten Abschnitt. Wie bei den Hauptidealen HKS
stellt sich dann auch hier bei den Einheiten die Frage, wann U = UK ist. In Abschnitt 3.3 wird ein Abbruchkriterium angegeben, welches gleichzeitig H = HKS
und U = UK unter der Voraussetzung einer vollstandigen Faktorbasis pruft.
Die Berechnung der Klassengruppe mit S -Relationen liefert also auch Einheiten.
Wegen der Isomorphie 3.2 lat sich die simultane Berechnung von HKS und UK
zusammenfassen als Berechnung der S -Einheiten UKS von K fur eine vollstandige
Faktorbasis S . Allerdings konnen wir S nicht ganz beliebig wahlen. Aufgrundder Methoden, mit denen wir S -Relationen bestimmen werden, mu S aus Primidealen mit kleinen Normen bestehen. Dazu kommen wir spater. Es sei nochangemerkt, da ein Erzeuger von TUK leicht im voraus oder extra berechnet
werden kann | siehe [16] |, so da wir uns nur um unabhangige S -Einheiten
zu kummern brauchen.
1

1

1

3.2

S -Einheitengitter

Im vorigen Abschnitt wurde gezeigt, da die S -Einheitengruppe modulo Torsionseinheiten frei vom Rang s + r ist. In diesem Abschnitt wollen wir ein zu

KAPITEL 3. DAS VERFAHREN

22

UKS =TUK isomorphes vollstandiges Gitter im s r de nieren. Durch Kombination
von Methoden der Abschnitte 2.1 und 2.3 und mit Hilfe dieses Gitters konnen wirdann eine Basis des Erzeugnisses endlich vieler S -Einheiten in UKS =TUK berechnen | und zwar bestehend aus unabhangigen S -Relationen und unabhangigen
Einheiten. Fur die Faktorbasis S mussen in diesem Abschnitt keine besonderen
Eigenschaften vorausgesetzt werden.
Es wurde bereits der Homomorphismus L : K  ! r de niert, welcher unabhangige Einheiten auf -linear unabhangige Vektoren abbildet. Wir wollen
jedoch auch S -Einheiten vernunftig abbilden, die keine Einheiten sind. Hierfur
ist L alleine nicht geeignet. Fur solche S -Relationen wurde oben S : IK ! s
mit analogen Eigenschaften wie L de niert. Einheiten werden aber hierdurch auf
den Nullvektor abgebildet. Den passenden Homomorphismus erhalten wir durch
Kombination von S und L:
!

(
x
oK )
S
S
S
s
r
K : UK !  ; x 7 !
L(x) :
R

+

R

R

Z

Z

R

Bei SK handelt es sich um einen Homomorphismus der multiplikativen Struktur
von UKS in die additive Struktur von Zs  R r mit Kern TUK . Letzteres gilt, da die
Elemente des Kerns Einheiten sein mussen, deren Konjugiertenbetrage samtlich
1 sind, und dies erfullen genau die Torsionseinheiten. Also besteht die Isomorphie

UKS =TUK ' SK (UKS ):De nition und Satz 3.2.1 SK (UKS ) ist ein vollstandiges Gitter im s r , dasR+

S -Einheitengitter von K genannt wird. Die Gitterdeterminante von SK (UKS ) ist
hSK RK .

Beweis: Fur die erste Aussage mu gezeigt werden, da in UKS unabhangige

Elemente durch SK in R -linear unabhangige Vektoren uberfuhrt werden. Da
UKS =TUK frei vom Rang s + r ist, handelt es sich dann beim Bild von UKS unterSK um ein vollstandiges Gitter im R s r .
Seien ; : : : ; m 2 UKS zunachst beliebige S -Einheiten und bezeichne, analog
dem vorigen Abschnitt, mit U S das Erzeugnis der i in UKS , mit H das Bild
von U S unter x 7! xoK und mit U die erzeugte Einheitengruppe U S \ UK . Wir
betrachten die Matrix B 2 R s r m , die von den Spalten SK ( ); : : : ; SK ( m)gebildet wird und nennen sie die Relationsmatrix von ; : : : ; m. Der obere Teilvon B ist aus Zsm. Es gibt eine unimodulare Matrix T 2 Zmm, so da dieser
Teil durch Multiplikation mit T von rechts in eine untere Hermite Normalform Huberfuhrt wird, deren Rang mit m bezeichnet sei. Die ersten m Spalten von H
sind R -linear unabhangig, die anderen Spalten sind Nullspalten. Dies vor Augen
wenden wir T von rechts auf B an, erhalten die transformierte Relationsmatrix
C und erkennen, da die ersten m Spalten von C o ensichtlich ebenfalls linear
+

1

( + )

1

1

0

0

0

3.2. S -EINHEITENGITTER

23

unabhangig sind. Die restlichen Spalten korrespondieren aufgrund der Nullen im
S
Z-Anteil mit Einheiten in UK . Die transformierte Relationsmatrix hat also die
Form
!
0
H
C=  C2

mit H 2 Zsm0 in Hermite Normalform mit Rang m und C 2 R rm1 , wobei
m = m m . Wir wenden nun die unimodulare Transformation T | als Potenzprodukt | auf die i an und bezeichnen das Ergebnis mit e ; : : : ; e m. Die
unimodulare Transformation schadet nichts; die e i erzeugen dieselbe Gruppe wie
die i , namlich U S . Wir erkennen ferner, da C die Spalten SK ( e ); : : : ; SK ( e m)besitzt. Bei den m letzten e i handelt es sich demnach um Einheiten. Sie erzeugen U . Die m ersten der e i sind S -Relationen. Ihr Erzeugnis in HKS ist
H.
Unter der Annahme, da die i unabhangig sind, wollen wir jetzt zeigen, da
der Rang von B bzw. C gleich m ist. Wir wissen bereits, da die ersten m
Spalten R-linear unabhangig sind. Die Eigenschaft der Abbildung L, unabhangige
Einheiten auf R -linear unabhangige Vektoren zu werfen, ergibt die zur Frage
stehende lineare Unabhangigkeit der restlichen Spalten von C . Die letzten mder e i sind namlich unabhangige Einheiten. Hieraus folgt unmittelbar, da auch
B vollen Rang uber R besitzt, und die erste Aussage ist bewiesen.
Aufgrund der Kastchengestalt der transformierten Relationsmatrix C folgt fur
s + r unabhangige S -Einheiten i, da
0

1

2

0

1

1

1

0

0

1

j det C j = j det H jj det C j = (IKS : H ) Reg(U ):2

Aus dieser Gleichung folgt die zweite Aussage.

Das im Beweis Gesagte lehrt, da wir durch die Bildung einer Hermite Normalform des oberen Teils der Relationsmatrix bzw. durch Anwenden einer unimodularen Transformation S -Relationen und Einheiten trennen konnen. Genauer
gesagt erhalt man eine Basis von H und ein Erzeugendensystem fur U . Der Index (IKS : H ) | falls der Rang von H bzw. H gleich s ist | ist das Produkt
der Diagonalelemente von H . In dieser Matrix sammelt sich die Informationuber die Klassengruppe. Insbesondere ist die Determinante bzw. der Index ein
ganzzahliges Vielfaches der S -Klassenzahl.
Wir mussen allerdings eine Basis von U kennen, um den Rang und bei Ranggleich r auch den Regulator von U bestimmen zu konnen. Der Regulator von
U ist in diesem Fall ein ganzzahliges Vielfaches von RK . Sind also beliebige
Einheiten " ; : : : ; "m gegeben, so konnen wir sukzessive fur i = 1; : : : ; m Basender Erzeugnisse der " ; : : : ; "i mit Hilfe von SK bzw. L ausrechnen. Zur i-ten Basisnehmen wir "i dazu und verwenden den MLLL-Algorithmus, um die (i + 1)-te
Basis zu bestimmen. Dieses Vorgehen wurde schon am Ende des Abschnitts 2.3
erlautert.
1

1

+1

KAPITEL 3. DAS VERFAHREN

24

Mit Hilfe der beschriebenen Methoden kann man zu gegebenen S -Einheiten das
von ihnen erzeugte Teilgitter des S -Einheitengitters bestimmen.

De nition 3.2.2 Die durch Weglassen der Nullspalten aus der unteren Hermite

Normalform der Matrix (S ( i))1im entstehende Matrix H nennen wir die
Klassengruppenmatrix der i . Eine Matrix B , fur die( ; : : : ; m) B = (p ; : : : ; ps) H
1

1

ist, heit Relationsbasismatrix der i . Eine Matrix U , fur die ( 1 ; : : : ; m ) Ueine Basis von U ist, wird Einheitenmatrix der i genannt.

Algorithmus 3.2.3 (Berechnung des S -Einheitengitters)
Eingabe: S -Einheiten

1; : : : ; m.

Ausgabe: Die Klassengruppenmatrix H , eine Relationsbasismatrix B und eine
Einheitenmatrix U der 1 ; : : : ; m .
1. (Initialisierung) Setze L() Matrix mit r Zeilen und 0 Spalten, H()
Matrix mit s Zeilen und 0 Spalten, B() Matrix mit 0 Zeilen und
Spalten, U() Matrix mit 0 Zeilen und Spalten und schlielich i 1.
2. (Fuge i hinzu) Sei k die Spaltenzahl von! U . Erweitere L (L! j L( i)),B 0 2 Zii und U
U 2 Zik.
H (H j S ( i)), B
0 1
03. (Hermite Reduktion) Bilde die untere Hermite Normalform von H mittels
Transformationsmatrix T : H
H T . Setze B B T .
4. (Einheit gefunden?) Wenn die letzte Spalte von H eine Nullspalte ist,
wurde eine Einheit gefunden. Ist dies nicht der Fall, mache bei Schritt 7
weiter. Ansonsten entferne diese Spalte von H . Entferne auch die letzte
Spalte von B und nenne sie u.
5. (Neue Einheit ist Torsionsenheit?) Wenn L u der Nullvektor ist, wurdeeine Torsionseinheit gefunden. Gehe zu Schritt 7.
6. (MLLL-Reduktion) Setze U(U j u). Bestimme mit Hilfe des MLLLAlgorithmus angewendet auf L U eine Transformationsmatrix T , so da
die Spalten von L U T eine Basis des von den Spalten von L U aufgespannten Gitters sind. Setze U
U T.
7. (Nachste S -Einheit) Wenn i = m Ausgabe von H ; B ; U und terminiere.
Setze sonst i i + 1 und gehe zu Schritt 2.

3.3. ABBRUCHBEDINGUNGEN

25

Wir wollen einige Bermerkungen zu diesem Algorithmus machen:
Die Nullen in Schritt 2 stehen fur Matrizen variabler Zeilen- und Spaltenzahl mit
lauter Nulleintragen. Fur i = 1 beispielsweise wird B = (1) gesetzt.
Die am Ende der MLLL-Reduktion neuberechnete Einheitenmatrix U sollte bei
zu groen Eintragen LLL-reduziert werden.
Der Test auf Torsionseinheit und die MLLL-Reduktion werden mit reeller Arithmetik ausgefuhrt. Die dabei verwendete Prazision mu den ; : : : ; m und insbesondere auch der Groe der Koezienten von U und u angepat werden.
Gegebenenfalls ist L ganz neu zu berechnen. Im Torsionstest prufen wir, ob die
Eintrage von L u betraglich kleiner sind als einem gewissen " > 0, welches vonder Prazision abhangt.
Das ausschlieliche Arbeiten mit den Transformationmatrizen B und U ist essentiell. Die Eintrage von B und U sind namlich aufgrund 3.2.2 als Exponenten
von Potenzprodukten der i zu interpretieren. Die S -Relationen und Einheiten,
die man daraus erhalt, sind in der Regel keineswegs mehr gut konditioniert. Die
direkte Berechnung von L u uber L( ) mit = ( ; : : : ; m ) u ist daher sehr
ungenau und erfordert eine wesentlich hohere Prazision. Allerdings wird die Berechnung dieser Potenzprodukte bereits bei bescheidenen Eintragen in B und U
zeitintensiv oder ist gar nicht mehr moglich. Fur etwas kompliziertere Beispielewerden die Eintrage von B und U aber meistens ziemlich gro. Damit konnen
wir auf direktem Wege leider auch keinen algebraischen Test auf Torsioneinheit
durchfuhren.
Wir werden Algorithmus 3.2.3 nicht ganz in der hier dargestellten Form einsetzen.
Vielmehr entstehen unsere S -Einheiten ; : : : ; m der Reihe nach, und mit jeder
neuen S -Einheit rufen wir Algrithmus 3.2.3 unter Berucksichtigung der schon
eingespeisten S -Einheiten auf. Auerdem kennen wir schon S ( i) und konnen
dies an Algorithmus 3.2.3 ubergeben.
Praktische Versuche zeigen, da man Algorithmus 3.2.3 nach Moglichkeit nur fur
Faktorbasen mit nicht viel mehr als 200 Idealen anwenden sollte. Schlielich ist
sukzessive die Hermite Normalform einer s  m-Matrix zu berechnen, wobei m
mitunter das doppelte oder dreifache von s betragt. Auerdem mussen m  mTransformationsmatrizen gehalten werden, deren Eintrage gro werden konnen.
Die Zeit, die von Algorithmus 3.2.3 bei solchen groen Faktorbasen benotigt wird,
steht gewohlich in keinem sinnvollen Verhaltnis zur Zeit, die die Berechnung derFaktorbasis und der Relationen erfordert.
11

1

3.3 Abbruchbedingungen
Mit Algorithmus 3.2.3 kann man das von einigen S -Einheiten erzeugte Teilgitter des S -Einheitengitters bestimmen. Wir benotigen nun ein Kriterium, mit

KAPITEL 3. DAS VERFAHREN

26

dem entschieden werden kann, wann das volle S -Einheitengitter bestimmt wurde.
Hierzu gibt es zwei Methoden.

p-ter Wurzeltest
Wir bezeichnen mit H wieder das Erzeugnis einiger S -Einheiten in HKS und setzen voraus, da H in HKS endlichen Index besitzt. Die Idee der ersten Methodebasiert auf der Tatsache, da zwischen H und IKS nur endlich viele Zwischengruppen liegen konnen, die mit IKS ebenfalls frei sind. Wir bestimmen fur jede

dieser Gruppen eine Basis. Eine solche Basis besteht aus Idealen, von denenzunachst unbekannt ist, ob sie aus HKS sind. Dies entscheiden wir dann mit Hilfe
eines Hauptidealtests. Stellt sich heraus, da alle Basisideale Hauptideale sind,so haben wir eine Obergruppe von H gefunden, die ganz in HKS enthalten ist.
Allerdings macht man sich mit dieser Vorgehensweise zu viel Arbeit. Insbesondere testet man naturlich nicht alle Zwischengruppen ab, sondern nur die jeweils
nachstgroeren von H . Auch kann man den Hauptidealtest durch Ausnutzung
der bereits berechneten Informationen wesentlich gunstiger ausfuhren als fur beliebig gegebene Ideale. Dazu mu aber ein p-maximales Einheitensystem aus r
unabhangigen Einheiten bekannt sein. Wir nennen diese Methode den "p-ten
Wurzeltest\. Es handelt sich hierbei nicht nur um ein reines Testkriterium, sondern liefert im Fall, da H noch nicht maximal ist, ein groeres H zuruck. Die
genaue Darstellung und Durchfuhrung der beschriebenen Ideen lat sich in in[16, 15, 21] nachlesen.

Eulerprodukt

Wir kommen zur zweiten Methode, der Methode des "Eulerprodukts\, auf die
wir uns in dieser Arbeit ausschlielich stutzen wollen. Fur diese Methode mu
die Vollstandigkeit der Faktorbasis vorausgesetzt werden, denn wir benotigen
ganzzahlige Vielfache von hK und RK bzw. eine Untergruppe endlichen Index
von UKS =TUK . Diese Vielfache werden bei Eingabe geeigneter S -Relationen vonAlgorithmus 3.2.3 geliefert. Die zugrundeliegende Idee ist nun einfach. Wirkonnen namlich das Produkt hK RK auf analytischem Weg approximieren. Durch
Vergleich mit dem von uns berechneten Vielfachen dieses Produkts lat sich ganz
einfach feststellen, ob wir mit der berechneten Untergruppe von UKS =TUK schonganz UKS =TUK erreicht haben oder nicht. Die Approximation von hK RK beruht
auf folgenden De nitionen und Satzen:

De nition und Satz 3.3.1 Wir de nieren die Dedekindsche Zetafunktion Keines Zahlkorpers K fur Re(s) > 1 durchK (s) =X 1
s;a N (a)3.3. ABBRUCHBEDINGUNGEN

27

wobei sich die Summe uber alle ganzen Ideale erstreckt. Die Reihe K (s) ist
absolut und gleichmaig konvergent im Bereich Re(s)  1 +  fur jedes  > 0. Im
Bereich Re(s) > 1 besitzt K die DarstellungYK (s) = 1 N1(p) s ;p
wobei sich das Produkt uber alle Primideale von K erstreckt. Die Dedekindsche
Zetafunktion K hat eine analytische Fortsetzung auf C nf1g.

Satz 3.3.2 (Analytische Klassenzahlformel) Wir bezeichnen wie ublich mit(r ; r ) die Signatur, mit DK die Diskriminante, mit hK und RK Klassenzahl und
Regulator und mit wK die Anzahl der Torsionseinheiten von K . Die Dedekindsche
Zetafunktion K hat in s = 1 einen einfachen Pol mit dem Residuum
2r1 (2q)r2 hK RK
:
lim
(
s
1)

(
s
)
=
K
s!
wK jDK j
1

2

1

Beweis: Zum Beweis dieser Satze siehe [13], Kapitel VIII Paragraph 5.



Satz 3.3.3 Fur das Residuum der Zetafunktion K giltlim (s 1)K (s) =s!
1YQ (1(1 pN (p) ) ) ;
p pjp
1

1

wobei p der Reihe nach alle Primzahlen durchlauft.

Beweis: Zum Beweis siehe [23]. Ein wesentliches Argument wird aber auch imnachsten Abschnitt gezeigt.
Dieser Satz motiviert die folgende De nition:

De nition 3.3.4 Unter dem Eulerprodukt EPK von K verstehen wir das Produkt auf der rechten Seite der Gleichung in Satz 3.3.3. Fur x 2  de nieren
wir EPK (x) durchZ

EPK (x) =Y0Q (1(1 pN (p) ) ) :px p j p
1

1

Die Berechnung von hK RK erfolgt nun durch Approximation des Eulerprodukts
und Umstellen der analytischen Klassenzahlformel. Es sei noch bemerkt, da es
in der Literatur "das\ Eulerprodukt nicht gibt. Samtliche Darstellungen von Zetafunktionen als Produkt uber Primideale werden ublicherweise als Eulerprodukt
bezeichnet.
Von groem Interesse ist jetzt naturlich die Konvergenzgeschwindigkeit unseres
Eulerprodukts. Hierzu werden im nachsten Abschnitt Betrachtungen angestellt.

KAPITEL 3. DAS VERFAHREN

28

Eine sinnvolle Approximation von hK RK ist ubrigens nur deshalb moglich, weil
die Menge der von uns berechneten Kandidaten fur hK RK eine Diskretheitsbedingung erfullt. Wir betrachten M = f log(k hK RK ) j k 2 Z g. Die Approximation
von hK RK bzw. log(hK RK ) soll so genau sein, da dadurch log(hK RK ) eindeutig als Minimum von M charakterisiert wird. Weil der Abstand des Minimums
zum nachstgroeren Element log(2) betragt, genugt es, wenn die Approximation im Intervall [ log(2) + log(hK RK ); log(2) + log(hK RK ) [ liegt. Der Wert
log(hK RK ) wird dann eindeutig durch die Eigenschaft charakterisiert, von derApproximation einen Abstand kleiner gleich log(2) zu haben. Daraus ergibt
sich das folgende Lemma:
1

1
2

1
2

1
2

Lemma 3.3.5 Fur ein geeignetes x 2  geltepp1  EPEPK (x) < 2
2
Z

1

K


und sei k 2 Z1. Dann besteht die Aquivalenz:pk = 1 , k EPK  2 EPK (x):Die ausreichende Approximation des Eulerprodukts stellt in der Praxis kein Problem dar. Fur die Erzeugung der Faktorbasis gibt man sich namlich ublicherweiseeine relativ kleine Schranke vor und berechnet alle Primideale zu Primzahlen unterhalb dieser Schranke. In der Regel ist es vollkommen genugend, diese Primideale zur Berechnung des Eulerprodukts heranzuziehen. Nur bei Korpern mit
sehr kleiner Diskriminante kann es notig sein, weitere Primideale hinzuzunehmen. Bei samtlichen bisher behandelten Korpern reicht es aus, das Eulerprodukt
auf diese Weise unter Verwendung mindestens der Primideale uber den ersten
150 Primzahlen zu berechnen. Anstelle von Lemma 3.3.5 wurde hierbei sogar
die Bedingung 0:9  k EPK =EPK (x)  1:1 getestet. Praktische Untersuchungenzeigen, da EPK (x) fur wachsendes x zunachst ziemlich schnell zu konvergieren
scheint, dann jedoch in einem gewissen kleinen Bereich pendelt, auch wenn x
schon verhaltnismaig gro geworden ist. Aus diesem Grund ist es unangenehm,
das Eulerprodukt bei Kenntnis des Regulators zur Bestimmung von hK zu benutzen. Hierfur ist namlich eine wesentlich hohere Approximationsgenauigkeitvonnoten.

3.4 Konvergenzverhalten des Eulerprodukts
In diesem Abschnitt soll uber das Konvergenzverhalten des Eulerprodukts berichtet werden, und zwar mit und ohne Annahme der verallgemeinerten Riemannschen Vermutung (GRH). Die Darstellung lehnt sich an [4] an. Wir gehen wie
folgt vor: Zuerst wird das Restglied des Eulerprodukts nach Logarithmierung3.4. KONVERGENZVERHALTEN DES EULERPRODUKTS

29

als Summe dreier Reihen dargestellt. Die Konvergenz zweier dieser Reihen ist
absolut und entsprechend unproblematisch. Die dritte Reihe ist nicht absolut
konvergent. Ihr Konvergenzverhalten entspricht einer Aussage uber die asymptotische Verteilung von Primidealen und wir bestimmen es mit zwei "e ektiven\
Versionen des Primidealsatzes.

Geeignete Darstellung des Eulerprodukts

Wir setzen E (p) = (1 p ) Qp j p(1 N (p) ) und nennen E (p) den Eulerfaktor
von p. Wir de nieren das Restglied des Eulerprodukts fur x  2 durchY
T (x) = E (p):
1

1

1

p>x

Die Aufgabe besteht nun darin, zu vorgegebenem " > 0 ein x zu nden, sop da
j log(T (x)) j < " ist. Laut Lemma 3.3.5 interessiert uns besonders " = log( 2).
Wir betrachten zunachstQdie Eulerfaktoren etwas genauer und wollenPdann T (x)logarithmieren. Sei p = gi pei i und fi = f (pi j p). Wir setzen fg = i fi . Dannlat sich E (p) schreiben alsfg
E (p) = Qp g (p(pfi 1)1) :(3.3)
i
Wir fassen diesen Ausdruck fur den Moment als eine rationale Funktion der
Variablen p auf. Augenscheinlich ist das Nennerpolynom durch p 1 teilbar.
Dividieren wir auch noch durch pfg , so erhalten wir
=1

1

=1

1

!
a
a
( p)
n ( p)E ( p) = 1 + p + : : : + pn;
(3.4)
wobei die ai(p) 2 eindeutig durch die fi und somit durch das Zerlegungsverhalten von p (als Primzahl)
bestimmt werden. Hierbei sind ai (p) = 0 fur
fg  i  n 1. Wegen Pi fi  n gibt es nur endlich viele Konstellationen (f ; : : : ; fg ) fur verschiedene Primzahlen p und somit auch nur endlich viele(a (p); : : : ; an (p)). Aus Grunden, die etwas spater klar werden, interessieren
wir uns speziell fur den Wert von a (p). Sei g die Anzahl der Primideale mit
Grad 1 uber p. Ein scharfer Blick auf das Nennerpolynom in (3.3) zeigt, da
es die Spur g besitzt, denn schlielich ist die Spur das Negative der Summe
der Nullstellen eines Polynoms. Da nach der Division des Nennerpolynoms durch
p 1 einmal eine Eins als Nullstelle verloren geht, folgt a (p) = 1 g .
Wir wollen jetzt T (x) logarithmieren. Fur n  2 und p  2 ist j E (p) 1 j < 1.
Fur x  2 erhalten wir also
!
X
a
a
( p)
n ( p);
log(T (x)) = log 1 +p + : : : + pn
p>x
1

1

1

1

Z

1

1

1

1

1

1

1

1

1

1

1

1

KAPITEL 3. DAS VERFAHREN

30

und mit Hilfe der Reihenentwicklung fur den Logarithmus ergibt sich!j
1 a ( p)XXan (p) ( 1)jlog(T (x)) =p + : : : + pnjp>x j
1 ( 1)jX a (p) X 1 nX ak (p) X X
=
+
+
k
jpj
p>x p
p>x p k p
p>x j
+1

1

1

1

=1

1

1

2

=2

2

nX1 a (p) !j
k
k 1 :
p
k=1

+1

=2

In der letzten Gleichung wurde der Term fur j = 1 aus der Reihe daruber extra
geschrieben und so aufgeteilt, da die Bruche, in denen p als einfache Potenz im
Nenner auftritt, die erste Reihe bilden. In der zweiten Reihe sind die ubrigenBruche zusammengefat und in der dritten Reihe treten die restlichen Terme fur
j > 1 auf. Diese Gleichung ist veri ziert, wenn die Konvergenz der drei Reihen
nachgewiesen ist. Wir betrachten jetzt die zweite und dritte Reihe. Diese sindnamlich absolut konvergent | wie gleich gezeigt wird |, da p mindestens im
Quadrat in den Nennern auftritt. Aufgrund der endlich vielen Moglichkeiten fur(a (p); : : : ; an (p)) gibt es nur von n abhangige Konstanten c und c , so da
1

1

1

nX1
k=2

ak (p)p k+2  c1 und

nX1
k=1

a k ( p) p k

+1

2

c

2

fur jedes p > x gilt. Konkret lat sich jak (p)j beispielsweise durch 2n nach oben
abschatzen und somit ergibt sich 2n als moglicher Wert fur c und c . Wir
fordern, da ab jetzt x  2c gilt. Dann
+1

1

2

2

X 1 nX ak (p) X c c p xkp>x p k p
p>x
1

2

1

2

=2

1

2

und

1 c !j1 1 nX ak (p) j
XX
XX

j
k
p
p>x j
p>x j jp k p
!
Xc
2c
1


x;
p>x p 1 c =p
wobei die Abschatzung P 1=p < 1=x zu beachten ist, die leicht durch Inte1

=2

=1

2

1

=2

2
2

2
2

2

p>x

2

2

grieren bewiesen werden kann.

Verwendung des Primidealsatzes

Es bleibt wie angekundigt die Konvergenz der ReiheXp>xa (p)=p1(3.5)

3.4. KONVERGENZVERHALTEN DES EULERPRODUKTS

31zu
Eine Abschatzung wie oben ist fur diese Reihe nicht moglich, denn
P zeigen.
p>x 1=p ist divergent. Dies bedeutet, da besondere Eigenschaften der a (p)ausgenutzt werden mussen. Daher de nieren wir
1

A ( t) =Xpta ( p)
1

und werden gleich das Verhalten von A(t) fur wachsendes t untersuchen. Die
Verbindung zu (3.5) stellen wir mit Hilfe der folgenden Stieltjes-Integrale her,wobei limt!1 A(t)=t = 0 vorausgesetzt sei:Z 1 A(t)X a ( p) Z 1 1=
dA(t) = A(x) +
dt:
(3.6)
x
x t
x t
p>x p
1

2

Durch Einsetzen oberer Abschatzungen fur jA(t)j konnen wir feststellen, ob die
rechte Seite uberhaupt konvergiert. Ist dies der Fall, so konvergiert auch die linke
Seite und man erhalt auerdem die gesuchten Abschatzungen fur (3.5).
Wir bezeichnen fur einen beliebigen Zahlkorper K die Anzahl der Primideale von
K mit Norm kleiner gleich einer positiven Zahl t mit K (t) und die Anzahl derPrimideale vom Grad eins unter den letzteren mit K (t). Weil a (p) = 1 g ,wenn g gleich der Anzahl der Primideale uber p in K vom Grad eins ist, kannman A(t) schreiben als
A(t) = Q (t) K (t)und daher
jA(t)j  jQ (t) K (t)j + jK (t) K (t)j:
(3.7)
(1)

1

1

1

(1)

(1)

Satz 3.4.1 (Primidealsatz) Sei K ein algebraischer Zahlkorper vom Grad n
mit Diskriminante DK . Wir de nieren

Z t duli(t) =:
log uFur beliebiges " > 0 gibt es eine von K unabhangige aber von " abhangige Konstante c = c(") > 0, so da2K (t) = li(t) + O(Dt log(t) exp( cn log(t) 21 =D))2

mit D = n3 c njDK j". Die Konstante des O-Terms hangt nicht von K ab. Setzen
wir die verallgemeinerte Riemannsche Vermutung fur K voraus, so gilt fur t  2:pjK (t) li(t)j  t log(t) (log(jDK j)c (t) + nc (t))
34

mit c3 (t) = 1=( log(t)) + 5:3= log(t)2 und c4 (t) = 1=(2 ) + 2= log(t).

KAPITEL 3. DAS VERFAHREN

32

Beweis: Die erste Aussage ist ein Spezialfall des in [6] bewiesenen Satzes. Die
zweite Aussage ist ein Spezialfall von Satz 3 aus [14].
Die Fehlerabschatzung von K (t) ohne Voraussetzung der GRH ist nicht die
bestmogliche. Wir verwenden sie hier, weil die Abhangigkeit der Konstanten
von n und DK angegeben wird.
Lemma 3.4.2 Fur t  2 gilt:pjK (t) K (t)j  n2 Q ( t):Auerdem ist
p p
lim

Q ( t)=( t log(t)) = 0
t!1
und
p
t log(t)=(t log(t) exp( c log(t) 21 )) = 0
lim
t!1
fur c  0.
er eins eine Norm kleiner gleich t, so liegt
Beweis: Besitzt p vom Grad grop
p uber einer Primzahl p mit p  t. U ber p konnen aber nur maximal n=2
solcher Primideale liegen. Fur die erste Limes-Aussage ist zu pbeachten,
p dali(t) = t= log(t) + O(t= log(t) ), siehe [12] S. 372. Also strebt li( t)=( t log(t))
fur wachsendes t gegen Null. Fur die
p zweite Limesaussage ist zu beachten, da
exp(c log(t) 12 ) schwacher wachst als t = exp(log(t)=2).

Das Lemma besagt, da die Primideale vom Grad groer eins "vernachlassigbar\
sind. Ihre Anzahl wachst schwacher als der Fehlerterm von K (t) mit GRH undohne GRH.
(1)

2

2

Abschatzung mit GRH

Wir konnen (3.7) unter Verwendung des Primidealsatzes, des Lemmas und unter
Annahme der GRH fur Q und K folgendermaen nach oben abschatzen:pjA(t)j  t log(t) (log(jDK j)c (t) + (n + 1)c (t)) +ppn li( t) + 12 4 t log(t)c (t)np t log(t) 2 + log(jDK j)c (t) + (n + 1)c (t) ;wobei die letzte Ungleichung fur t  20 gilt. Wir kurzen den geklammerten Ausdruck dieser UngleichungR mit
p C (t) ab. O ensichtlich ist Cp(t) monoton fallend.
Beachtet man noch, da t log(t)=t dt = (4 + 2 log(t))= t, so folgt aus (3.6)
fur x  20:
X a ( p)(3.8)
C(x) 4 + 3plog(x) :
x
p>x p
3

4

4

3

2

1

4

3.4. KONVERGENZVERHALTEN DES EULERPRODUKTS
und schlielich

33x) + c + 2c :j log(T (x))j  C (x) 4 + 3plog(
x
x
1

2
2

(3.9)

Mit dieser Ungleichung kann man die erforderliche Genauigkeit, bis zu der das
Eulerprodukt approximiert werden mu,p bestimmen. Die rechte Seite mu dazu,
wie bereits erwahnt, kleiner als log( 2) werden, was man fur ausreichend groes
x erreichen kann. Wir wollen jedoch auch wissen, wie sich die minimalen Wertefur x bei festem Grad aber wachsender Diskriminante
entwickeln. Wir setzenpdazu die rechte Seite aus (3.9) gleich log( 2) und bemerken, da diese Seite fur
x  2 streng monoton fallend in x ist. Hierdurch wird x als Funktion von DK
implizit de niert, also x = x(DK ). Wenn jDK j ! 1, so gilt auch x(DK ) ! 1.
Fur g; h : R ! R schreiben wir g(t)  h(t), wenn limt!1 g(t)=h(t) = 1 ist. Mitdieser Notation und unter Beachtung, da x = x(DK ) und n fest ist, gilt o enbar!

!

log(jDK j) 1 + 5:3 + n + 1 + n + 2(n + 1) 4 + 3plog(x)  log(p2);log(x)  log(x)22 log(x)xalsop3 log(pxjDK j)  log( 2);1

und daher

36
log(jDK j)  x:
( log(2))
Der Vorfaktor betragt ungefahr 7:6. Fur geeignet groe Diskriminanten brauchen wir daher das Eulerprodukt nur bis beispielsweise 8 log(jDK j) zu approximieren. Dieses asymptotisch gute Ergebnis ist leider im konkreten Fall nichtbesonders gut. In c (x) und c (x) treten namlich Terme der Form 1= log(x)auf und diese Terme konvergieren extrem langsam: Wenn x als ein konstantes Vielfaches des Quadrats des Logarithmus von jDK j interpretiert wird, giltlog(x)  2 log(log(jDK j)). Fur n = 4 und DK = 10 beispielsweise mu x ungefahr 100 log(jDK j) betragen, damit die Approximationsbedingung erfullt ist.
Interessant ist daher ein Ergebnis von Bach, welches besagt, da das Eulerprodukt fur jeden Zahlkorper nur 1bis x = 12 log(jDK j) approximiert werden mu,um im Schwankungsbereich 2 2 um EPK zu liegen. Dies wird in [2] gezeigt.
Es sei noch angemerkt, da in [4] die Abschatzung (3.8) auf anderem Weg als hierdargestellt erhalten wird. Insbesondere wird dort ein anderes C (t) verwendet, indas Daten der normalen Hulle L von K bzw. der Galoisgruppe von L uber Q
ein ieen. Daher ist es dort nicht moglich, einen expliziten Vorfaktor fur die
obige asymptotische Aussage anzugeben.
2

2

2

3

4

40

2

2

KAPITEL 3. DAS VERFAHREN

34

Abschatzung ohne GRH

Die Abschatzung von j log(T (x))j ist ohne Annahme von GRH fur Q und K
schwieriger. In der Literatur ist hieruber nichts zu nden.
Wir geben uns jetzt das " > 0 aus dem Primidealsatz fest vor. Weil die OKonstante und c unbestimmt sind, konnen wir keine expliziten Werte fur geeignete x angeben und sind von vorneherein am asymptotischen Verhalten vonx = x(DK ) interessiert. Aber auch hierfur gibt der Primidealsatz nicht genugend
Information her: Die O-Aussage teilt nur mit, da es von K unabhangige Konstanten C und x gibt, so da fur alle x  x gilt:jK (x) li(x)j  C Dx log(x) exp( cn log(x) 12 =D):
(3.10)
Hierbei ist x = x (n; DK ) und genaueres ist nicht bekannt. Wir wollen jetzt konkret mit dieser Ungleichung arbeiten, um das sich daraus ergebende asymptotische Verhalten fur x = x(DK ) analog wie oben zu bestimmen. Naturlich mu fur
ein korrektes Endresultat auch die Forderung x(DK )  x (n; DK ) berucksichtigt
werden.
Der Fehlerterm von Q (x) ist von der Ordnung c x log(x) exp( c log(x) 21 ).
Dieser Ausdruck wird kleiner als der im O-Term von K (x) fur x  2, wenn nur
jDK j"  cn =n , was ab jetzt gelten soll. Also
0

0

0

2

0

0

0

0

1

1

2

2

2

(3.11)jQ (x) K (x)j  2C Dx log(x) exp( cn log(x) =D)fur x  maxfx (n; DK ); x (1p; 1); 2g. Der Fehlerterm von Q (x) wachst nach
0

1
2

2

0

0

Lemma 3.4.2 starker als nQ ( x)=2. Aus diesem Grund gibt es ein x = x (n),so da fur x  x giltn  (x)  c x log(x) exp( c log(x) 12 ):(3.12)
2 Q
Wir fassen (3.11) und (3.12) zusammen und erhalten mit (3.7):
1

1

1

1

2

2

(3.13)
jA(x)j  (2C + 1)Dx log(x) exp( cn log(x) =D)fur x  maxfx (n; DK ); x (1; 1); x (n); 2g.
Die Ungleichung (3.13) zeigt, da limx!1 jA(x)j=x = 0. Da wir (3.6) anwenden
0

1
2

2

0

0

1

wollen, mu die rechte Seite integriert werden. Kurzt man log(x) 12 durch y ab
und schreibt a fur cn=D, so erhalten wir fur das Integral

Z log(x) exp( cn log(x) 12 =D)dxx2die Stammfunktion!
5y 20y 60y 120y 120
y2 exp( ay)a+ a + a + a + a + a :
5

4

2

3

3

2

4

5

6

(3.14)

3.4. KONVERGENZVERHALTEN DES EULERPRODUKTS

35

Fur x ! 1 gilt auch y ! 1 und (3.14) strebt gegen Null. Daher erkenntman, da die Integrale aus (3.6), die Reihe (3.5) und auch das Eulerprodukt
konvergieren.
Um die die rechte Seite von (3.6) zusammenzufassen, mussen wir die rechte Seite
aus (3.13) durch x dividieren und zum Betrag von (3.14) multipliziert mit (2C +1)D addieren. Der geklammerte Term wird dadurch um y =2 vergroert undbesitzt folgende Gestalt:
04

y + 5y + y + 20y + 60y + 120y + 120 :
a a
2
a
a
a
a
Dann konnen wir in diesem Term jede der Potenzen von y durch y ersetzen,
dies vergroert den Ausdruck, wenn x  e. Zusatzlich erweitern wir jeden derKoezienten auf 120. Wenn jDK j"  cn =n ist , so gilt a  1. Der Term
wird also hochstens groer, wenn die Potenzen von a bzw. der Nenner 2 durcha ersetzt werden. Durch eine ahnliche Schranke konnen wir a  2=D erreichen.
Wir bezeichnen das Maximum dieser Schranke und der Schranke fur jDK j" vor(3.11), die nur von n abhangen, mit D(n). Man erhalt nach diesen Schritten die
obere Abschatzung
4

5

4

3

2

2

3

4

5

6

5

+1

2

6

6

X
p>x

)y D ;
a (p)=p  240(2C + 1) exp( cny=D
cn
5

0

1

6

6

(3.15)

6

die fur x  maxfx (n; DK ); x (1; 1); x (n); eg und jDK j"  D(n) gultig ist.
Um j log(T (x))j abzuschatzen, mu noch der Fehlerterm, der durch die beiden
absolut konvergenten Reihen gegeben wird, berucksichtigt werden. Er betragt(c + 2c )=x wenn x  2c , wobei c ; c nur von n abhangen. Weil dieser Termviel schneller fallt als (3.15) fur wachsendes x und weil (3.15) monoton in jDK jwachst, gibt es ein x = x (n)  2c , fur das (3.15) groer als (c + 2c )=x wird,
wenn nur x  x ist.
Wir setzen x (n) = maxfx (1; 1); x (n); x (n); eg, C = 480n c n (2C + 1)
und b = cn =n . Dann gilt:
0

0

2
2

1

2

1

2

1

2

2

2

1

2
2

12 6(1

)

2

+1

3

0

2

1

2

1

0

j log(T (x))j  C jDK j " log(x) exp( b log(x) =jDK j")
6

1

5
2

(3.16)

1
2

fur x  maxfx (n; DK ); x (n)g und jDK j"  D(n).
Wir wollen jetzt fordern, da
p die rechte Seite von (3.16) bei gegebenem DK fur
x = x(DK ) echt kleiner log( 2) ist, und das asymptotische Verhalten von x(DK )fur wachsende Diskriminante beschreiben. Dazu de nieren wir
0

3



x (n; DK ; ) = exp jDK j " [11 log(jDK j") + 5 log(log(jDK j")) + ] =b
4

2

2

2

KAPITEL 3. DAS VERFAHREN

36

fur ein  > 0. Setzt man x (n; DK ; ) fur x in (3.16) ein, so erhalt man
4

C [11 + 5 log(log(jD j"))= log(jD j") + = log(jD j")] :KKKb exp()1(3.17)

5

5

Dies konvergiert fur jDK j ! 1 gegen 11 C b exp( ). Durch die geeignete
Wahl von  | abhangig nur von n | lat sich erreichen, da (3.17) fur p
genugend
groes jDK j unter Verwendung von x = x (n; DK ; ) echt kleiner als log( 2) wird.
Hieraus resultiert eine weitere untere und nur von n und  abhangige Schrankefur den Diskriminantenbetrag.
5

5

1

4

Folgerung 3.4.3 Es gibt D > 0 und  > 0, so da gilt: Wenn x (n; DK ) x (n; DK ; ) fur jDK j  D , so mu EPK (x) fur maximal
p x = x (n; DK ; )berechnet werden, damit j log(EPK ) log(EPK (x))j < log( 2) gilt.
4

0

0

0

4

Beweis: Wir wahlen  wie oben passend. D wird zuerst groer als das Ma0

ximum der bisherigen unteren Schranken fur den Diskriminantenbetrag | die
nur von n und mit einer Ausnahme auch von  abhangen | gewahlt. Dannvergroern wir D solange, bis x (n; D ; ) den Wert von x (n) uberschreitet.
Setzen wir jetzt x (n; DK )  x (n; DK ; ) fur jDK j  D voraus, so gilt (3.16)
und durch Einsetzen von x (n; DKp; ) fur x in der rechten Seite von (3.16) erhaltman j log(T (x (n; DK ; )))j < log( 2).
Weil das eingangs gewahlte " beliebig war, kann man unter Annahme der Vorausetzung von 3.4.3 fur "=4 auch x (n; DK ; ) = exp(jDK j") wahlen, wobei D
eventuell vergroert werden mu.
0

4

0

0

4

3

0

4

4

4

0

Bemerkungen

Unter der Annahme von GRH mu das Eulerprodukt EPK (x) bis zu einem x approximiert werden, welches mit der Diskriminante von der Ordnung log(jDK j)wachst. Wird ein " > 0 vorgegeben, so erhalt man fur x unter speziellen Voraussetzungen, aber ohne GRH, ein Wachstum der Ordnung exp(jDK j"). Die letztere
Aussage steht im Einklang mit einer Form des Primidealsatzes fur normale Erweiterungen, die in [24] bewiesen wird. Dort wird ein O-Term angegeben, in dem die
Konstanten nicht einmal mehr von DK abhangig sind. Dies wurde dazu fuhren,da x = x(DK ) konstant in DK ist. Daher gibt es dort die Nebenbedingungx  exp(jDK j") mit beliebigem " > 0. Diese Nebenbedingung spielt die Rolle desobigen x (n; DK ) und stimmt mit unserem Wachstumsverhalten uberein.
Da die Reihe (3.5) nicht absolut konvergiert, kann man sich mit dem Dichtigkeitssatz von Tschebotare klar machen. Da sie konvergiert bedeutet also ein
gewisses "oszillatorisches\ Gleichgewicht von Primzahlen, uber denen Grad-eins
Primideale liegen, und Primzahlen, uber denen keine solchen Primideale liegen.
203.5. BERECHNUNG DER KLASSENGRUPPENSTRUKTUR

37

Beim Beweis des Primidealsatzes arbeitet man mit einer mit K verwandten
Funktion K . Fur diese Funktion erhalt man mit funktionentheoretischen Mitteln eine sogenannte explizite Formel, aus der das zu beweisende asymptotische
Verhalten problemlos abgeleitet werden konnte, trate dort nicht noch eine Reiheuber die Nullstellen von K im StreifenP0 < Re(s) < 1 auf. Fur K = Q beispielsweise hat diese Reihe die Gestalt k x , wobei k die Ordnung des Polsvon  0= bei bezeichnet. Es ist zu zeigen, da sie schwacher wachst als x.
Die verallgemeinerte Riemannsche Vermutung besagt nun fur Dedekindsche Zetafunktionen K , da aus K (s) = 0 fur 0 < Re(s) < 1 folgt Re(s) = , und dieshilft bei der Handhabung der Reihe. Wird nichts voraussetzt, so mu man im
Streifen 0 < Re(s) < 1 spezielle nullstellenfreie Gebiete fur K betrachten. Auer
fur den Fall K = Q , siehe [19], scheint es keine unkonditionelle Version des Primidealsatzes mit expliziten von n und DK abhangigen Konstanten zu geben.
12

3.5 Berechnung der Klassengruppenstruktur
Nachdem wir mit Hilfe des Eulerprodukts davon ausgehen, da wir fur eine
vollstandige Faktorbasis S = fp ; : : : ; psg genugend S -Relationen ; : : : ; m gefunden haben, um das S -Einheitengitter zu erzeugen, und weiterhin die von Algorithmus 3.2.3 berechnete Klassengruppenmatrix H , die Relationsbasismatrix B
und die Einheitenmatrix U vorzuliegen haben, wollen wir jetzt die eingangs geforderten Informationen uber die Klassengruppe ermitteln. Die Einheitenmatrix
ist hierfur nicht erforderlich.
Ausgangspunkt bildet die Gleichung(p ; : : : ; ps) H = ( ; : : : ; m) B ;(3.18)
wobei H den Rang s hat und in unterer Hermite Normalform ist. In dieser Gleichung haben wir den multiplikativen Sachverhalt wie schon oben einmal additiv
notiert. Zu jeder Zeile bzw. jedem Diagonaleintrag von H korrespondiert wie ausder Gleichung ersichtlich eines der Primideale pi. Die Primideale, deren Diagonaleintrag ungleich 1 ist, erzeugen die Klassengruppe, denn alle anderen Primideale
werden modulo Hauptidealen durch diese dargestellt. Weil meistens sehr wenige
Primideale aus S genugen, um die Klassengruppe zu erzeugen, und diese hau gziemlich beliebig aus S wahlbar sind, ist ein Groteil der Diagonalelemente vonH gleich 1 und die Diagonaleintrage ungleich 1 sammeln sich in H tendenziell
unten rechts. Daher ist es sinnvoll, da die Primideale, die an der Erzeugung derKlassengruppe beteiligt werden sollen, in der Faktorbasis nach hinten sortiert
werden. Dies werden im allgemeinen Primideale kleiner Norm sein. Zur Verkleinerung von H konnen nun alle Zeilen und Spalten gestrichen werden, in deneneine 1 auf der Diagonalen steht. Entsprechend sind Primideale aus S und Spalten
aus B zu entfernen. Wir wollen annehmen, da nach passender Umbennung die
obige Gleichung unverandert gilt.
1

1

1

1

KAPITEL 3. DAS VERFAHREN

38

Von der Matrix H wird nun die Smith Normalform gebildet: S = U H V mit
unimodularen U , V . Entsprechend gilt dann(p ; : : : ; ps) U S = ( ; : : : ; m ) B V:
(3.19)
Wir sind damit dem Ziel schon sehr nahe. Allerdings kann U negative Eintrage
besitzen; infolgedessen wurden gebrochene Ideale als Erzeuger fur die zyklischen
Faktoren auftreten. Wir durfen aber zu den Spalten von U ganzzahlige Linearkombinationen der Spalten von H addieren, denn hierdurch werden diese
Erzeuger nur mit Hauptidealen multipliziert, was an den Eigenschaften innerhalb
der Klassengruppe nichts andert. Durch gesta eltes Addieren geeigneter Vielfacher der Spalten von H zu jeder einzelnen Spalte von U lat sich erreichen,da die Eintrage einer i-ten Zeile von U groer gleich Null und kleiner gleich
dem i-ten Diagonalelement von H werden. Bezeichnen wir die so erhaltene
neue Matrix mit Ue , so konnen wir unter Zuhilfenahme einer weiteren Matrix
A diesen Proze als verallgemeinerte Division mit Rest fur Matrizen notieren:
U = Ue + H A. Setzen wir dies in (3.19) ein und beachten (3.18), so erhalten
wir nach Umformunge = ( ; : : : ; m) B (V AS ):(p ; : : : ; ps) US(3.20)
Die gesuchten ganzen Ideale ai liefert uns jetzt die linke Seite ohne S , wohingegendie zugehorigen i durch die rechte Seite gegeben werden.
Mit dieser Methode erhalt man meistens gut konditionierte Erzeuger der zyklischen Faktoren der Klassengruppe. Die i hingegen konnen schlecht konditioniert
sein. Vor einer tatsachlichen Berechnung kann man in diesem Fall beispielsweise
die Spalten von B (V A) mit Hilfe von U reduzieren. Eine weitere Moglichkeit
ist, die i modulo Einheiten im S -Einheitengitter zu reduzieren.
1

1

1

1

1

1

1

1

1

1

3.6 Veri kation der S -Einheiten
Im Algorithmus 3.2.3 benutzen wir reelle Arithmetik endlicher Prazision, um das
von einigen S -Einheiten erzeugte Gitter zu bestimmen. Fur eine vollstandige Faktorbasis verwenden wir eine Approximation des Eulerprodukts, um zu entscheiden, wann das volle S -Einheitengitter erreicht wird. Dies kann dazu fuhren, da
die Einheiten nicht korrekt sind oder eine echte Untergruppe der S -Klassengruppe
berechnet wurde. Im folgenden soll daher ein Test vorgestellt werden, mit dem
unter Ausschaltung dieser Fehlerquellen bestimmt werden kann, ob tatsachlicheine Basis der S -Einheiten modulo Torsionseinheiten gefunden wurde, also insbesondere die korrekte S -Klassengruppe vorliegt. An S werden keine besonderen
Vorausetzungen gestellt.
Sei G eine abelsche Gruppe und U eine Untergruppe von G. Fur eine Primzahl
p nennt man U p-maximal in G, wenn aus w 2 G mit wp 2 U folgt w 2 U .

3.6. VERIFIKATION DER S -EINHEITEN

39

Lemma 3.6.1(i) Sei (G : U ) endlich. U ist p-maximal in G genau dann, wenn p - (G : U ).
(ii) Sei U inneres direktes Produkt zweier weiterer Untergruppen U1 und U2 vonG, wobei U1 die Ordnung n 2 N besitzt und p - n gilt. Es folgt, da U genau
dann p-maximal in G ist, wenn U2 p-maximal in G ist.
(iii) Sei U inneres direktes Produkt dreier Untergruppen U1 , U2 und U3 von
G und H = H1  H2 eine freie abelsche Gruppe. Sei  : G ! H ein
Homomorphismus mit U3  Kern , U1 \ Kern  = ;, (U1 )  H1 und
(U2)  H2. Weiter sei (U1) p-maximal in H1. U ist p-maximal in G
genau dann, wenn U2 U3 p-maximal in G ist.

Beweis: Die Aussage (i) folgt aus dem Satz von Cauchy angewendet auf G=U
und aus der Multiplikativitat von Indizes.
Zur Aussage (ii): "(\ Sei w 2 G mit wp 2 U , also wp = u u mit u 2 U undu 2 U . Nach dem Satz von Bezout gibt es k; l 2 N mit 1 = kp + ln. Daher
wp = ukpu . Folglich (wu k)p = u 2 U , so da wu k 2 U nach Voraussetzung.
Also w 2 U U = U .
)\ Sei w 2 G mit wp 2 U  U . Nachp Voraussetzungw 2 U , also w = u u"mitu 2 U und u 2 U . Wegen wp = u up folgt up 2 U \ U und somit up = 1.
Wegen p - n ergibt sich u = 1 und deswegen ist w = u 2 U .
Zur Aussage (iii): "(\ Sei w 2 G mit wp 2 U , also wp = u u u mit ui 2 Ui
fur 1  i  3. Wir konnen schreiben (w) = h h mit geeignetem h 2 H undh 2 H . Nach Potenzierung mit p, Anwenden von  und wegen des direkten
Produkts folgt aus der Division dieser beiden Gleichungen hp = (u ) und daraush 2 (U ). Daher gibt es unter Berucksichtigung der Kernbedingung an  einv 2 U mit vp = u . Durch Einsetzen wp = vpu u und wegen der p-Maximalitatgilt wv 2 U U . Deswegen gilt also w 2 U .
)\ Sei w 2 G mit wp 2 U U , also wp = upu . Nach der p-Maximalit
at von U"gilt
w = v v v mit vi 2 Ui . Hieraus folgt v 2 U U und somit vp = 1. Wegen(v )p = 1 und weil H frei ist, ergibt sich v 2 Kern  \ U und deswegen v = 1,
also w 2 U U .
Seien jetzt mit ; : : : ; r s beliebige S -Einheiten und mit r s ein Erzeuger
der Torsionseinheiten gegeben. Wir wollen an Aussage (ii) des vorangegangenen
Lemmas anknupfen:
1

2

2

1

1

2

2

1

2

1

1

2

2

1

2

2

1

1

2

1

2

1

2

1

1

1

2

2

1

2

1

1

2

2

2

3

2

1

1

2

1

1

1

1

1

1

1

1

1

1

2

1

2

2

3

3

3

2

3

1 2 3

1

1

2

3

1

2

1

1

1

3

1

+

+ +1

Lemma 3.6.2 Sei m = r + s +1 wenn p j wK und m = r + s sonst. Weiter gelte
1  m  m . Die von den Elementen m0 ; : : : ; m1 erzeugte Untergruppe U vonin UKS und m0 ; : : : ; r s sind unabhangig genau dann, wenn
UKS ist p-maximal
Q
k
m
p
1
i
aus = i m0 i fur beliebiges 2 UKS folgt, da km0  : : :  km1  0 mod p
gilt.
1

0

1

1

+

=

KAPITEL 3. DAS VERFAHREN

40

Beweis: ")\ Sei 2QUKS mit p = Qmi m

ki
i . Nach Voraussetzung gibt es aucheine Darstellung = mi=1m0 ili . Hieraus folgt ki pli = 0, also ki  0 mod p fur
m0  i  r + s. Wird wK von p geteilt, so gilt zusatzlich km1 plm1  0 mod wK ,und es ergibt sich km1  0 mod p.
ki
S mit p 2 U , also p = Qm1
(
\
Sei
2
U
i=m0 i . Nach Voraussetzung folgt p j ki
K"fur m  i  m . Der Kern von x 7! xp besteht
aus p-ten Einheitswurzeln. Dies01liefert =  Qmi=1m0 iki=p mit einer geeigneten p-ten Einheitswurzel  2 UKS . Wird
wK nicht von p geteilt, so folgt  = 1. Andernfalls konnen wir  durch r+s+1
1=0

ausdrucken. Daher ist 2 U und U somit p-maximal. Wahlen wir speziell = 1,
so sind die eben betrachteten ki=p fur m  i  r + s erneut durch p teilbar usw.
Also gehen in den ki beliebige Potenzen von p auf, so da nur noch ki = 0 furm  i  r + s ubrig bleibt.

Wir wollen mit Hilfe der beiden letzten Lemmata testen, ob der von unseren
gefundenen (vermeintlich) unabhangigen r + s S -Einheiten erzeugte Untermodul
samt Torsionseinheiten p-maximal in UKS fur jede Primzahl p ist. Dann namlich
ist die Gleichheit nachgewiesen. Naturlich ist es nicht moglich, tatsachlich jedes p einzeln zu testen. Es mu schon von vorneherein fur fast alle Primzahlen
feststehen, da p-Maximalitat vorliegt. Um dies zu erreichen, verwenden wir
eine obere Indexschranke. Aufgrund der Isomorphie 3.2 und Satz 3.2.1, S. 21
und S. 22, konnen wir den Klassengruppenanteil und den Einheitenanteil getrennt betrachten. Fur den Klassengruppenanteil sind die Primteiler der vermeintlichen S -Klassenzahl det H zu testen, weil nur diese im Index zur wahren
S -Klassenzahl auftreten konnen. Beim Einheitenanteil benotigen wir eine untere
Regulatorschranke, um den Index der berechneten Einheitengruppe in UK nachoben abschatzen zu konnen, vergleiche (2.1), S. 14. Dann sind alle Primzahlen
unterhalb der Indexschranke zu testen. Die untere Regulatorschranke erhalt man
mit Methoden aus [16, 15, 22].
Die Bedingung des Lemmas 3.6.2 zeigt, da man o enbar in den Exponenten
modulo p rechnen mu und auerdem die Eigenschaften der Basiselemente irgendwie greifbar zu machen hat. Dies geschieht durch die Verkettung mehrerer
Abbildungen zu einem Homomorphismus der multiplikativen Struktur von UKS in
die additive von F p .
Sei q ein Primideal mit q 62 S . Wir wollen die Elemente von UKS sinnvoll modulo
q betrachten. Dazu lokalisieren wir oK nach q, bilden also den Quotientenring
oK
oqK =
0

0

oK n q

und bezeichnen mit  : oqK ! oqK =qoqK die Restklassenabbildung. Es gilt
UKS  oqK und ferneroK =q ' oqK =qoqKunter dem durch die Inklusion oK  oqK induzierten kanonischen Isomorphismus.
Durch entsprechende Verknupfung wird ein Homomorphismus  : UKS ! oK =q12

3.6. VERIFIKATION DER S -EINHEITEN

41

geliefert, dessen Einschrankung auf oK \ UKS mit der ublichen Restklassenabbildung ubereinstimmt. Diese Aussagen konnen beispielsweise in [18], S. 181,
nachgelesen werden.
Wir betrachten den Restklassenkorper oK =q mit N (q) Elementen. (oK =q) isteine zyklische Gruppe der Ordnung N (q) 1; alle endlichen Untergruppen dermultiplikativen Gruppe eines Korpers sind namlich zyklisch. Also (oK =q) =< > mit einem geeigneten  2 (oK =q). Jedes 2 (oK =q) hat eine Darstellung=  k , wobei k modulo N (q) 1 eindeutig bestimmt ist. Dies nutzen wir zur
De nition von log : (oK =q) ! Z=(N (q) 1)Z durch log ( ) = k.
Jetzt sei angenommen, da das Primideal q mit p j N (q) 1 gewahlt wird, wobei
p eine zu testende Primzahl ist. Damit erhalt man ein  : Z=(N (q) 1)Z ! F p ,welches x + (N (q) 1)Z auf x + pZ abbildet.
Durch Hintereinanderausfuhrung von  , log und  lat sich der angekundigte
Homomorphismus  : UKS ! F p , der von q und der Wahl von  abhangt, de nieren. Mit Hilfe von  und mehreren Primidealen q konnen wir die Bedingung
aus Lemma 3.6.2 testen:3

2

3

Satz 3.6.3 Seien p eine Primzahl und m ; : : : ; r s S -Einheiten mit 1  m 0+0

r + s. Zusatzlich sei r s ein Erzeuger der Torsionseinheiten und m = r + s +1
wenn p j wK , ansonsten m = r + s. Schlielich sei eine Menge Q = fqm0 ; : : : ; qk g
von Primidealen gegeben. Zu jedem qi 2 Q wahlen wir einen Erzeuger i von(oK =qi). Gelten nun die Bedingungen(i) qi 62 S fur m  i  k,(ii) p j N (qi) 1 fur m  i  k,(iii) Die Matrix (i ( j ))i;j mit m  i  k und m  j  m hat Rangm m + 1 uber p ,so ist die von m0 ; : : : ; r s erzeugte Untergruppe von UKS p-maximal. Ist umgekehrt diese Untergruppe p-maximal, so existiert eine Menge Q von Primidealen
+ +1

1

1

0

0

0

1

0

0

1

F

+ +1

mit den Eigenschaften (i){(iii).

Beweis: Die erste Aussage ist klar, wenn man i auf die Bedingung aus Lemma

3.6.2 anwendet und bedenkt, da i ein Homomorphismus ist. Auerdem mu
Lemma 3.6.1 (ii) beachtet werden. Es sei noch bemerkt, da die Wahl der ikeinen wesentlichen Ein u auf die Matrix aus der dritten Bedingung hat. Eine
andere Wahl fuhrt zu einer neuen Matrix, die aus den Zeilen der alten Matrix
multipliziert mit Elementen aus F p besteht. Dies andert den Rang nicht.
Schwierig ist die zweite Aussage. Im Falle von Einheiten werden die wesentlichen
Argumente ausfuhrlich in [22] beschrieben, so da wir uns an dieser Stelle mit
einer knapperen Darstellung begnugen wollen. Wir konnen davon ausgehen, da

KAPITEL 3. DAS VERFAHREN

42

die von den m0 ; : : : ; m1 erzeugte Untergruppe U p-maximal in UKS ist und dajedes i ganzalgebraisch ist. Letzteres lat sich durch eine unimodulare Transformation bewerkstelligen, die man aus der Bildung einer Hermite Normalform derMatrix (S ( i))m0 im1 erhalt. Die Idee ist jetzt, die Matrix aus der obigen dritten Bedingung zeilenweise in unterer Diagonalgestalt aufzubauen, wobei simultan
m0 ; : : : ; m1 unimodular transformiert werden. Diagonalelemente ungleich Nullverscha en wir uns mit Hilfe der folgenden U berlegungen:
Sei eine ganzalgebraische S -Einheit, die keine p-te Potenz ist. Das Polynom
g(t) = tp
ist dann irreduzibel. Die Ordnung der Galoisgruppe dieses Polynoms wird von p geteilt, so da darin nach dem Satz von Cauchy ein Element derOrdnung p existiert. Aufgefat als Permutationsgruppe der p Nullstellen von g(t)stellt dieses Element eine Permutation des Zykeltyps (p) dar. Nach dem Dichtigkeitssatz von Tschebotare gibt es aus diesem Grund unendlich viele Primidealeq, so da g (t) mod q irrdeduzibel ist. Es kann sogar gefordert werden, da q
den Restklassengrad 1 besitzt. Also ist auch mod q keine p-te Potenz. Wirkonnen zusatzlich annehmen, da q 62 S . Ferner folgt aus der Existenz von ,da p j N (q) 1, denn sonst ware jedes Element von (oK =q) eine p-te Potenz.
Dies alles hat zur Folge, da  ( ) 6= 0 ist. Durch  ist hierbei ein Erzeuger von(oK =q) gegeben.
Wir gehen jetzt per Induktion uber i vor. Seien m  i  m , m0 ;i; : : : ; m1 ;i die
aktuellen S -Einheiten, die U erzeugen, Qi = fqm0 ; : : : ; qi g eine Menge von im Primidealen, die den Bedingungen (i){(ii) gerecht wird, und Mi = (g ( j;i))g;j
mit m  g < i und m  j  m eine Matrix in unterer Dreiecksgestalt.
Aufgrund der p-Maximalitat von U ist keins der m0 ;i; : : : ; m1 ;i eine p-te Potenz,
so da speziell ein Primideal qi 62 S mit i ( i;i) 6= 0 existiert. Dies liefertzunachst eine neue Zeile von Mi, die an der i-ten Stelle den Eintrag i ( i;i) hat.
Aber hinter der i-ten Stelle konnen auch noch Eintrage ungleich Null auftreten.
Angenommen, i ( v;i ) 6= 0 fur ein v > i. Da man in F p invertieren kann, lat sichdieser Eintrag mit einem Gauss'schen Eliminationsschritt durch Spaltenoperation
nullen. Entsprechend setzen wir v;i = v;i i;iu , wobei 0 < u < p geeignet. Dies
wird fur alle solche v getan und fur die restlichen Indizes v setzen wir dannv;i = v;i . Ferner wird Qi = Qi [ fqi g gesetzt. Die m0 ;i ; : : : ; m1 ;i sindmittels unimodularer Transformation entstanden und erzeugen daher U .
Schlielich ist Mm1 eine quadratische Matrix in unterer Diagonalgestalt mit
Determinante ungleich Null, also Rang m m + 1, was zu zeigen war.

0

1

1

0

0

0

1

+1

+1

+1

+1

+1

+1

1

0

Wir wollen auf eine Verbesserung hinweisen. Es ist namlich unter gewissen
Voraussetzungen an ; : : : ; m1 nicht unbedingt notig, alle diese Elemente zum
Testen heranzuziehen. Entsprechend sind weniger Primideale fur Q zu berechnen. Wir setzen speziell jetzt ( ; : : : ; s) = ( ; : : : ; m) B V , wie in der ungekurzten Fassung von (3.19) auf S. 38, ( s; : : : ; r s) = ( ; : : : ; m ) U undr s wie oben. An dieser Stelle ist bewiesen, da die durch U gelieferten
Elemente wirklich Einheiten und ; : : : ; s unabhangige S -Relationen sind. Sei
1

1

1

1+

+ +1

1

+

1

3.6. VERIFIKATION DER S -EINHEITEN

43

a = minf i : p j di und 1  i  sg. Wir be nden uns in der Situation vonLemma 3.6.1 (iii), wobei G = UKS , U = < s; : : : ; r s > und  = S . WeiterU = < ; : : : ; a >, U = < a; : : : ; s > und H = a , H = s a. Zum
Testen der Primzahl p konnen also ; : : : ; a weggelassen werden. Weil ein
Groteil der ersten di in der ungekurzten Fassung aus (3.19) Einsen sind, wird
hierdurch eine groe Verbesserung erzielt.
Wir formulieren jetzt einen Algorithmus, der speziell die Korrektheit der S Klassengruppe testet:
3

1

1

1

1+

+ +1

2

1

1

Z

1

2

Z

1

Algorithmus 3.6.4 (Test der S -Klassengruppe)
Eingabe: S , S -Einheiten 1 ; : : : ; m, Matrizen U , B , V und S wie in derungekurzten Fassung von (3.19). Auerdem ein Erzeuger  der Torsionseinheiten und der Torsionsrang w.
Ausgabe: Bei Termination ist die Korrektheit der berechneten S -Klassengruppe
bewiesen.
1. (Initialisierung) Seien p1 ; : : : ; pl die Primfaktoren der Determinante von S
und d1 ; : : : ; ds die Diagonalelemente von S . Setze aj minf i : pj j di und
1  i  sg fur 1  j  l. Setze j 0.
2. (Nachste Primzahl) Setze M() und j

j + 1. Wenn j > l terminiere.

3. (Berechne neue Zeile) Setze U bzw. B gleich der Matrix, die aus den U
bzw. B V durch Reduktion der Koezienten modulo pj entsteht. Entferne
die ersten aj 1 Spalten von B . Finde ein fur dieses j noch nicht betrachtetes Primideal q 62 S uber der Primzahl q mit p j q 1 und berechne
einen Erzeuger  von (oK =q). Erweitere M um die Zeile, die aus den
kleinen Zeilen ( ( 1 ); : : : ;  ( m)) B , ( ( 1 ); : : : ;  ( m )) U und ( ( ))| letzteres aber nur im Fall p j w | entsteht.
4. (Rang von M?) Hat M den maximalen Rang s aj +1+ r +1 fur p j w oders aj + 1 + r sonst, so ist die pj -Maximalitat getestet, gehe zu Schritt 2.
Sonst gehe zu Schritt 3.

Die Tatsache, da  homomorph ist, kann nutzbringend eingesetzt werden. Dadurch lat sich die direkte Berechnung der ; : : : ; s vermeiden und die unterUmstanden groen Koezienten der Matrizen U und B V konnen modulo p
reduziert werden. Die benotigten Primideale q lassen sich in der Praxis meistensziemlich leicht nden.
1

KAPITEL 3. DAS VERFAHREN

44

3.7 Zusammenfassung

Wir wollen im folgenden Algorithmus den Ablauf einer Klassengruppenberechnung in der U bersicht angeben und die bisher behandelten Methoden einordnen.
Algorithmus 3.7.1 (Klassengruppenverfahren)
Eingabe: Ein Zahlkorper der Signatur (r ; r ) mit erzeugendem Polynom f (t)und Ganzheitsbasis.
Ausgabe: Ganze Ideale a ; : : : ; am , c ; : : : ; cm 2 Z und ganzalgebraische Zahlen; : : : ; m wie in (3.1).
1. (Erstellung der Faktorbasis) Mit den Methoden des nachsten Kapitels undwie in Abschnitt 4.3.3 wird eine geeignete Faktorbasis S berechnet. Das
Eulerprodukt wird wie in Abschnitt 3.3 erlautert approximiert.
2. (Suche nach einer Relation) Mit den Methoden des nachsten Kapitels, Abschnitt 4.4.5 und Abschnitt 4.5, wird eine S -Relation berechnet.
3. (Auswertung der Relation) Mit Algorithmus 3.2.3 wird die neue S -Relation
unter Berucksichtigung der bereits berechneten S -Relationen ausgewertet.
4. (Testen der Abbruchbedingung) Wenn der Rang der Klassengruppenmatrix
noch nicht s oder der Rang der Einheitenmatrix noch nicht r betragt, gehezu Schritt 2. Teste mit Hilfe des Eulerprodukts wie in Abschnitt 3.3 beschrieben, ob vermutlich die korrekte Klassenzahl und der korrekte Regulator berechnet wurden. Wenn nein, gehe zu Schritt 2.
5. (Ableitung der Klassengruppendaten) Bestimme wie in Abschnitt 3.5 beschrieben die Daten, die fur die Ausgabe benotigt werden.
6. (Veri kation der Ergebnisse) Fuhre Algorithmus 3.6.4 durch. Damit wird

die Korrektheit der S -Klassengruppe bewiesen. Uberpr
ufe auch wie imnachsten Kapitel beschrieben die Vollstandigkeit der Faktorbasis S .
7. (Ausgabe der Ergebnisse) Ausgabe der Klassengruppendaten. Terminiere.
Fur die einzelnen Schritte ist zu beachten, was bereits im Speziellen gesagt wurde
und auch noch gesagt werden wird. Hau g mochte man beispielsweise auf die explizite Berechnung der ; : : : ; m aus Zeitgrunden verzichten. Auch kann man
die Veri kation der Klassengruppe auslassen oder nur teilweise durchfuhren. Der
Beweis der Vollstandigkeit der Faktorbasis ist der kritischste Punkt. Ohne Hinzunahme unbewiesener Vermutungen ist es fur Zahlkorper groeren Grades und
Diskriminante sehr langwierig oder zeitlich gesehen nicht mehr moglich, die Klassengruppe bewiesen zu berechnen. Durch diesen Algorithmus werden auch Fundamentaleinheiten geliefert, deren Test ebenfalls sehr zeitaufwendig werden kann.
1

1

1

1

1

2

2

Kapitel 4
Faktorbasis und Relationensuche
In diesem Kapitel wollen wir auf die Berechnung geeigneter Faktorbasen S und die
S -Relationensuche eingehen. Eine Faktorbasis S mu verschiedene Eigenschaften
aufweisen. Sie mu zuerst einmal vollstandig sein, also die ganze Klassengruppe
erzeugen. Sie sollte naturlich die S -Relationensuche unterstutzen, und sie sollte
nicht zu gro sein. Gerade die letzten beiden Forderungen sind in gewissem Sinne
kontrar, so da ein Mittelweg beschritten werden mu.

4.1 Grundideen der Relationensuche
Die meisten Methoden der Relationengewinnung beruhen auf der Moglichkeit,
ganzalgebraische Zahlen in Idealen von K mit betraglich kleinen Normen zu bestimmen. Sei dazu a ein beliebiges ganzes Ideal von K . Wie im Abschnitt 2.3
beschrieben, bestimmen wir im Konjugiertengitter von a Elemente mit kleineroder kleinster T -Norm. Fur ein solches 2 a ist aufgrund der Ungleichungzwischen arithmetischem und geometrischem Mittel und weil a j ist zu erwarten, da =a ein ganzes Ideal mit kleiner Norm, also N ( =a) ganz und klein ist.
Die Bestimmung solcher Elemente kann wie erwahnt mit dem Auszahlalgorithmus von Fincke und Pohst sehr e ektiv geschehen. Ein bezuglich der T -Normsehr kleines | hau g kleinstes | Element wird mit dem ersten Element einer
LLL-reduzierten Basis geliefert, so da auch die LLL-Reduktion fur die Relationensuche verwendet werden kann. Interessant ist an dieser Stelle, wie die Normeines Element 2 a mit kleinster T -Norm nach oben beschrankt wird. Aus [21],Lemma 4.3 auf S. 44, erfahren wir, da
2

2

2

1
n 2 N (a)jD j 21 ;
n
(4.1)
K
n
wobei nn die n-te Hermitesche Konstante bezeichnet. Verwenden wir ein erstes
Element einer LLL-reduzierten Basis, so gilt
1jN ( )j  2n n n n 2 N (a)jDK j 21 :(4.2)

jN ( )j 

n

(

1)

45

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

46

Siehe dazu [15], S. 62.
Fur das folgende wollen wir a de nieren als Potenzprodukt von Primidealen einer
Faktorbasis S , wobei a 6= oK . Wahlen wir S bestehend aus allen Primidealen mit
Norm unterhalb der Schranke (4.1), so liefert uns ein 2 a kleinster T -Normeine S -Relation, denn =a faktorisiert in Primideale aus S . Erfreulicherweise ist
diese Faktorbasis wegen (4.1) und den Konsequenzen aus (2.2), S. 17 vollstandig.
Wie wir sehen werden, ist es aber hau g moglich und notig, eine wesentlich kleinere Schranke als (4.1) fur die Faktorbasis zu verwenden. In diesem Fall liefert
uns ein T -Norm-kleinstes Element von a keineswegs mehr unbedingt eine S Relation, da in der Faktorisierung von =a, die zwar tendenziell aus Primidealen
kleiner Norm besteht, groere Primideale auftreten konnen als in der Faktorbasis
vorhanden sind. Sofern S nicht zu drastisch verkleinert wurde, ist es naturlich
trotzdem noch "recht wahrscheinlich\, da auf diese Weise S -Relationen gewonnen werden konnen. Will man sich darauf aber nicht allein verlassen, so merkt
man sich fur mehrere solcher und a die ganzen Ideale =a, deren Norm durch
die Schranke (4.1) beschrankt ist. Da es nur endlich viele ganze Ideale mit beschrankter Norm gibt, konnen bei ausreichender Anzahl nicht alle der gemerkten
Ideale verschieden sein; also etwa =a = =b und folglich = = a=b. Weil aund b Potenzprodukte von Primidealen aus S sind, ist = eine S -Einheit undim Falle a 6= b naturlich eine S -Relation.
Die Methode, sich die =a zu merken und auf Gleichheit zu uberprufen, fuhrt auf
die Relationengewinnung mittels reduzierter Ideale, die in [20] beschrieben wird,
und auf die Relationenerzwingung von v. Schmettow, siehe [21].
Man kann sich nun fragen, wie man die Ideale a zu wahlen hat, um mit den erzeugende Elemente von HKS zu berechnen, und ob dies uberhaupt moglich ist. Die
Relationenerzwingung ist eine Strategie, wie man mit den obigen Methoden eine
Untergruppe von HKS mit endlichem Index berechnen kann. Von hier kann man
mit dem p-ten Wurzeltest | sofern Einheiten gegeben sind | zu HKS aufsteigen.
Es sei erwahnt, da es eine weitere Methode der Relationengewinnung gibt, dienicht uber die Bestimmung von Elementen kleiner T -Norm geht. Es ist die
Methode, die im Number Field Sieve (NFS) verwendet wird. Wir kommen darauf
spater zu sprechen.
Zum Schlu wollen wir die Verwendung des Auszahlalgorithmus beschreiben. Fur
2 a gilt aufgrund der Ungleichung zwischen arithmetischen und geometrischen
Mittel T ( )  nN (a) =n . Wir bestimmen daher Elemente mit
2inN (a) =n  T ( ) < 2i nN (a) =n ;beginnend bei i = 0. Finden sich in diesem Ringbereich keine nicht bereits ausgezahlten Elemente mehr, so wird i gleich i + 1 gesetzt und das Auszahlen fortgefuhrt. Speziell geht man so vor, da mit auch
als ausgezahlt gilt. Diese
Methode wird bei samtlichen Auszahlprozessen in dieser Arbeit angewendet.
2

2

2

2

2

2

2

+1

2

4.2. SMOOTHNESS-EIGENSCHAFTEN

47

4.2 Heuristische Schranken und SmoothnessEigenschaften

Wir wollen die etwas vage Aussage "die Zahl ist wahrscheinlich eine S -Relation\des vorigen Abschnitts mit Hilfe der folgenden Satze konkretisieren und dann aneinem Beispiel verdeutlichen.

Satz 4.2.1 Die Anzahl der ganzen Ideale von K mit Norm unterhalb einem x > 0
ist gegeben durch

I (x) = 2 (2) hK1RK  x + O(x n1 ):wK jDK j 2
r1

r2

1

Der Vorfaktor ist das Residuum der Dedekindschen Zetafunktion K (s) bei 1.

Beweis: Siehe [12], S. 361 und S. 415.
De nition 4.2.2 Seien x; c 2 , c > 0 und x > 1.

R(i) Wir nennen ein ganzes Ideal a von K x-smooth, wenn fur jedes Primideal
p mit p j a gilt, da N (p)  x ist.
(ii) Wir setzen

fK (x; c) = j fa j N (a)  x und a ist xc -smooth g j:

Satz 4.2.3 Fur die Funktion fK (x; c) gilt die asymptotische AussagefK (x; c) = I (x)(c) + O(x= log x);
wobei  die Dickman-de-Bruijn-Funktion bezeichnet.

Beweis: Siehe [21], S. 30-31. Dort werden auch genaue Angaben uber  gemacht.
Bei  handelt es sich um eine stetige monoton wachsende Funktion > ! > .
O enbar ist (c) = 1 fur c  1. Im Bereich c 2 [ ; 1] gilt (c) = 1 + log c.
R

0

R

1
2

0

Ansonsten erfullt  fur 0 < c < c < 1 die FunktionalgleichungZ c2
(c ) (c ) = ( u ) du :1 u uc1Diese kann genutzt werden, um  sukzessive in den Intervallen [ ; ), [ ; ), : : :numerisch zu berechnen, denn geschlossene Ausdrucke fur (c) sind hier namlich
nicht bekannt. Mit Hilfe des Computeralgebra-Systems Maple erhalten wir beispielsweise:
1

2

2

1

1
3

1
2

1
4

1
3

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

48

c 0:75 0:5 0:33 0:25
0:2
(c) 0:71 0:31 0:046 0:00491 0:000355
Wie schon erwahnt, werden Elemente kleiner T -Norm in Idealen a berechnet |wobei a uber der verwendeten Faktorbasis vollstandig faktorisiert |, so da das
Ideal =a beschrankte Norm besitzt. Unter der Voraussetzung, da diese Ideale
beschrankter Norm hinreichend zufallig bestimmt werden, ist es also mehr als nur
plausibel, da mit dieser Methode Relationen gewonnen werden konnen. Nehmen
wir nun an, da die Ideale =a zufallig mit Norm unterhalb einer Schranke B
bestimmt werden und die Faktorbasis S aus den Primidealen mit Norm unterhalb
B c besteht | wobei 0 < c  1 |, so ist die zu erwartende Anzahl an Relationen
unter m Kandidaten bei Vernachlassigung des O-Terms gleich (c)  m.
Inwieweit die Ideale =a tatsachlich zufallig mit Norm kleiner gleich B bestimmt
werden, hangt von der Art der Relationensuche ab. Man ist naturlich bemuht,da die Normen nicht zufallig bzw. gleichverteilt unter B liegen, sondern eher
kleiner sind, denn hierdurch wird die Smoothnesswahrscheinlichkeit erhoht. Entsprechend wird es fraglicher, ob  zur Einschatzung dieser Wahrscheinlichkeit
herangezogen werden kann. Auerdem mu beachtet werden, da die Ideale =a
auf ganz spezielle Weise erzeugt werden und dies unter Umstanden Ruckwirkung
auf Smoothnesseigenschaften hat. Hieruber scheint aber nichts bekannt zu sein.
Moglichst kleine Normen erhalten wir, wenn nur Elemente kleinster oder sehrkleiner T -Norm bestimmt werden. In einem Ideal a erhalt man so ein mit dem
ersten Basiselement einer LLL-reduzierten Basis des Ideals. Hierbei handelt essich hau g um ein Minimum in a im Sinne von [5], S. 346-348, bzw. [21], S. 9,
und das ganze Ideal =a ist in diesem Fall das Inverse eines reduzierten Ideals.
Wir wollen Ideale a= , wobei das erste Element einer LLL-reduzierten Basisvon a ist, "pseudoreduzierte\ Ideale nennen.
Beispiel 4.2.4 Es sei K der von f (t) = t 3457t + 1127 erzeugte Zahlkorper
mit r = 2, r = 1 und log (DK )  19:99. Die Minkowskischranke betragt
ungefahr 119  10 . Zur Relationensuche wahlen wir der Reihe nach die Primideale p mit Norm unterhalb einer Schranke C  100. Aus diesen Primidealen
erhalten wir durch Multiplikation mit zufalligen Produkten der Form Q pki i , indenen hochstens 5 Primideale pi mit N (pi )  100 auftreten und die Exponenten
0  ki  3 erfullen, Ideale a, in deren Konjugiertengitter jeweils das erste Element einer LLL-reduzierten Basis bestimmt wird. Diese Elemente dienen dannals Relationskandidaten. Eine genaue Beschreibung dieser Art von Relationensuche ndet sich weiter unten in Algorithmus 4.4.5.
Fur C 2 f200; 400; 700; 1000g bestimmen wir mit dieser Methode jeweils 2000
Elemente, so da N ( =a) kleiner gleich B = 75  10 ist, und ermitteln darunter
die C -smoothen Elemente. Fur jedes C wird die Anzahl der Kandidaten und
die Anzahl der tatsachlich C -smoothen Elemente, so da N ( =a)  x ist, fur
2

2

4

1

2

7

3

10

7

4.2. SMOOTHNESS-EIGENSCHAFTEN

49

0  x  B uber x in der Abbildung 4.1 aufgetragen. Die Skalierung der x-Achse
ist so gewahlt, da 500 dem tatsachlichen Wert von x gleich 75  10 entspricht.
7

2000

1500

1000

500

0

100

200

x

300

400

500

Abbildung 4.1: Die Normverteilung der Inversen einiger zufalliger pseudoreduzierter Ideale fur verschiedene
Smoothnessbedingungen
Die vier Kurven ohne Smoothnessbedingung liegen dicht beieinander, die Groeder Faktorbasis spielt hier keine Rolle. Anders sieht das bei den Smoothnesskurven aus. Diese entsprechen der Groe nach den verschiedenen Werten von C .

Es ist zu beobachten, da von einer zufalligen Verteilung der Normen nicht die
Rede sein kann. Die Kurven ohne Smoothnessbedingung sind charakteristischfur die Art der Relationssuche; auch fur andere Anzahlen von zu berechnenden
Kandidaten haben sie bis auf einen Skalierungsfaktor diese Form. Mit Ie sei die
zugehorige (stetige) Funktion gemeint, die man im Mittel aus diesen vier nahebeieinander liegenden Kurven erhalt.
Wir wollen jetzt unter Vernachlassigung obiger Bedenken  zur Smoothnessbestimmung heranziehen und aber versuchen, der ungleichmaigen Verteilung derNormen Rechnung zu tragen. Die nachfolgenden Berechnungen erheben keinen

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

50

Anspruch auf besondere Exaktheit und dienen vornehmlich der Suche nach heuristischen Aussagen uber Smoothnesswahrscheinlichkeiten. Die Idee ist die folgende: Anstatt alle C -smoothen Ideale mit Norm kleiner gleich einem x  B
auf einmal zu berechnen, unterteilen wir diesen Bereich in Intervalle [xi ; xi ] mit
1 = x < : : : < xk = x und bestimmen uber  die Anzahlen der C -smoothen
Ideale mit Norm zwischen xi und xi . Die Wahrscheinlichkeit, da ein zufalliges
gewahltes ganzes Ideal mit Norm groer xi und kleiner gleich xi C -smooth ist,
sollte bei
(log(C )= log(xi ))I (xi ) (log(C )= log(xi))I (xi)I (xi ) I (xi)liegen. Fur x ist log(x ) = 0; hierfur sei (log(C )= log(x )) = 1 de niert. Durch
Aufsummieren dieser Werte fur i = 1; : : : ; k ergibt sich schlielich ungefahr die
Gesamtanzahl der C -smoothen Ideale, die bei der durchgefuhrten Relationensuche auftreten:kX (log(C )= log(x ))x(log(C )= log(xi ))xi (Ie(x ) Ie(x )):
i
i
i
i
xi
xi
i
Den Vorfaktor der Idealzahlfunktion I haben wir hier herausgekurzt. Im Grenzproze k ! 1 wird aus dieser Summe ein Integral und wir setzenZeC (x) = 1 x gC0 dI;e
(4.3)
Ie(x)
wobei gC (t) = t(log(C )= log(t)) ist. Die Ableitung von gC ist Null fur t <C , fur t = C existiert sie nicht und fur t > C kann man sie mit Hilfe der
Funktionalgleichung von  wieder durch  ausdrucken. Dieses e C (x) soll die
Wahrscheinlichkeit angeben, da Relationskandidaten mit N ( =a)  x C smooth sind. In Ie gehen die Eigenschaften der verwendeten Relationssuche ein.
+1

1

+1

+1

+1

+1

+1

1

1

=1

1

1

+1

+1

+1

+1

1

Beispiel 4.2.5 Wir wiederholen das obige Beispiel, beschranken uns diesmal
aber auf den interessanten Bereich N ( =a)  B mit B = 9  10 , was in der7

Abbildung 4.1 dem Wert 60 auf der x-Achse entspricht. Auf dieselbe Weise wie
oben werden jeweils 2000 passende Elemente bestimmt, die auf Smoothnesseigenschaften untersucht werden. Entsprechend werden Ie und e C de niert. Zusatzlich
approximieren wir e C (x)Ie(x) und tragen die so erhaltenen Smoothnesskurven(grau) zum Vergleich mit den tatsachlichen Kurven (schwarz) in Abbildung 4.2
ein. C ist wieder aus f200; 400; 700; 1000g. Die Kurven fur Ie werden fortgelassen.

Es bietet sich zunachst ein ahnliches Bild wie schon zuvor, nur da der Normbereich vermieden wird, in dem quasi keine Ideale mehr erzeugt werden. Au allig
ist die relativ gute U bereinstimmung der tatsachlichen mit den uber e C und Ie berechneten Kurven sowohl in Form als auch in absoluter Groe. U brigens werden
die tatsachlichen Kurven umso glatter, je mehr Elemente bestimmt werden.

4.2. SMOOTHNESS-EIGENSCHAFTEN

51

250

200

150

100

50

0

10

20

30
x

40

50

60

Abbildung 4.2: Tatsachliche und theoretische Smoothnesskurven im Vergleich
Durch dieses Beispiel wird nahegelegt, da man sich tatsachlich mit  unter
Verwendung der praktisch zu bestimmenden Funktion Ie einen U berblick uberverschiedene Smoothnesswahrscheinlichkeiten pseudoreduzierter Ideale verschaffen kann. Dies ist jedoch mit Vorsicht zu genieen, da wir einige unbewiesene
Annahmen gemacht und O-Terme vernachlassigt haben. Es zeigt sich, da dievorausgesagten Smoothnesskurven fur andere Zahlkorper meistens bis auf einen
Skalierungsfaktor oder auch eine Verschiebung ganz gut mit den tatsachlichenubereinstimmen, aber ohne diese A nderungen eher unterhalb liegen. Das Faktorisierungsverhalten ist also eher freundlicher als vorhergesagt.
Eine Moglichkeit, sich bei der Relationensuche nicht nur auf die obige Pseudoreduktion zu stutzen, besteht beispielsweise darin, in den Idealen a statt desersten Elements einer LLL-reduzierten Basis eine gewisse Anzahl an Elementen
kleiner T -Norm zu bestimmen und dann =a zu betrachten. Auch fur solche
Ideale konnen wir entsprechende Smoothnesskurven und ein Ie bestimmen; wie
zuvor fallen namlich beim obigen Beispiel die Kurven der absoluten Anzahl quasi
zusammen. Der Verlauf dieses Ie ist wesentlich linearer und entsprechend treten
auch eher groere Normen auf bei gleichzeitig sinkender Smoothnesswahrschein2

52

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

lichkeiten. Die mit (4.3) vorausgesagten Kurven stimmen wieder von der Formher gut uberein, sind aber ebenfalls zu pessimistisch.
Wir wollen jetzt uberlegen, welche Schlusse aus dem bisher gesagten fur einemoglichst gut geeignete Faktorbasis gezogen werden konnen. Es wurde eingangs
schon erwahnt, da eine Faktorbasis, abgesehen von der Bedingung vollstandig zu
sein, fur die Relationensuche weder zu klein noch zu gro sein sollte. In ersterem
Fall lassen sich keine Relationen nden | auch wenn nur wenige notig sind, damit
die Klassengruppenmatrix vollen Rang bekommt |, wohingegen im zweiten Fall
Relationen zwar leicht gefunden werden, aber auch viele vonnoten sind. A priori
gibt es keinen Ansatz, wie die geeignete Groe zu nden ist.
Wir benotigen wieder den Primidealsatz. Fur die mit Hilfe obiger Methode bestimmten Relationen zeigt sich, da sie ublicherweise fast allesamt unabhangig
sind und nur wenig mehr davon als Elemente in der Faktorbasis vorhanden zur
Bestimmung der Klassengruppe benotigt werden. Daher mute die Anzahl derwahrend einer Klassengruppenberechnung zu berechnenden Relationskandidaten
2 a mit N ( =a)  B ungefahrli(C )
e C (B )(4.4)

betragen. Minimieren wir diese Anzahl fur festes B aber variables C , so sollte man
mit dem entsprechenden C die optimale Schranke fur eine Faktorbasis gefunden
haben.

Beispiel 4.2.6 Wir betrachten das bereits verwendete Beispiel. Fur verschiedene
Werte von C zwischen 100 und 2500 werden solange Relationskandidaten 2 a
mit N ( =a)  B nach der obigen Methode berechnet, bis fur jedes Primideal

eine Relation gefunden wurde. Die Anzahl der Relationskandidaten tragen wir inAbhangigkeit von C in der folgenden Graphik ein. Hierbei sind die verschiedenenMepunkte\ durch kleine Kreise markiert. Zum Vergleich wird die durch (4.4)"erhaltene
Kurve grau eingezeichnet.

In Abbildung 4.3 wird deutlich, da eine Faktorbasis fur die Relationensuche zu
gro aber auch zu klein sein kann. Dies wird durch beide Kurven angezeigt.
Die theoretische Kurve verlauft allerdings besonders fur kleine Faktorbasen zu
schlecht. Entsprechend liegt die tatsachlich beste Schranke fur die Faktorbasis
bei 440 wahrend der theoretisch vorgeschlagene Wert ungefahr 630 betragt.
Durch die Untersuchung einiger Relationskandidaten und unter Verwendung von lassen sich also heuristische Schranken nden, so da die aus allen Primidealen mit Norm unterhalb einer solchen Schranke bestehende Faktorbasis untereinigen Annahmen besonders gut zur Klasengruppenberechnung geeignet seinmute. Das obige Beispiel deutet aber schon an, da Ergebnisse relativ ungenau

4.3. DIE FAKTORBASIS

53

2600
2400
2200
2000
1800
1600
1400
1200
500

1000

C

1500

2000

2500

Abbildung 4.3: Tatsachliche und theoretische Anzahlen zu bestimmender Relationskandidaten fur verschiedene Faktorbasisschranken im Vergleichsein konnen (und werden). Immerhin ist die heuristische Schranke 630 im Vergleich zu 440 passabel, wenn man bedenkt, da eine Schranke zwischen 0 und
der Minkowskischranke 119  10 ohne Anhaltspunkte zu wahlen ist. Wir werden
uns im folgenden jedoch nicht auf solche heuristischen Schranken stutzen. Die
Berechnung ist namlich einerseits relativ aufwendig und andererseits verwenden
wir verschiedene Methoden der Relationensuche, die Relationskandidaten unterschiedlicher Smoothnesswahrscheinlichkeiten liefern. Auerdem konnen wir zu
gro angesetzte Faktorbasen mit einem Reduktionsalgorithmus verkleinern.
7

4.3 Die Faktorbasis
Die Idealschranken fur vollstandige Faktorbasen sind fast immer viel zu gro wassowohl die Vollstandigkeit als auch die Eignung zur Relationensuche im Sinne
des Abschnitts 4.2 betri t. Wir werden daher mit kleinen Idealschranken beziehungsweise kleinen Faktorbasen arbeiten, von denen wir zunachst nur annehmenkonnen, da sie vollstandig sind. Diese Faktorbasen sollten also moglichst sobalanciert sein, da die Relationensuche aufgrund geringer Faktorisierungswahrscheinlichkeiten nicht zu schwierig wird, aber aufgrund eines hohen S -Einheitenrangs auch nicht zuviele Relationen zu bestimmen sind. Insbesondere sollten
keine kleinen Primideale fehlen. Es ist naturlich auerdem erforderlich, die

54

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

Vollstandigkeit einer solchen Faktorbasis unter Verwendung korrekter Schranken
zu beweisen.
Die Berechnung der Primideale der Faktorbasis uber einer Primzahl p erfolgt mit
Satz (2.27) Kapitel 6.2 aus [16] und mit dem Berlekamp-Verfahren [15] fur den
Fall, da der Index der Gleichungsordnung in der Maximalordnung nicht von pgeteilt wird. Im Indexteilerfall wird Algorithmus 6.2.9 auf S. 314 in [5] verwendet.
Wir ordnen die Primideale der Faktorbasis ublicherweise so an, da Primidealezu gleichen Primzahlen beieinander stehen und zuerst die Primideale uber groenPrimzahlen, danach die uber kleineren Primzahlen usw. kommen. Man kann auchandere Anordnungen wahlen, vergleiche aber Abschnitt 3.5.

4.3.1 Reduktion einer Faktorbasis
Wir wollen eine Methode beschreiben, mit der eine Faktorbasis, die aus allen
Primidealen mit Norm unterhalb einer Schranke C besteht, verkleinert werdenkann, ohne da sich das Erzeugnis in der Klassengruppe andert. Unsere Methodebasiert auf einer ahnlichen Methode aus [21].

Lemma 4.3.1 Sei S eine Faktorbasis bestehend aus allen Primidealen mit Normkleiner gleich C und R  S . Fur beliebige Primzahlen p de niere m(R; p) =minfN (p) j p 2 S nR und p j pg, wobei das Minimum im Falle einer leeren Menge
als 1 gesetzt wird. Sei q 2 S nR, 2 q und N = N ( =q), so da fur jedes p mit
p j N gilt: pp(N ) < m(R; p) und pp(N )  C . Dann wird q in der Klassengruppe
durch Primideale aus R dargestellt.
Beweis: Gilt p j q , so folgt aus der ersten Bedingung wegen N (p)  pp N ,da p 2 R ist, falls p 2 S gilt. Insbesondere ist p = q nicht moglich. Die
zweite Bedingung fordert p 2 S . Dies zeigt, da =q nur in Primideale aus R
faktorisiert.

1

(

)

Algorithmus 4.3.2 (Reduktion einer Faktorbasis)
Eingabe: Eine Faktorbasis S = fp ; : : : ; psg bestehend aus allen Primidealen mit
Norm kleiner gleich C .

1Ausgabe: Eine evtl. verkleinerte Faktorbasis S 0 mit gleichem Erzeugnis in der
Klassengruppe wie S .
1. (Initialisierung) Setze C 0 minfMK ; 30+ MK4 g, S 0 fp 2 S j N (p)  C 0 g
und R S 0 . Berechne fur jedes Primideal aus S nR eine im Konjugiertengitter des Primideals LLL-reduzierte Basis.
1

4.3. DIE FAKTORBASIS

55

2. (Schwaches Reduzieren) Prufe der Reihe nach fur jedes Primideal p 2 S nR
unter Verwendung der Elemente der vorberechneten LLL-reduzierten Basis von p mit Lemma 4.3.1, ob p sich in der Klassengruppe bereits durch
Primideale aus R darstellen lat, und setze in diesem Fall R R [ fpg.
3. (Wiederhole) Wenn R in Schritt 2 vergroert werden konnte, wiederhole
Schritt 2. Wenn R = S , so Ausgabe von S 0 und terminiere.
4. (Starkes Reduzieren) Prufe der Reihe nach fur jedes Primideal p 2 S nR,
ob es ein Element der LLL-reduzierten Basis von p gibt, so da =p nur in
Primideale aus R faktorisiert, und setze in diesem Fall R R [ fpg.
5. (Wiederhole) Wenn R in Schritt 4 vergroert werden konnte, wiederhole
Schritt 4. Wenn R = S , so Ausgabe von S 0 und terminiere.
6. (Vergroere S 0) Setze C 0 2C 0 , S 0 fp 2 S j N (p)  C 0 g und R
solange, bis sich S 0 vergroert hat. Gehe zu Schritt 4.

R [ S0Im Schritt 4 genugt es, =p nur uber der Faktorbasis zu faktorisieren. Dazu kannman eine leicht abgewandelte Version des weiter unten vorgestellten Algorithmus
4.4.1 verwenden. Hat man einmal solche Faktorisierungen fur ein p berechnet
und fallt p noch nicht fort, so werden sie fur den etwaigen spateren Gebrauch
gespeichert.

Beispiel 4.3.3 Wir betrachten den Zahlkorper K , der durch f (t) = t 7t +117
erzeugt wird. Es gilt r = 2 und log (DK )  10:81. Die Minkowskischranke
5

2

2

10

betragt 15876. Es gibt 1869 Primideale mit Norm unter 15876. Wir wenden Algorithmus 4.3.2 auf die Faktorbasis S an, die aus diesen Primidealen besteht, underhalten ein S 0 mit nur 16 Primidealen. Alle 1853 anderen Primideale konnten
durch dreimalige Ausfuhrung von Schritt 2 fortgelassen werden. Dazu wurden
ungefahr 100 Sekunden benotigt. Die Berechnung der Primideale unterhalb der
Minkowskischranke brauchte zuvor 53 Sekunden.

Zu den angegebenen Zeiten in diesem und allen folgenden Beispielen siehe Kapitel 6. Man konnte nun befurchten, da durch die Reduktion einer Faktorbasis
vorher gute Smoothnesseigenschaften zerstort werden und die Relationensuche
entsprechend erschwert wird. In der Praxis lat sich dies nicht beobachten. Die
beiden Reduktionsschritte hangen selbst von Smoothnesseigenschaften ab und gehen nicht zu grundlich vor. Umso schlechter die Smoothnesseigenschaften sind,umso weniger wird reduziert. Im Beispiel konnen wir ohne Probleme fur die
Klassengruppen- und Einheitenberechnung ausreichend viele S 0-Relationen nden (Algorithmus 4.4.9 benotigt 5 Sekunden).

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

56

4.3.2 Nachweis der Vollstandigkeit

Wir arbeiten ublicherweise mit einer im Vergleich zur Minkowskischranke kleinen
Schranke C , von der wir nur annehmen, da alle Primideale mit Norm unterhalb
dieser Schranke eine vollstandige Faktorbasis bilden. Wir wollen dies algorithmisch bestatigen und brauchen dazu "bewiesene\ Schranken dieser Eigenschaft.
Es gibt eine ganze Reihe solcher bewiesener Schranken. Bekannt aber verbessert ist die Minkowskischranke MK aus Abschnitt 2.5. Eine asymptotisch bessere
Schranke liefert (4.1), S. 45 unter Einsetzen oberer Abschatzungen fur die Hermiteschen Konstanten, siehe [21, 16]. Allerdings tritt die Verbesserung hierdurch
beispielsweise fur total reelle Korper erst ab Grad 36 und fur total komplexe
Korper ab Grad 6 auf. Ist der Grad kleiner gleich 8, so sind die Hermiteschen
Konstanten bekannt und genaue Aussagen moglich. Das Verhaltnis der Schranke(4.1) zu MK schwankt hier ungefahr zwischen 0:5 und 1:5 und kann in [16] nachgelesen werden. Von Zimmert stammen weitere Schranken fur spezielle p
Grade
und Signaturen, siehe z. B. [20], S. 90-91. Alle diese Schranken sind O( DK )mit von n und r abhangiger O-Konstante.
Eine weitere wichtige Schranke ist die Bachschranke
2

BK = 12 log jDK j:
2

Die Primideale mit Norm kleiner gleich dieser Schranke erzeugen die Klassengruppe unter Annahme der verallgemeinerten Riemannschen Vermutung (GRH),
siehe [1]. Diese Schranke ist asymptotisch bedeutend besser als die oben genannten Schranken. Allerdings kommt dies aufgrund des im Vergleich sehr groen
Vorfaktors "12\ erst bei groeren Diskriminanten zum Tragen.
Wir wahlen also eine solche bewiesene Schranke CK und gehen dann wie folgt
vor: Wir durchlaufen mit p alle Primzahlen unter CK der Reihe nach beginnend
bei 2. Fur jedes Primideal p uber p mit C < N (p)  CK suchen wir in p nacheiner Relation der Form
= p  pk1    pkmm ;(4.5)
wobei fur jedes pi entweder N (pi )  C gilt oder bereits ein solches gefunden
wurde: Es ist klar, da damit p "bewiesen\ wird.
Fur ein 2 p konnen wir (4.5) wie folgt hinreichend uberprufen. Wir setzen
Ce = C , falls p  C und Ce = CK sonst. Dann mu fur jede Primzahl q mit
q j N ( =p) gelten, da q  maxfC; p 1g, und fur k = q (N ( =p)) mu qk  Ce
sein. Sind diese Bedingungen erfullt, so gilt (4.5).
Wir fassen diese Bemerkungen im folgenden Algorithmus zusammen:
1

Algorithmus 4.3.4 (Beweis der Vollstandigkeit einer Faktorbasis)
Eingabe: Schranken C; CK mit 0 < C < CK .

4.3. DIE FAKTORBASIS

57

Ausgabe: Bei Termination ist bewiesen, da die Primideale p mit C < N (p) 
CK in der Klassengruppe durch Primideale mit Norm unterhalb C dargestellt werden.
1. (Initialisierung) Setze P
C . Setze p 1.

fq ; : : : ; qk g Liste der Primzahlen kleiner gleich
1

2. (Nachstes p) Setze p nachste Primzahl groer p. Wenn p > CK terminiere. Wenn p  C setze Ce C sonst Ce CK . Sei L fp1 ; : : : ; pmg
Liste der Primideale uber p mit C < N (p)  CK , i 1.
3. (Prufe pi ) Zahle solange 2 pi mit kleiner T2 -Norm aus, bis folgende zwei
Bedingungen erfullt sind: (i) Setze N N ( )=N (pi ). Fur j = 1; : : : ; kund solange N 6= 1 bestimme kj = qj (N ); es mu gelten qjkj  Ce . Setze indiesem Fall N N=qjkj . (ii) Zum Schlu mu gelten N = 1.
4. (Nachstes pi ) Wenn i < m setze i
5. (Fuge p hinzu) Setze qk+1
Schritt 2.

i + 1 und gehe zu Schritt 3.
p, P P [ fqk g, k k + 1. Gehe zu+1

Bemerkungen:
Algorithmus 4.3.4 terminiert nicht, wenn die Schranke C zu klein ist. Seine
Anwendung sollte nach einer Klassengruppenberechnung erfolgen, da dann mit
Hilfe des Eulerprodukts und des S -Einheitentests die Vollstandigkeit der Faktorbasis quasi feststeht. Ein anderer Grund ist, da wegen der teilweise sehr hohen
bewiesenen Schranken CK dieser Algorithmus ein Vielfaches der Zeit einer Klassengruppenberechnung unter Verwendung einer kleinen Faktorbasis benotigt.
In Schritt 3 sehen wir von der Faktorisierung von in Primideale ab und verwenden stattdessen die nur hinreichenden Bedingungen. Auch hierdurch kann es
theoretisch geschehen, da Algorithmus 4.3.4 nicht terminiert. Deswegen ist es
gunstig, bei vielen vergeblichen Versuchen zur genauen Faktorisierung in bereits
getestete Primideale uberzugehen. In der Praxis werden aber bei vielen Beispielen nur wenig darstellende Relationen ubergangen. Dieses Vorgehen bringt zwei
wesentliche Vorteile mit sich. Wir sparen den Speicherplatz fur die Primidealeuber den Primzahlen aus P und pro tieren von der Zeitersparnis.

Beispiel 4.3.5 Wir wollen das Verhalten von Algorithmus 4.3.4 fur ein paar

Zahlkorper untersuchen. Dazu notieren wir in der folgenden Tabelle der Reihe
nach die Werte f , C , CK0 , wobei CK0 eine beliebige, nicht unbedingt bewiesene
Schranke bezeichne, danach die Anzahl s1 der Primideale mit Norm unterhalb C ,die Anzahl s2 der zu testenden Primideale mit Norm unterhalb CK0 , die Anzahl A1
aller in Schritt 3 bestimmten Elemente , die Anzahl A2 der Elemente , fur die

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

58

wir eine Darstellung 4.5 mit bereits bewiesenen Primidealen bei genauer Faktorisierung erhalten hatten, und schlielich die Anzahl A3 von letzteren Elementen,fur die der Test in Schritt 3 (unnotigerweise) nicht zutraf.

f
C CK0 s sA
A A
x x + 22500 15619 93 1729 1731 1729 0
x + 71x 37x + 220 500 36561 97 3845 22218 3946 101
x 21000 3000 163 260 636 262 2
1

2

1

2

3

6

6

5

25

Die Korperdiskriminante des ersten Beispiels besitzt 12 Dezimalstellen. Die Minkowskischranke fallt dadurch nicht zu gro aus; es ist die verwendete Schranke
CK0 . An diesem Beispiel lesen wir ab, da fast jedes erzeugte eine darstellende Relation liefert. Auerdem wird durch den Test nichts verschenkt. Anders
sieht die Situation beim zweiten Beispiel aus. Die Diskriminante besitzt hier 24
Stellen, entsprechend gro ist die Minkowskischranke mit 11 Stellen. Bei derverwendeten Schranke CK0 handelt es sich jetzt um die Bachschranke. Mit dem
Test schneiden wir hier nicht so gut ab. Trotzdem ist das Verhaltnis von A3 zu
A2 noch relativ gut. Die im Vergleich zu s2 hohe Anzahl A1 an Elementen zeigt,da die Schranke C etwas klein gewahlt wurde; wir konnen schlecht faktorisieren.
Die genauere Betrachtung zeigt, da bis zum Zeitpunkt p = 5351 in Algorithmus
4.3.4 ca. 640 Ideale behandelt und aber 11873 Elemente dazu bestimmt wurden.
Von diesen hatten nur 715 verwendet werden konnen, also elen 75 Elementeunnotigerweise durch den Test. Fur diese Ideale wurden demnach durchschnittlich ca. 18 Elemente zur Darstellung benotigt. Fur die restlichen 3205 Ideale
waren dazu dann durchschnittlich nur noch ca. 3 Elemente erforderlich. Entsprechend entfallt ein Groteil der unnotigen negativen Testergebnisse in diesen
Anfangsbereich. Beim dritten Beispiel besitzt die Diskriminante 43, die Minkowskischranke 13 und die Bachschranke 6 Dezimalstellen. Wir verwenden einfach
CK0 = 3000. Der Test funktioniert gut und auch das Verhaltnis s2 zu A1 ist
passabel.
Die Berechnung der zu testenden Primideale aber auch die Berechnung der Kandidaten stellt den zeitlich dominierenden Teil von Algorithmus 4.3.4 dar. Bevor
wir hierfur Zahlen angeben, soll bereits auf Verbesserungen eingegangen werden.

Eine gunstige Berechnung der zu testenden Primideale erhalten wir durch die
folgenden U berlegungen. Nach dem Primzahlsatz gibt es Q (x)  x= log x viele
Primzahlen unterhalb einer Zahl x. Die Anzahl der Primzahlen mit p  x im
Verhaltnis zu Q (x) ist somit ungefahr gleichpQ ( x)  p2 ;Q (x)xalso fur groes x ziemlich gering. Bei einem Groteil der Primideale mit Norm
unterhalb x handelt es sich also um Primideale vom Grad eins. Dies mussen wir
2

4.3. DIE FAKTORBASIS

59

bei der Bestimmung der Primideale p j p, die fast immer durch die Faktorisierungdes den Zahlkorper erzeugenden Polynoms f (t) modulo p geschieht, berucksichtigen. Entsprechend Satz (2.27) Kapitel 6.2 aus [16] sind wir nur an Linearfaktoren
von f (t) modulo p interessiert.

Lemma 4.3.6 Das durchg(t) = ggTp(f (t); tp t)
de nierte Polynom g(t) 2 F p [t] besteht genau aus den Linearfaktoren von f (t)modulo p.

Beweis: Die Behauptung ist klar, wenn man berucksichtigt, da tQ(t a) ist.

t=

p



a2Fp

Durch die Faktorisierung von g(t) mit der Methode von Cantor und Zassenhauskonnen wir nun erheblich schneller die gesuchten Primideale p bestimmen, siehe[15].
Die nachsten U berlegungen richten sich auf die schnellere Generierung der Kandidaten 2 p. Wie schon erwahnt verwenden wir hierfur den Auszahlalgorithmus.
Entsprechend [16] benotigen wir als Eingangsdatum die Grammatrix Ap der T Norm bezuglich einer Basis von p. Aus dieser Matrix wird dann als wesentliche
Vorbereitung eine Cholesky-artige Zerlegung der Form
2

Ap = Qtp Dp Qp(4.6)

berechnet, wobei Qp; Dp 2 R nn , Dp eine Diagonalmatrix mit positiven Diagonalelementen und Qp eine obere Dreiecksmatrix mit Einsen auf der Diagonalen
ist. Die Berechnung dieser Zerlegung fur jedes p mu nicht mit Ap starten, sondern kann auch aus einer solchen Zerlegung der Grammatrix AoK der T -Normbezuglich einer Ganzheitsbasis ! ; : : : ; !n erfolgen, AoK = QtoK DoK QoK in derobigen Form. Ist namlich M 2 Znn eine regulare Matrix, so besitzt die Grammatrix der T -Norm bezuglich der Basis (! ; : : : ; !n) M die Darstellung M t AoK M .
Es existiert nun eine Basis des Primideals p, so da die zugehorige U bergangsmatrix M der Ganzheitsbasis in die Idealbasis in oberer Hermite Normalform
ist. Folglich handelt es sich bei QoK M ebenfalls um eine obere Dreiecksmatrix.
Allerdings hat diese Matrix nicht nur Einsen auf der Diagonalen. Um dies undsomit (4.6) herzustellen, konnen wir QoK M mit einer geeigneten Diagonalmatrix
D0 von links multiplizieren. Wir erhalten Qp = D0 QoK M und Dp = (D0) D.
Durch dieses Vorgehen konnen wir das Gitter, in dem wir auszahlen, nicht mehrdirekt LLL-reduzieren. Dies ist jedoch hau g kein schwerwiegender Nachteil.
Naturlich kann man wenigstens noch von einer LLL-reduzierten Ganzheitsbasis
ausgehen.
2

1

2

1

2

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

60

Beispiel 4.3.7 Wir wenden uns dem zeitlichen Verhalten von Algorithmus 4.3.4

zu. In den folgenden Tabellen notieren wir unter Fortfuhrung obigen Beispiels die
Zeit tp, die fur die Berechnung der Primideale p uber p mit C < N (p)  CK0 und
C < p  CK0 benotigt wurde, die Zeit t , die fur die Berechnung der Kandidaten
samt Initialisierung des Auszahlalgorithmus benotigt wurde, und die Zeit tT , die
die Berechnung der Normen und das Testen dieser Elemente in Anspruch nahm.
In der ersten Tabelle sind die Zeiten ohne Berucksichtigung der geschilderten
speziellen Methoden angegeben. Insbesondere wird hier genau gepruft, ob die
Kandidaten entsprechend (4.5) faktorisieren. Die Angaben sind in Sekunden.

f
tp t
tT gesamtt t + 2234 125 17 176
t + 71t 37t + 220 133 481 184 798
t 2
60 3625 31 3716
6

6

5

25

f
tp t tT gesamt
t t + 22
10 13 225
t + 71t 37t + 220 33 60 133 226
t 2
10 50 9
69
6

6

5

25

Bei diesen Beispielen ergibt sich der grote Teil der zeitlichen Verbesserung durch
die Verwendung der vorberechneten Cholesky-artigen Zerlegung (4.6). Es ist aberzu erwarten, da die spezielle Berechnung der Primideale vom Grad eins unter
Verwendung groerer Idealschranken den Hauptanteil der Verbesserung liefern
wird.

4.3.3 Vorgehensweise in der Praxis

Aufgrund der Beschrankung der Zeilenzahl der Klassengruppenmatrix durch Algorithmus 3.2.3 sollten Faktorbasen im Moment nicht aus mehr als ungefahr 200
Primidealen bestehen. Dies ist gleichbedeutend mit Idealschranken im Bereich
um 1200. Eine solche Idealschranke ist fur die Vollstandigkeit der Faktorbasis in
der Praxis so gut wie immer ausreichend. Dem Verfasser ist kein Beispiel bekannt,
wo nicht eine Schranke von 100 fur die Vollstandigkeit gereicht hatte. Aber auchfur die Relationensuche ist dies hau g vollig ausreichend. Das Beispiel 4.2.4 aus
Abschnitt 4.2 hatte eine 20-stellige Diskriminante, was fur einen Korper vierten
Grades schon relativ gro ist, und fur eine gute Faktorbasis wurde die Schranke
440 ermittelt. Spater wird eine Methode beschrieben, mit der die Wirkung einergroeren Faktorbasis erzielt werden kann.
In der Praxis hat sich das folgende Vorgehen bewahrt: Man wahle eine Schranke
zwischen 100 und 1000 in Abhangigkeit der Groe der Koezienten des erzeugenden Polynoms oder der Diskriminante, und reduziere die daraus resultierende4.4. RELATIONENSUCHE

61

Faktorbasis mit Algorithmus 4.3.2. Dann wendet man die Methoden der Relationssuche aus dem nachsten Abschnitt an, sieht, ob eine Berechnung der Klassengruppe uberhaupt moglich ist und erhalt auch schon ein Ergebnis. Zu einemspateren Zeitpunkt verwendet man dann Algorithmus 4.3.4, um die Vollstandigkeit nachzuweisen.

4.4 Relationensuche
In diesem Abschnitt sollen verschiedene Strategien der Relationengewinnung besprochen werden. Wir arbeiten mit einer fest vorgegebenen Faktorbasis undstutzen uns meist, aber nicht ausschlielich, auf die Smoothnesseigenschaften
der erzeugten Relationenkandidaten. Im nachsten Abschnitt wird sich dies dann
andern.

4.4.1 Test auf S -EinheitFur die Relationensuche wird ein Test benotigt, der pruft, ob ein 2 K eine
S -Einheit ist oder nicht. Da gefundene S -Einheiten an Algorithmus 3.2.3 weitergeleitet werden und dort S ( ) benotigt wird, konnen wir S ( ) auch schon hierberechnen.

Algorithmus 4.4.1 (Test auf S -Einheit)
Eingabe: Eine Faktorbasis S = fp ; : : : ; psg und ein 2 K .
1Ausgabe: "Wahr\ und S ( ), wenn eine S -Einheit ist. Sonst "falsch\.

1. (Initialisierung) Setze P
f p j es gibt ein p 2 S mit p j pg. Fur jedes
p 2 P setze Sp fp j p 2 S und p j pg und Sp0 fp j p 62 S und p j pg.

2. (Aufspalten) Schreibe = =d mit 2 oK und d 2 Z0 minimal.
3. (Sieben) Bestimme N N ( ). Fur jede Primzahl p 2 P setze p p(N )und setze danach N N=p p . Auerdem dp p(d) und d d=pdp . Ist
zum Schlu N 6= 1 oder d 6= 1, so ist keine S -Einheit, Ausgabe "falsch\
und terminiere.
4. (Schleife uber p) Fur jedes p 2 P :5. (Bewertung ) Fur jedes p 2 Sp berechne vp
p( ) und setze p
v
f
(
p
j
p
)
.
Wenn
Null
ist,
gilt
f
u
r
alle
restlichenp, da p( ) = 0ppp
ist. Ist nach Abarbeitung dieser Schritte p nicht Null, aber 2 oK , so
ist keine S -Einheit, Ausgabe "falsch\ und terminiere. Ist 62 oK , fuhrediese Schritte auch noch fur alle p 2 S 0 durch.
p

62

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE
6. (Bewertung d) Wenn dp 6= 0 so setze fur jedes p 2 Sp und dann p 2 Sp0vp vp dpe(p j p).
7. (Nachstes p) Wiederhole ab Schritt 4.
8. (Schlufolgerung) Wenn vp = 0 fur jedes p 2 Sp0 , so ist eine S -Einheit.
Ausgabe wahr\ und S ( ) (vp1 ; : : : ; vps ). Sonst Ausgabe "falsch\. Terminiere. "Die Berechnung von p( ) in Schritt 5 erfolgt mit dem Algorithmus 4.8.17 auf
S. 201 in [5].
Zu diesem Algorithmus ist ansonsten nicht viel zu sagen. Wichtig ist, da NichtS -Einheiten schnell erkannt werden. Wie in Abschnitt 4.2 gesehen, ist der Anteil
an solchen Elementen namlich sehr gro. An Schritt 3 scheitert ublicherweise ein
Groteil der Nicht-S -Einheiten, und bis dahin lauft der Algorithmus schnell ab.
Die Berechung der Bewertungen ist dagegen ziemlich teuer. Weil fur nicht ganzalgebraische Zahlen zusatzlich die Bewertungen an Primidealen aus Sp0 berechnet
werden mussen, versucht man sich bei der Relationensuche nach Moglichkeit auf
ganzalgebraische Zahlen zu konzentrieren.

4.4.2 Schnelle Relationen

Wir beschreiben jetzt eine Methode, mit der man auf schnellem Wege Relationen erhalten kann. Mit Algorithmus 4.4.1 stellt man fest, ob es sich bei einem
Kandidaten um eine S -Einheit handelt oder nicht.

Algorithmus 4.4.2 (Schnelle Relationen)
Eingabe: Eine Faktorbasis S = fp ; : : : ; psg.
1

Ausgabe: S -Relationen

1; ; : : :.
2

1. (Initialisierung) Initialisiere den Auszahlalgorithmus fur jedes Primideal
der Faktorbasis. Setze i 1 und l 1.
2. (Suche) Fahre mit dem Auszahlen von Elementen von pi fort, bis eine S Relation gefunden wurde.
3. (Nachstes pi) Ausgabe von lund setze li 1 sonst i i + 1. Gehe zu Schritt 2.

l + 1. Wenn i = s dann

Der Schritt 2 wird nicht verlassen, bevor nicht eine Relation in pi gefunden wurde.
Dies ist (wenigstens theoretisch) immer moglich, da beispielsweise beliebige Potenzen von pihK Hauptideale liefern, deren Erzeuger durch Auszahlen der Elemente
von pi gefunden werden konnen. Es ist sogar moglich, durch eine endliche Zahl

4.4. RELATIONENSUCHE

63

an von Algorithmus 4.4.2 bestimmten Relationen ganz HKS zu erzeugen. In derPraxis nden sich in pi meist sehr schnell Relationen. Durch dieses Beharren auf
pi wird erreicht, da gefundene Relationen einigermaen unabhangig\ sind. Fur" von s an solchen Relationen, um
viele Beispiele genugt das zwei- bis dreifache
Einheiten und Klassengruppe zu berechnen.
Es gibt aber auch so ungunstig bescha ene Korper, da man mit Algorithmus
4.4.2 aus praktischer Sicht nicht in vernunftiger Zeit zum Ziel kommen kann. Die
bei den folgenden Beispielen angegebenen Zeiten beinhalten auch die Zeit, dievon Algorithmus 3.2.3 benotigt wird.

Beispiel 4.4.3 Wir betrachten den Zahlkorper K , der durch f (t) = t + 2t +8

7

72t 130t 4018t 11504t 136379t +515628t +6454324 gegeben wird. Es giltr = 4 und log (DK )  13:91. Der Regulator betragt ungefahr 4643:02 und die
Klassengruppe ist isomorph zu Z=6Z. Fur die Faktorbasis verwenden wir die 114
Primideale mit Norm kleiner gleich 500. Nach den ersten 112 von Algorithmus
4.4.2 bestimmten Relationen betragt der Rang der Klassengruppenmatrix 60 und
der Rang der Einheitenmatrix 1. Nach weiteren 312 Relationen hat sich nichts
geandert. Bei Relation 548 hat sich der Rang der Klassengruppenmatrix auf 78
erhoht. Wir brechen das Beispiel schlielich "kurz vor Schlu\ bei Rang 113
bzw. 3 nach 1952 Relationen und ungefahr 8500 Sekunden ab.
6

2

5

4

3

2

10

Interessanterweise gibt es bei diesem Beispiel auch fur andere Faktorbasisschranken stets beim Rang der Klassengruppenmatrix von ungefahr s=2 das erste Plateau, an dem der Rang nicht weiter wachst.
Wir bemerken zum Schlu, da man den Initialisierungsschritt mit Hilfe der vorberechneten Zerlegung (4.6), S. 59, | unter Vorbehalt | verschnellern kann,wenn die Konjugiertengitter der beteiligten Primideale nicht zu schlecht konditioniert sind.

Beispiel 4.4.4 Wir betrachten jetzt den Zahlkorper K , der durch f (t) = x +4608 erzeugt wird. Es gilt r = 9 und log( DK )  32:94. Der Regulator betragt
18

2

ungefahr 5682014322:3 und die Klassenzahl ist eins. Fur die Faktorbasis verwenden wir die 62 Primideale mit Norm kleiner gleich 300. Nach 118 Relationen
und 310 Sekunden ist die Klassengruppe und Einheitengruppe bestimmt. Wird
zur Initialisierung des Auszahlalgorithmus fur die Primideale der Faktorbasis auf
die vorberechnete Zerlegung (4.6) zuruckgegri en, so ist die Berechnung nach
182 Relationen und 242 Sekunden zu Ende. O enbar sind die Konjugiertengitter der Primideale schon etwas ungunstiger ausgelegt als zuvor. Trotzdem wird
weniger Zeit benotigt als zuvor. Arbeiten wir bezuglich einer LLL-reduzierten
Ganzheitsbasis von K unter Verwendung der Zerlegung (4.6), so ergibt sich mit
118 Relationen bei 120 Sekunden die schnellste Berechnung.

64

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

4.4.3 Gute Relationen

Wir beschreiben jetzt eine Methode, wie man Relationen gewinnen kann, die eine
gute Unabhangigkeit aufweisen. Von diesen Relationen werden meist nur wenig
mehr als r + s Stuck benotigt, um das S -Einheitengitter zu erzeugen.

Algorithmus 4.4.5 (Gute Relationen)
Eingabe: Eine Faktorbasis S = fp ; : : : ; psg.
1

Ausgabe: S -Relationen

1; : : : ; l.

1. (Initialisierung) Setze S 0 f p j p 2 S und N (p)  minf2 log(jDK j); 51 C gg,
wobei C die zur Herstellung der Faktorbasis verwendete Schranke bezeichne.
Setze a minf5; jS 0jg und b 3. Setze i 1 und l 1.
2. (Suche) Wahle q1 ; : : : ; qa zufallig aus S 0 aus. Wahle zufallige k1 ; : : : ; ka mit
0  kj  b fur 1  j  a. Bestimme das erste Element einer LLLreduzierten Basis von pi Qaj=1 qkj j .
3. (Relation gefunden?) Wenn keine S -Relation ist, so gehe zu Schritt 2.
4. (Nachstes pi ) Wenn bisher nicht gefunden wurde, so Ausgabe von lund setze l l + 1. Wenn der Anteil mehrfach gefundener Relationen 20
Prozent ubersteigt, so terminiere. Wenn i = s so i 1 sonst i i + 1.
Gehe zu Schritt 2.

Die Groe von S 0 und die Konstanten des Initialisierungsschritts und derTerQaminationsbedingung sind heuristisch gewahlt. Fur die Idealgewichte j qkj jmu man einen Kompromi zwischen dem Aufwand ihrer Berechnung und ihrer
Vielfaltigkeit nden. Insbesondere sollte S 0 nicht zu klein sein. Es ist namlich
denkbar, da fur samtliche Kombinationen in Schritt 2 keine S -Einheit oder nur
wenige verschiedene gefunden werden konnen. Dies wird umso unwahrscheinlicher, je groer S 0 ist. Ein zu groes S 0 fuhrt allerdings zu schlechteren Faktorisierungseigenschaften der Relationskandidaten. Durch den Algorithmus konnen
im ubrigen nur endlich viele verschiedene Relationskandidaten erzeugt werden,
so da ein geeignetes Abbruchkriterium hinzugefugt werden mu.
Eine Moglichkeit, die Anzahl der Kandidaten fur S -Einheiten im Schritt 2 zu
erhohen, besteht in der Gewichtung der T -Norm beziehungsweise der Gewichtung
der Vektoren des Konjugiertengitters, in dem die LLL-Reduzierung vorgenommen
wird. Dies scheint zumindest theoretisch auch den Vorteil mit sich zu bringen,da ungunstige Ein usse schlecht konditionierter Einheiten ausgeglichen werdenkonnen. Schlielich suchen wir Elemente auf Norm achen zu moglichst kleinen
Normen, und diese Elemente konnen bezuglich der ungewichteten T -Norm auch"weit drauen\ liegen.
=1

2

2

4.4. RELATIONENSUCHE

65

Die Berechnung der Idealgewichte ist besondersk fur groeren Grad n ziemlich
zeitaufwendig. Man kann zwar die Potenzen qj j zum Anfang auf Vorrat berechnen, dies bringt aber nicht sehr viel. Die meisten Primideale liegen in 2Elementdarstellung vor und lassen sich somit sehr leicht potenzieren. Die einzelnen Potenzen setzen wir dann sukzessive durch Idealmultiplikation eines Ideals
in Z-Basisdarstellung mit einem Ideal in 2-Elementdarstellung zusammen. Zu
diesen verschiedenen Idealdarstellungen siehe [16, 15].
Auerdem darf bei der Zeitkomponente nicht vergessen werden, da in jedem
Suchschritt das Gitter erzeugt und eine LLL-Reduktion durchgefuhrt werdenmu.
Beispiel 4.4.6 Wir testen Algorithmus 4.4.5 an dem Zahlkorper aus Beispiel
4.4.3. Nach 117 Relationen hat die Klassgruppenmatrix den maximalen Rang
114 und die Einheitenmatrix den Rang 3. Allerdings ist der korrespondierende S Einheitenindex laut Eulerprodukt noch nicht eins. Es werden weitere 5 Relationenbenotigt, um diesen Index zu eins zu machen. Die Berechnung benotigt insgesamt
ungefahr 192 Sekunden.
Fur dieses Beispiel ist es also quasi unerlalich, die Relationensuche mit Algorithmus 4.4.5 durchzufuhren. Umgekehrt ist es bei dem anderen Beispiel.
Beispiel 4.4.7 Wir probieren jetzt Beispiel 4.4.4 mit Algorithmus 4.4.5 aus. Als
Schranke fur S 0 verwenden wir 60, was 15 Primideale liefert. Nach 73 Relationen
und 462 Sekunden ist die Berechung beendet. Die Verwendung eines groeren S 0fuhrt zu erheblich langeren Zeiten.

4.4.4 Gezielte Relationen

Bei der Relationensuche | besonders bei Algorithmus 4.4.2 | stellt man fest,da es gegen Ende immer schwieriger wird, von den bisherigen Relationen unabhangige Relationen zu nden. Die Klassengruppenmatrix ist dann nicht mehr
weit von einer unteren Dreiecksmatrix mit Eintragen ungleich Null auf der Diagonalen entfernt. Fur manche Primideale gibt es aber noch keine eigene Stufe. Eine
Idee konnte sein, gezielt nur in diesen Primidealen nach Relationen zu suchen, inder Ho nung, eine neue Stufe in der Klassengruppenmatrix zu erzeugen. Es zeigt
sich allerdings, da bei Verwendung von Algorithmus 4.4.2 die Einschrankung nur
auf diese "Nichtstufenideale\ ungunstig ist. Die Laufzeiten liegen meist hoher als
vorher und es scheint, als ware die beste Vorgehensweise, die Informationen aus
allen Primidealen der Faktorbasis "gleichmaig herauszuholen\. Immerhin hangt
es auch von der Anordnung der Faktorbasis ab, ob ein Primideal ein "Stufen-\oder "Nichtstufenideal\ ist.
Auf die Laufzeit wirkt sich mitunter auch die folgende Situation ungunstig aus:
Die Klassengruppenmatrix ist regular, aber die Determinante ist noch ein Vielfaches der Klassenzahl. Dies bedeutet, da ein oder mehrere Diagonalelemente zu

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

66

gro sind und man konnte nun speziell in den korrespondierenden Primidealennach Relationen suchen, um kleinere Diagonalelemente zu erhalten. Dies erweist
sich als gunstig, wenn man (unter Umstanden) auf Idealgewichte wie in Algorithmus 4.4.5 zuruckgreift. Da meistens nur sehr wenige Diagonalelemente ungleich
1 sind, fallen etwaige Nachteile von Algorithmus 4.4.5 nicht sehr ins Gewicht.

Beispiel 4.4.8 Wir betrachten den Zahlkorper K , der durch f (t) = t +3t 5t9

8

7

6t +9t +5t 25t 50t+45 erzeugt wird. Es gilt r = 3, r = 3 und log( DK ) 
21:97. Der Regulator betragt ungefahr 146323318:14 und die Klassenzahl ist 1.
Fur die Faktorbasis wahlen wir eine Schranke von 300. Dies liefert 76 Primideale.
Mit Algorithmus 4.4.5 sind wir nach 82 Relationen fast am Ziel: der Regulator
ist schon berechnet und die Klassengruppenmatrix hat Determinante 2. Aber erst
nach weiteren 59 Relationen und insgesamt 443 Sekunden wird die Determinante
1. Durch Auszahlen in dem verantwortlichen Primideal hatten dafur 4 weitere
Relationen genugt.
5

4

3

2

1

2

4.4.5 Kombination der verschiedenen Strategien

Die beschriebenen Strategien waren fur die Relationensuche bei manchen Korpern
von Vorteil, bei anderen aber auch von Nachteil. Wir wollen jetzt eine Kombination dieser Strategien mit Ruckkopplung zu Algorithmus 3.2.3 beschreiben. Die
Schritte 2-4 des Klassengruppenverfahren 3.7.1 werden zu einem Unteralgorithmus zusammengefat:

Algorithmus 4.4.9 (Relationensuche)
Eingabe: Eine Faktorbasis S = fp ; : : : ; ps g und das approximierte Eulerprodukt
1

EPK (x).
Ausgabe: S -Relationen ; : : : ; m, die Klassengruppenmatrix H , die Relationsbasismatrix B , die Einheitenmatrix U , und laut Eulerprodukt die
korrekte Klassenzahl hK und der korrekte Regulator RK .
1

1. (Initialisierung) De niere das Idealgewicht a oK . Initialisiere den Auszahlalgorithmus fur jedes Ideal pa mit p 2 S . Setze i 0, m 0 und
t 0. Initialisiere auch Algorithmus 3.2.3.
2. (Neues Idealgewicht?) Wenn t > 10 oder wenn t > 4 falls sowohl H
den Rang s und U den Rang r besitzen, so setze t 0 und bestimme
ein neues Idealgewicht a durch Berechnung eines zufalligen Produkts wie in
Algorithmus 4.4.2.
3. (Wahle Primideal) Wenn der Rang von H gleich s und der Rang von U
gleich r ist und wenn auf der Diagonalen von H ein Eintrag groer 1 steht,dann wird i die Nummer der nachsten Zeile unter der i-ten Zeile von H ,4.4. RELATIONENSUCHE

67

in der sich ein Diagonalelement groer 1 be ndet. Gibt es keine solche
Zeile mehr, dann wird i die Nummer der obersten Zeile in H mit einem
Diagonalelement groer 1. Tri t aber eine der obigen drei Bedingungennicht zu, so setze i i + 1 und wenn i > s setze i 1.
4. (Suche Relation) Wenn der Auszahlalgorithmus fur pi a noch nicht initialisiert wurde, so geschieht das jetzt. Fahre mit dem Auszahlen in pia fort,
bis eine Relation gefunden wurde. Setze m m + 1 und m.
5. (Auswerten der Relation) Mit Algorithmus 3.2.3 wird die neue Relation
unter Berucksichtigung der bereits berechneten Relationen ausgewertet. Wirsetzen t t + 1, wenn sich weder der Rang von H noch der Rang von U
noch der S -Einheitenindex | wenn endlich | verandert haben.
6. (Testen der Abbruchbedingung) Wenn der S -Einheitenindex nicht endlichoder laut Eulerprodukt nicht 1 ist, so gehen wir zu Schritt 2.
7. (Ausgabe) Die erforderlichen Daten sind berechnet und konnen ausgegeben
werden. Terminiere.

Informell und nicht ganz korrekt gesagt handelt es sich also bei Algorithmus 4.4.9
zunachst um Algorithmus 4.4.2, und wenn dieser keine guten Relationen bringt,
geht man zu Algorithmus 4.4.5 oder zur gezielten Suche wie beschrieben uber.
Wieder sind die Konstanten in Schritt 2 heuristisch gewahlt. Wenn sich nach 10
beziehungsweise 4 Relationen nichts verandert hat, wird ein neues Idealgewicht
berechnet. Man konnte diese Konstanten auch wahrend des Algorithmus furjedes neue Idealgewicht um einen gewissen Wert bis zu einer gewissen unteren
Schranke heruntersetzen und so erreichen, da bei Beispielen wie 4.4.3 hau ger
neue Idealgewichte berechnet werden.
Primzahlen, uber denen nur Primideale der Faktorbasis liegen, sind Relationen,
die wir "umsonst\ bekommen. Diese sollten bereits im Initialisierungsschritt
berucksichtigt werden. Entsprechend emp ehlt es sich, im Suchschritt nur Relationskandidaten zuzulassen, die keine ganzrationalen Zahlen sind. Hat man eine
Relation gefunden, so ist es gunstig zu prufen, ob diese Relation schon einmal
gefunden wurde.

Beispiel 4.4.10 Wir wenden Algorithmus 4.4.9 auf die drei obigen Beispiele

unter Benutzung einer LLL-reduzierten Ganzheitsbasis und der vorberechneten
Zerlegung (4.6) an. Fur Beispiel 4.4.4 ergeben sich unverandert 118 Relationen
nach 120 Sekunden. Fur Beispiel 4.4.3 ergeben sich 142 Relationen nach 59
Sekunden und fur Beispiel 4.4.8 bekommen wir 99 Relationen nach 40 Sekunden.

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

68

4.4.6 Relationen aus dem Number Field Sieve

Die bisherigen Methoden der Relationengewinnung beruhten im wesentlichen auf
der Bestimmung von Elementen kleiner T -Norm in geeigneten Idealen. Durch die
Ungleichung zwischen arithmetischem und geometrischem Mittel wurde gewahrleistet, da die Normen der entsprechenden algebraischen Zahlen klein blieben.
Ein anderer Ansatz der Relationengewinnung wird im Number Field Sieve verwendet. Beim Number Field Sieve handelt es sich um die zur Zeit asymptotischbeste Methode zum Faktorisieren groer ganzer Zahlen. Beschreibungen dieses
Verfahrens sind zu nden in [10], [5], [15]. Die Methode der Relationengewinnung, die jetzt beschrieben wird, ist nicht so universell einsetzbar wie die bisherigen Methoden, und ist als Erganzung gedacht. Man kann damit manchmal auf
schnellem Weg einige gute Relationen dazubekommen. Eine besondere Starke
scheint diese Methode in Verbindung mit der Methode der Ausnahmeprimidealeaus dem nachsten Abschnitt bei zufallig erzeugten Korpern kleinen Grades undgroer Diskriminante zu entfalten.
2Satz 4.4.11 Sei 2 K und m (t) das zugehorige Minimalpolynom aus [t].
Dann ist der Normbetrag von a + b fur ganze Zahlen a; b 2 mit b =6 0 durch
jNK=Q (a + b )j = bnjm ( a=b)j K Q
Q

Z

[

:

( )]

gegeben.

Beweis: Setze d = [ ( ) : ] und d = [K : ( )]. Das Minimalpolynom von
1

Q

Q

Q

2

a + b ist bd1 m ((t a)=b). Folglich NQ =Q (a + b ) = ( b)d1 m ( a=b). Unter
Beachtung der Transitivitat der Norm erhalt man
jNK=Q (a + b )j = jNQ =Q (a + b )jd2 = bnjm ( a=b)jd2 :
( )

( )



Satz 4.4.12 Sei 2 K mit K = ( ). Seien a; b 2 teilerfremd mit b 6= 0.
Jedes Primideal p mit a + b 2 p ist vom Grad eins oder teilt den Index f = (oK :QZ[ ]). Teilt p den Index nicht, so liegt a + b in keinem weiteren Primideal uberderselben Primzahl wie p.

Z

Beweis: Sei p die Primzahl von p. Wir wissen p b, denn sonst a 2 p \ = p
und a; b nicht teilerfremd. Wir nehmen nun an, da p f , und wahlen c; d 2
mit bc  1 mod p und fd  1 mod p. Dann ist  ac mod p. Fur x 2 oK ist
fx 2 [ ], also etwa fx = g( ) mit g(t) 2 [t] und weiter x  dg( ac) mod p.
Somit ist jedes Element aus oK zu einem Element aus f0; 1; : : : ; p 1g kongruent
-

Z

-

Z

Z
Z

Z

modulo p und die erste Behauptung bewiesen. Ist q ein weiteres Primideal uber
p mit a + b 2 q, so wahlen wir oben speziell ein x 2 pnq. Wegen x  dg( ac) 
0 mod p folgt pjdg( ac). Wegen x  dg( ac) 6 0 mod q folgt aber p - dg( ac).
Dies ist ein Widerspruch und die zweite Behauptung bewiesen.
4.5. AUSNAHMEPRIMIDEALE

69

Algorithmus 4.4.13 (NFS Relationen)
Eingabe: Eine Faktorbasis S sowie 2 K mit K = ( ) und a; b 2  .
QAusgabe: S -Relationen

1

Z

1

; : : : ; m.

1. (Initialisierung) Setze klynom von .

1, la und m0. Berechne das Minimalpo-

2. (Relation gefunden?) Wenn a und b teilerfremd sind, prufe unter Zuhilfenahme von Satz 4.4.11, ob l + k eine S -Relation ist. Wenn ja, m m +1
und Ausgabe von m l + k .
3. (Nachster Kandidat) Wenn l > a, setze l l 1 und gehe zu Schritt
2. Sonst setze l a und k k + 1. Wenn k  b gehe zu Schritt 2.
Terminiere.

Die Relationskandidaten, die von diesem Algorithmus erzeugt werden, habenkeine besonders kleine Norm mehr. Daher mussen groe Faktorbasen verwendet
werden, um uberhaupt Relationen zu erhalten. Entsprechend mehr Relationen
sind naturlich zu nden. Die Philosophie hinter Algorithmus 4.4.13 ist, moglichst
viele Kandidaten moglichst schnell durchzutesten. Dies steht im Gegensatz zu
Algorithmus 4.4.5, bei dem mit Zeitaufwand Relationskandidaten moglichst kleiner Norm erzeugt werden. Algorithmus 4.4.2 steht unter dieser Betrachtungsweise zwischen beiden letzteren Algorithmen. Die Verwendung groer Faktorbasen stot jedoch bei Klassengruppenberechnungen im Gegensatz zum Number
Field Sieve auf ein unangenehmes Problem. Es wurde bereits erwahnt, da die
Berechnung der Hermite Normalform und der Transformationsmatrizen fur groe
Faktorbasen schnell zu aufwendig wird. Algorithmus 4.4.13 ist daher nicht ohne
Verwendung von Algorithmus 4.5.1 aus dem nachsten Abschnitt einsetzbar. Wir
geben auch dort erst ein kombiniertes Beispiel zur NFS Relationensuche. Es
sei noch vorausgreifend angemerkt, da sich Algorithmus 4.4.13 (momentan) nur
fur kleine Grade | ungefahr n  5 | eignet. Die beteiligten Normen wachsenublicherweise sehr stark mit n an, groe meist doppelte Ausnahmeprimfaktoren
treten auf. In entsprechendem Volumen ist die Relationensuche durchzufuhren,
wobei die Faktorbasis trotz Verwendung von Algorithmus 4.5.1 ziemlich, beziehungsweise zu gro sein mu. Damit zerschlagt sich auch die Ho nung, aus derbesonders bei groeren Graden gunstigen Berechnung der Normen der NFS Relationskandidaten Pro t zu schlagen.

4.5 Ausnahmeprimideale
Wie in Abschitt 4.3 erlautert liegen sinnvolle Faktorbasisschranken aufgrund der
Einschrankung durch Algorithmus 3.2.3 maximal bei ungefahr 1200. Bei festem

70

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

Grad n und fester Schranke fur die Faktorbasis aber wachsender Diskriminante
werden die Smoothnesseigenschaften der Relationskandidaten rasant schlechter,entsprechend dem Verhalten der Kurven in Abbildung 4.3, S. 53, fur fallendes
C . In dieser Situation konnen wir uns mit der Methode der Ausnahmeprimideale
helfen. Die Idee dieser Methode basiert auf der Beobachtung, da relativ hau g
Relationskandidaten nur deshalb keine Relationen sind, weil ein zu groes Primideal in einfacher Potenz in ihnen aufgeht. Findet man zwei Relationskandidaten
und , in denen dasselbe groe Primideal aufgeht, so kurzt sich dieses Ausnahmeprimideal bei Division heraus und = ist eine Relation. Die durch "relativhau g\ angegebene Wahrscheinlichkeit hangt (vermutlich) unter anderem von derGroe der Diskriminante ab und wird fur beliebig groe Diskriminante beliebig
klein werden. Entsprechend kann diese Methode kein vollwertiger Ersatz fur einegroere Faktorbasis sein.

Algorithmus 4.5.1 (Relationensuche mit Ausnahmeprimidealen)
Eingabe: Eine Faktorbasis S und eine Schranke Ce > 0.
Ausgabe: S -Einheiten 1 , 2 , : : : .
1. (Initialisierung) Setze Se fg und l 0.
2. (Suche) Suche mit einer beliebigen Methode einen ganzalgebraischen Kandidaten fur eine S -Relation.
3. (Relation gefunden?) Wir testen mit Algorithmus 4.4.1, ob eine S Relation ist, und merken uns den Rest N der Norm von nach dem Siebschritt. Wenn eine S -Relation ist, so l l + 1, Ausgabe von lundgehe zu Schritt 2.
4. (Ausnahmeprimideal?) Wenn N > Ce oder N keine Primzahl ist, so gehezu Schritt 2.
5. (Eliminieren) Prufe fur jedes Paar (N; ) 2 Se, ob = eine S -Einheit undnicht rational ist. Wenn ja, so l l + 1, Ausgabe von l= und gehezu Schritt 2.
6. (Hinzufugen) Setze Se

Se [ f(N; )g und gehe zu Schritt 2.

Die Menge Se kann als dynamische Erweiterung der Faktorbasis angesehen werden. Ist (p; ) 2 Se, so wird durch und p eindeutig ein Primideal gekennzeichnet. Se wachst wahrend der Relationensuche und in Abhangigkeit der gefundenen
Kandidaten. So ist es moglich, da man eine erweiterte Faktorbasis erhalt, die
nur aus "wesentlichen\ Primidealen besteht. Auf der anderen Seite wird man
bei sehr groen Diskriminanten gar keine Erweiterung bekommen, weil sich keine
geeigneten Elemente (und besonders keine Relationen) nden lassen.

4.5. AUSNAHMEPRIMIDEALE

71

U ber die Wahl der Schranke Ce, die einer Schranke fur die Faktorbasis entspricht,konnen wir keine genauen Angaben machen. Sicher ist nur, da sie wie bei einer
normalen Faktorbasis nicht zu gro sein darf, denn dann wird Se bei groen
Diskriminanten zu gro, und auch nicht zu klein, sonst wird die Relationensuche
nicht ausreichend
unterstutzt. Ein erster Ansatz ist, Ce in der Groenordnung
12
von MK zu wahlen.
Algorithmus 4.5.1 kann zu verschiedenen Methoden der Relationsuche hinzugeschaltet werden. Der Einsatz lohnt sich erst bei schlechten Faktorisierungseigenschaften der Relationskandidaten bzw. groeren Diskriminanten.
Bei der praktischen Umsetzung von Algorithmus 4.5.1 mu darauf geachtet werden, da eine moglichst groe Zahl an Relationskandidaten in moglichst kurzer
Zeit verarbeitet wird. Dies ist ganz wesentlich, weil man von einer sehr geringen
Wahrscheinlichkeit ausgeht, Ausnahmeprimidealtre er zu erzielen. Wir lterndaher die Nichtrelationen zunachst mit der Bedingung N > Ce. Danach fuhren
wir ein paar nur notwendige Tests mit Miller-Rabin [5], S. 414, durch, ob N einePrimzahl ist. Dies geht erheblich schneller als der genaue Test, und es bringt
keinen Nachteil, sollte einmal ein nichtprimes N durchrutschen. Anschlieend
mu in Se nach den Paaren mit vorderem Eintrag N gesucht werden. Es ist
gunstig, diese Paare von vorneherein zu einem Tupel zusammenzufassen. Fur Se
brauchen wir also eine Suchstruktur | Suchschlussel ist N |, die darauf ausgelegt ist, moglichst schnell Elemente zu nden und einzufugen. Hierfur bieten
sich beispielsweise 2-3-4-Baume an, siehe [8] S. 533 . Im Eliminationsschritt
schlielich gehen wir wie folgt vor: Sind (N; ); : : : ; (N; m) 2 Se und neu, so
berechnen wir der Reihe nach = ; : : : ; = m und bestimmen den jeweils minimalen positiven ganzrationalen Nenner di, 1  i  m. Gilt N - di fur ein i, so ist= i eine S -Einheit, sofern N prim ist. Wenn es kein solches i gibt, dann wirdin Se unter N aufgenommen.
1

1

Beispiel 4.5.2 Wir betrachten den Zahlkorper K , der von f (t) = t +213421t
4

317777t + 7676768 erzeugt wird. Die Signatur ist (2; 1) und es gilt log ( DK ) 
35:31, weiter per Eulerprodukt log (RK )  15:96, ClK ' Z=6Z. Fur die Faktorbasis verwenden wir als Schranke 1000, was 153 Primideale vom Grad 1 und
7 Primideale groeren Grades liefert. Ce wird auf 10 gesetzt. Fur die Relationensuche greifen wir zuerst auf NFS Relationen mit a = 3000 und b = 1000 und=  zuruck. Hiermit konnen wir hochstens den Rang 153 erreichen, tun diesauch nach 170 Relationen, 719233 Relationskandidaten und 3900 Sekunden. Der
Rang der Einheitenmatrix ist zu diesem Zeitpunkt bereits 2. Nun benutzen wir
Algorithmus 4.4.9 und erhalten nach weiteren 19 Relationen, 819695 Relationskandidaten und 6700 Sekunden die volle Klassengruppenmatrix vom Rang 160.
Das mit Hilfe von hK und RK berechnete Residuum der Zetafunktion K dividiert durch die Approximation des Eulerprodukts EPK (1000) ergibt einen Wert
von 1:0055.
2

10

10

8

72

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

Nach der NFS Relationensuche enthalt Se 9260 Primzahlen und 9406 Elemente.
707426 Nichtrelationen wurden nicht naher betrachtet, weil ihr N groer als Cewar. Dann elen weitere 2297 Nichtrelationen durch den Primzahltest. Ubrig
blieben 9510 Elemente, von denen 250 zu Tre ern gemeinsamer Primzahlen fuhrten. Aus diesen konnten durch Elimination des Ausnahmeprimideals 104 S Relationen gewonnen werden. Von diesen 104 Relationen war keine rational.
Bei der anschlieenden normalen Relationensuche passieren ungefahr 2150 von
819695 Nichtrelationen den Test N  Ce. Ungefahr 400 davon scheitern am
Primzahltest. Die restlichen 1750 liefern Tre er gemeinsamer Primzahlen, undvon diesen werden 500 neu in Se aufgenommen. Bei den restlichen 1250 Elementen wird das Ausnahmeprimideal eliminiert. Aber bis auf 18 Stuck sind alle dieseRelationen rational.

Die Verwendung der NFS Relationen und die Berucksichtigung von Ausnahmeprimidealen liefern einen entscheidenden Beitrag zur Klassengruppenberechnung
dieses Korpers. 90 Prozent der benotigten Relationen kommen wahrend der NFS
Relationensuche in einem Drittel der Gesamtzeit zustande. Ungefahr 60 Prozent
der wahrend der NFS Relationensuche gefundenen Relationen und 95 Prozent derwahrend der normalen Relationensuche gefundenen Relationen werden durch Elimination von Ausnahmeprimidealen erzeugt. U brigens wird die Klassengruppe
schon von den 153 Primidealen ersten Grades unter 1000 erzeugt, so da wir uns
auch nur auf NFS Relationen hatten beschranken konnen.
Algorithmus 4.5.1 kann variiert werden. Eine Idee besteht darin, anstelle eines
zwei (oder mehrere) Ausnahmeprimideale zuzulassen. Man wurde dazu auf den
Primzahltest verzichten. Wie sich zeigt, verschlechtert sich dann die Laufzeit. Es
ist ein Mehraufwand zu betreiben, der sich nicht rentiert. Die Wahrscheinlichkeit, da die Ausnahmeprimideale zweier Elemente ubereinstimmen, ist namlich
extrem gering (man kann sie vermutlich ungefahr als Quadrat der Wahrscheinlichkeit, da nur ein Ausnahmeprimideal ubereinstimmt, ansetzen). A hnliches wirdin [10], S. 34, berichtet. Ein Test an unserem Beispiel zeigt, da keine einzige
Relation durch Elimination doppelter Ausnahmeprimideale gewonnen wird.
Eine weitere Idee besteht darin, in Se zwar nur Elemente mit einem Ausnahmeprimideal aufzunehmen, aber zu versuchen, aus Elementen mit zwei oder mehreren Ausnahmeprimidealen diese Ideale zu eliminieren. Diese Idee hat zwei Nachteile. N mu faktorisiert werden, um die einzelnen Primbestandteile in Erfahrungzu bringen. Einerseits wird der Durchsatz an Kandidaten vermindert und andererseits mit Se die Eliminationswahrscheinlichkeit vergroert. Fur obiges Beispiel wiegt ersteres schwerer und unter dem Strich verlangert sich die Laufzeit.
Der zweite Nachteil besteht darin, da gefundene S -Relationen schlechter konditioniert sind und in Algorithmus 3.2.3 eine groere Prazision erfordern. Man
kann diese Idee mit Algorithmus 4.5.1 durch Einfuhrung einer weiteren kleinen

4.5. AUSNAHMEPRIMIDEALE

73

Schranke, unterhalb derer N dann faktorisiert werden wurde, verbinden. Dieskonnte vielleicht gunstig sein, es liegt aber keine Praxiserfahrung vor.

4.5.1 Verbindung zur Methode der reduzierten Ideale

Die Methode der reduzierten Ideale besteht darin, zu zufallig erzeugten ganzen
Idealen a ; a ; : : :, die nur in Primideale der Faktorbasis faktorisieren, bezuglich
der T -Norm sehr kurze Elemente 2 a ; 2 a ; : : : zu nden. Dies geschieht
am besten mit dem LLL-Algorithmus. Die ganzen Ideale =a ; =a ; : : : habendann beschrankte Norm und bei ausreichender Anzahl mu es daher l; k geben
mit l =al = k =ak . Folglich ist l = k eine S -Einheit. Die Methode wird genau
in [20] beschrieben.
Wie wir gesehen haben, besteht bei nicht zu groer Diskriminante meist eine
gute Wahrscheinlichkeit, da bereits viele der i selbst S -Einheiten sind. Umso
groer die Diskriminante wird, umso hau ger treten aber in i =ai Ausnahmeprimideale auf. Im obigen Beispiel ist das (fast) immer der Fall. Eine Gleichung bereinstimmung der Ausnahmeprimideale (ini =ai = j =aj bedeutet nun eine Ugleicher Potenz) sowie eine Ubereinstimmung des Anteils, der durch Primideale
aus S geliefert wird. Aufgrund der obigen U berlegungen und des Beispiels kannman davon ausgehen, da U bereinstimmung der Ausnahmeprimideale im wesentlichen nur dann auftritt, wenn nur ein Ausnahmeprimideal in i und j vorhanden ist. In diesem Fall hatten wir unter Eingabe von i und j in Algorithmus
4.5.1 durch Elimination eine Relation erhalten, vorausgesetzt, Ce ist gro genug.
Fur die Gleichheit i=ai = j =aj mu aber noch der S -Anteil ubereinstimmen,
um wie oben eine Relation zu bekommen. Diese U berlegungen zeigen, da die
Methode der reduzierten Ideale im wesentlichen durch Algorithmus 4.4.5 kombiniert mit Algorithmus 4.5.1 abgedeckt wird und da letztere vermutlich fur
die Relationensuche sogar gunstiger sind. Immerhin benotigt die Methode derreduzierten Ideale eine gewisse Vorlaufzeit, bis aufgrund ausreichend vieler gespeicherter Ideale Relationen gefunden werden konnen. Gegenuber Beispielen
aus [20] ergeben sich fur die Relationensuche unter Verwendung von Algorithmus 4.4.9 statt Algorithmus 4.4.5 tatsachlich Verschnellerungen um Faktoren im
Bereich 100-1000.
Nach demselben Prinzip, wie die Methode der reduzierten Ideale, funktioniert
auch die Relationenerzwingung von v. Schmettow, siehe hierzu [21]. Grob gesagt
werden zu einem vorgegebenen Primideal p ganze Ideale a ; a ; : : : beschrankter
Norm und algebraische Zahlen ; ; : : : mit iai = pi bestimmt. Bei ausreichender Anzahl gibt es l > k mit pl k = l = k . Bei Beispiel 4.5.2 liegen die Werte
solcher l fur ein paar Primideale getestet im Bereich 2000-5000. Hier ist alsoauch eine gewisse Vorlaufzeit notig, die allerdings im Vergleich mit den obigen
Werten relativ klein erscheint. Wir verwenden diese Methode jedoch nicht fur
unser auf das Eulerprodukt gestutzte Klassengruppenverfahren. Man erhalt zwar
1

2

2

1

1

2

1

2

2

1

1

1

2

2

2

74

KAPITEL 4. FAKTORBASIS UND RELATIONENSUCHE

eine Klassengruppenmatrix vom Rang s, aber die Determinante ist bei groeren
Beispielen ein enormes Vielfaches der eigentlichen Klassenzahl, und es sind nochahnlich viele Relationen wie ohne Zuhilfenahme der Relationen l = k = pl k zu
nden, bis die Determinante gleich der Klassenzahl bzw. der Rang gleich s wird.
Auerdem kann l k fur eine Potenz ziemlich gro werden (bei Beispiel 4.5.2 im
Tausender-Bereich), so da die Relationen dann riesige Eintrage besitzen, und es
werden auch keine Einheiten geliefert.

Kapitel 5
Anwendungen
In diesem Kapitel werden zwei Anwendungen vorgestellt, welche die wahrend einer Klassengruppenberechnung ermittelten Daten benutzen. Diese Daten sindkonkret eine vollstandige Faktorbasis S , Relationen ; : : : ; k , welche das ganze
S -Einheitengitter erzeugen, und die Ausgaben von Algorithmus 3.2.3 fur die Faktorbasis und diese Relationen.
1

5.1 Die Klasse eines Ideals
In diesem Abschnitt soll beschrieben werden, wie die Klasse eines gegebenen
Ideals a bestimmt werden kann. Genau gesagt ist die Darstellung von a der
Form
m
Y
(5.1)
a=
aki i
i=1

gesucht, wobei entsprechend (3.1), S. 19, die ai Erzeuger der zyklischen Faktoren
der Klassengruppe der Ordnungen ci sind und 2 K , 0  ki < di fur 1  i  m
gilt.
Wir gehen in zwei Schritten vor. Zuerst ermitteln mit den Methoden des letzten
Kapitels ein 2 a, so da11=a = (p ; : : : ; ps) v

(5.2)

1

mit v 2 Zs gilt, also =a uber der Faktorbasis vollstandig faktorisiert. Diese Darstellung ubersetzen wir im zweiten Schritt in eine Darstellung uber (a ; : : : ; am),wobei ein weiteres 2 K dazukommt.
Zur Erreichung des zweiten Schritts folgen wir zunachst genau dem Vorgehen aus
Abschnitt 3.5, jedoch ohne die Diagonalelemente gleich 1 aus H herauszukurzen.
Dies entspricht einer Verkleinerung der Faktorbasis, und es wurde den ersten
Schritt unnotig schwierig machen, wahlte man diese Faktorbasis. Naturlich ist es
1

1

2

75

KAPITEL 5. ANWENDUNGEN

76

auch moglich, eine Zwischenlosung zu wahlen; die nachfolgenden U berlegungenverlaufen dann ganz analog.
Wir bilden also die Smith Normalform S der unverkleinerten s  s Matrix H
und erhalten unimodulare Matrizen U und V , so da(p ; : : : ; ps) U S = ( ; : : : ; m ) B V:
1

1

(5.3)

1

An U , V sollen gleich noch Bedingungen gestellt werden.
Die Anzahl der Diagonalelemente ungleich 1 von S stimmt mit m uberein. Bezeichne S 0 die m  m Teilmatrix von S , die genau alle Diagonalelemente ungleich
1 von S enthalt:!
10
S = 0 S0 :(5.4)

S 0 stimmt mit der in Abschnitt 3.5 bestimmten Smith Normalform uberein.
Sei M eine ss Matrix. Wir vereinbaren, da M die Teilmatrix von M bestehend
aus den ersten s m Spalten und M die Teilmatrix von M bestehend aus denletzen m Spalten ist.
Die Berechnung von S mu konsistent zu 3.5 erfolgen. Schlielich sollten in
12(p ; : : : ; ps) (U )112dieselben eventuell gebrochenen Ideale als Erzeuger der zyklischen Faktoren auftreten, die dort erhalten werden. Durch genaues Betrachten von H ist aberersichtlich, da und wie dies moglich ist. Durch elementare Zeilenoperationenlat sich erstens erreichen, da in jeder Spalte, deren Diagonalelement 1 ist, ansonsten nur noch Nullen stehen. Zweitens konnen wir durch simultane Zeilenund Spaltenvertauschungen die Diagonalelemente ungleich 1 | bei Erhaltung
der Reihenfolge | nach unten auf die Diagonale sortieren. Es bietet sich nun imwesentlichen dieselbe Situation wie in Abschnitt 3.5. Die Matrix, von der dort
die Smith Normalform berechnet wird, steht jetzt unten rechts. Schlielich ist
zu beachten, da die inversen Transformationen angewendet auf (p ; : : : ; ps) die
erzeugenden Primideale unverandert nach hinten bringen.
Wie in Abschnitt 3.5 reduzieren wir jetzt (U ) modulo H , also Ue = (U )H A mit einem geeigneten A. Ue und A stimmen bis auf zwischengeschobene
Nullzeilen mit den schon einmal berechneten Ue und A uberein.
Es folgt daraus, da analog
1

1

1

2

e 0 = ( ; : : : ; k ) B (V(a ; : : : ; am) S 0 = (p ; : : : ; ps) US
1

gilt.

1

1

2

AS 0 )

2(5.5)

5.1. DIE KLASSE EINES IDEALS

77

Wir stellen jetzt den Bezug zur linearen Algebra vollstandig her und benutzen die
Addition von Zeilenvektoren von Idealen als komponentenweise Multiplikation.
Die bisherigen U berlegungen liefern uns(a ; : : : ; am) = (p ; : : : ; ps) Ue= (p ; : : : ; ps) (U ) (p ; : : : ; ps) H A= (p ; : : : ; ps) (U ) ( ; : : : ; k ) B A
und daher(p ; : : : ; ps) (U ) = (a ; : : : ; am) + ( ; : : : ; k ) B A:
(5.6)
Aufgrund der Gestalt von S gilt weiter(p ; : : : ; ps) (U ) = ( ; : : : ; k ) B V :(5.7)
Es sollen jetzt die pi durch die ai dargestellt werden. Dazu kombinieren wir(5.6) und (5.7) durch Aneinanderfugen von Zeilenvektoren, denn es gilt U =((U ) j(U ) ), und multiplizieren von rechts mit U . Dies liefert(p ; : : : ; ps) = (oK ; : : : ; oK ; a ; : : : ; am) U + ( ; : : : ; k ) B (V jA)U; (5.8)
und die gesuchte Formel zum Umrechnen einer Darstellung in den pi in eine
Darstellung in den ai ist gefunden.
Durch Einsetzen von (5.8) in (5.2) sieht man, da sich die ki aus den m letzten
Eintragen von Uv ergeben. Allerdings sollte noch 0  ki < ci sein, wobei die ci
die Diagonaleintrage von S 0 sind. Sei U 0 die Matrix, die aus den letzen m Zeilen
von U besteht. Mit der "verallgemeinerten Division mit Rest fur Matrizen\ ausAbschnitt 3:5 schreiben wir U 0 v = S 0 Q + R. Die Eintrage von R bilden jetzt
die ki, und wir erhalten alles in allem unter Beachtung von (5.5)
a=+ ( ; : : : ; k )B M + (a ; : : : ; am ) R;
(5.9)
wobei M = (V jA)Uv + (V AS 0 )Q.
Bemerkungen:
Alle beteiligten Matrizen auer v, Q und R brauchen nur einmal berechnet undkonnen dann immer wieder verwendet werden. Die eigentliche Aufgabe besteht
nur noch darin, ein 2 a zu nden, so da (5.2) gilt. Eine fur viele Korperausreichende Vorgehensweise ist, in a so lange auszuzahlen, bis ein geeignetes
gefunden wird. Meistens sind dafur recht wenig Elemente zu bestimmen.
Zur konkreten Berechnung des Hauptidealanteils in (5.1) kann es notig sein, vorher im Einheitengitter modulo Einheiten oder ahnlich (B M jU ) zu reduzieren.
Mit diesem Verfahren zur Bestimmung der Klasse eines Ideals kann man naturlichauch Hauptidealtests durchfuhren, und dies sehr ezient. Wir verzichten auf
Beispiele an dieser Stelle.
1

1

1

1

1

1

1

1

2

2

1

2

1

1

1

1

1

1

1

1

1

1

1

1

2

1

1

1

1

1

1

1

1

2

1

1

78

5.2

KAPITEL 5. ANWENDUNGEN

S -Einheitenberechnung

In Kapitel 3 wurde einiges uber die S -Einheitengruppe gesagt. Dort wurde
erlautert, da eine Abbruchbedingung erforderlich ist, die entscheidet, ob mit einigen S -Einheiten bereits die ganze Gruppe erzeugt wurde, und wie dies mit dem
Eulerprodukt fur vollstandige Faktorbasen zu bewerkstelligen ist. Fur beliebige
Faktorbasen kann zu diesem Zweck mit der Methode des p-ten Wurzelziehens
vorgegangen werden. Besteht die Faktorbasis aber nur aus groen Primidealen, ist unklar, wie uberhaupt die erforderlichen S -Einheiten bestimmt werdenkonnen. Auf direktem Weg ist dies mit den Methoden der Relationensuche desKapitels 4 namlich nicht moglich. Es soll jetzt beschrieben werden, wie uber den
Umweg einer Klassengruppenberechnung beliebige S -Einheiten berechnet werdenkonnen.
Wir gehen davon aus, da die Klassengruppenberechnung bereits durchgefuhrt
wurde und die eingangs erwahnten Daten vorliegen. Zusatzlich sei mit S 0 die beliebige Faktorbasis gegeben, fur welche die S 0-Einheiten berechnet werden sollen.
Die Idee ist die folgende: Es werden einfach (S [ S 0)-Einheiten berechnet und
die S 0-Einheiten daraus als Untergruppe abgeleitet. Weil S [ S 0 mit S ebenfalls
vollstandig ist, wissen wir schon, welche Determinante die resultierende Klassengruppenmatrix haben mu, um fertig zu sein. Auch sollte die Relationensuchekein schwierigeres Problem als bei der vorangegangenen Klassengruppenberechnung darstellen. Die Ableitung der Unterguppenstruktur geschieht mit Hilfe einer
Hermite Normalform. Die Ideale aus S 0 werden in S [ S 0 nach hinten sortiert
und dazu die Klassengruppenmatrix in unterer Hermite Normalform berechnet.
Die jS 0j letzen Spalten der zugehorigen Relationsbasismatrix liefern eine Basis
der S 0-Einheiten (modulo Torsionseinheiten).
Konkret ist es zweckmaig, wie folgt vorzugehen: Fur jedes Primideal p 2 S 0nS
suchen wir nach einer (S [ S 0)-Relation 2 p, fur die =p nur in Primideale aus S
faktorisiert. Dann ist man schon fast fertig. Man erweitert die bereits bekannte
Klassengruppenmatrix um geeignete Nullzeilen und fugt die Spalten S[S ( )fur jedes der obigen an. Sind nun die Zeilen passend geordnet, so berechnet
man eine untere Hermite Normalform und kann dann S 0-Einheiten und sogar die
S 0-Klassengruppe erhalten. Die Details der Handhabung der Transformationsmatrizen sind einfach und werden nicht naher beschrieben. Die Berechnung der
speziellen Relationen setzt im ubrigen voraus, da S ausreichend gro ist.
Zum Schlu sei angemerkt, da man mit Hilfe der S -Klassengruppe auch Normgleichungen jN ( )j = k losen kann, wenn S aus allen Primidealen uber den
Primfaktoren von k besteht.
0Kapitel 6
Beispiele
Anhand einiger Beispiele soll nun in tabellarischer Form die Leistungsfahigkeit
des Klassengruppenverfahrens verdeutlicht werden. Die Implementierung der Algorithmen erfolgte im Computeralgebra-System KANT V4 . Naheres hierzu ist
in [9] zu erfahren. Fur die Berechnungen wurde eine Sun SparcStation 20 unter
SunOS 5.5 verwendet.
In den folgenden Tabellen besteht jeder Eintrag fur einen Korper aus drei Zeilen.
Die Eintrage der ersten Zeile sind: K | eine Darstellung des Zahlkorpers (k bezeichnet eine k-te primitive
Einheitswurzel), n | der Grad, r | der komplexe Anteil der Signatur, log (jDK j) | Logarithmus des Diskriminantenbetrags zur Basis 10,
 RK | der Regulator,
 ClK | die Struktur der Klassengruppe notiert als c  : : :  cm , wobei die
2

10

1

ci die Ordnungen der zyklischen Faktoren der Klassengruppe bezeichnen.

In der zweiten Zeile steht f (t) | ein den Zahlkorper erzeugendes Polynom.
Die dritte Zeile besteht aus

 C | eine kleine Faktorbasisschranke,
 CK0 | entweder die Minkowskischranke oder die Bachschranke, gekennzeichnet durch ein "M\ oder ein "B\,79

KAPITEL 6. BEISPIELE

80

 tC | gibt die Zeit an, die fur die Berechnung der Faktorbasis aus Primidea-

len mit Norm unterhalb von C benotigt wurde. Hierin ist die Reduktion
mit Algorithmus 4.3.2 und die Berechnung des Eulerprodukts enthalten,

 tCK | gibt die Zeit an, die der Beweis der Vollstandigkeit der Faktorbasis
0

mit Algorithmus 4.3.4 unter Verwendung der Schranke CK0 benotigte,

 tR | die Zeit, die fur die Relationensuche mit Algorithmus 4.4.9 notwendig
war,

 tV | die Zeit, die fur die Veri kation der S -Klassengruppe mit Algorithmus
3.6.4 gebraucht wurde.

Der Beweis der Vollstandigkeit der Faktorbasis hangt unter Verwendung derBachschranke von GRH ab. Er wurde ausgelassen, wenn sich anstelle von tCK
ein "{\ ndet. Bei zwei Beispielen ist tR mit einem "*\ gekennzeichnet. Hier
wurde anstelle von Algorithmus 4.4.9 der Algorithmus 4.4.5 angewendet. Durch
die Veri kation der S -Klassengruppe wird der Regulator nur fur die Primteiler
von hSK getestet und hangt ansonsten von der ausreichenden Approximation desEulerprodukts ab. Wir beginnen mit einigen durch zufallig gewahlte Polynomeerzeugten Korpern und gehen dann zu spezielleren Korpern mit interessanteren
Klassenzahlen uber.
0

81

jDK j)

RK

ClK

tC

tCK

tR

tV gesamt

2

12.88

217330.08

1171507M

6s

590s

5s

7

3

12.64

2614.1426279M

10s

72s

4s

9

4

29.21

94425050371.45

54266B

6s

2000s

177s

11

5

16.23

10563.85

60765M

17s

900s

10s

13

6

29.25

7594433941.11

54420B

12s

920s

310s

15

7

28.89

993382933.54

29s

1000s

105s

K
f (t )CQ ()t5 + 7t

222

500

Q ()

t + 5t
7

3

500

Q ()

n

r2

CK0
5

log 10 (

0

0s

601s
1

31

t + 1133

0s

86s
9

9

500

Q ()

t +t
11

7

500

Q ()
Q ()

t

t

t

15 + 14 + 13

Q ()

t

t

Q ()

t

19

300

t

:

36.74

85866B

27s

{

170s

19

9

32.16

646567462.10

50s

{

80s

t + 12

1 578



8

t

0s

927s
1

0s

1242s
1

0s

1012

17

17 + 5 11

300

1

7

53048B

500

2184s

3

t13 + 17
500

1s

1134s
1

0s

197s
1

12 + 11 + 4

65796B

Tabelle 6.1: Beispiele I.

0s

130s

KAPITEL 6. BEISPIELE

82

jDK j)

RK

ClK

tCK

tR

tV gesamt

9.97

2106.38

4s

11s

5s

1

15.61

195722.90

2s

33s

19s

11.44

9922.48

3s

41s

5s

6

3

13.85

84373.90

3212199B

3s

33s

5s

6

3

17.31

1175109.39

Kn
r2
f (t )
C
CK0
tC
Q ()
4
1
4
3
2
t + 8t 5t + 112t
11484M300

Q ()t + 97t

3300

15499B

5

t

37

Q ()

t

t + t + 42t
5

2

300

Q ()

t

t

t

6+9 5+8 4

Q ()

7

t

t

Q ()

t + 3t
8

8

t

10

300

2

t

10s

3

11.15

675.15t

12s

222337B

41s
5

0s

20.59
4

50

9

t

2

8

21.85

t + 12t + 46t + 14t
7s

122s

5

6

8s

t

2

4

t + 5t

114s

2

64

t

14s

18.74

5

2
1s

196733720.90

3

3

111s
1

32
0s

23617.47
2

24s

21

20s

4

2

1s

24226386.96

t + 96t
3

54s

2

7s

80s

5

t + 2t + t + t
7

49s

0s

38s

3

7

54s

0s

6s

10s

10

8

t

t +t

30374B

300

Q ()

4

9

t + 3t + 7t
9t

526971B

300

Q ()

t

5

0s

21 + 35

2

6

6

5

5s

8
7

20s

2

7 2+5 +2

4760M

300

2

t

t

7+2 6+ 5

0s

85 3 + 43 2 + 39 + 69

19067B300

tt + 4t

36

2

93

1

3

25709M

300

6

5

2

2

552

4

0

t + 1032t + 481

4

Q ()

t

4

log10 (

143s
10

t

14 + 934s

Tabelle 6.2: Beispiele II.

1s

157s

83
K
f (t)

C

Q ((

1
23) 2 )

Q ((

1
23) 2

jDK j)

RK

tC

tCK

tR

2

1

1.96

1

3M

0s

0s

0s

4

2

4.88

2.63

n

r2

CK0

t + 23log10 (

0

ClK
tV

gesamt
3

2

t

;

3
1
32 )

4

t

2 3+7 2t

6 + 78

41

0s

2s

Q ((

41M

1s

1
23) 2

6

3

8.86

56.75

1
33 )

6

t

3 5 + 21 4

Q ((

1
23) 2

t

8

t

;
;

t

0s

t

500
1
34 )

t
t
3
444t + 1278t2
500

Q ((

t

;

1
35 )

5 9 + 40 8
500

Q ((

1
23) 2

12

11

Q ((

1
23) 2

;

9 + 174

853M

8s

1s

3s

8

4

13.13

574.27

1
36 )

t

t

0s

23094M

12s

90s

8s

t

14

t

;

10

5

17.62

103020.51ttt

130 7 + 545 6tt

19742B

17s

12

6

Q ((

t

;

1
38 )

3

103s

26s

1s

8

7

359158.112631580B

29s

310s

39s

14

7

27.1

178632294.12

tt

287 11 + 1421 10546687B

50s

16

8

t

8

15

14

500

13

65243B 2  12388s
3t

4641 9 + 15757 84377097

730s

t

3

183s

32.00

12

43s

147s

10s

3s

559555865.53

1850s

11

10

909s

Tabelle 6.3: Q (( 23) 12 ; 3 m1 ) fur m = 1; : : : ; 8.

966s

2

t + 76t 392t + 2086t 7784t + 28924t
81656t9 + 227131t8
489912t7 + 1042188t6
1684200t5+2693166t4
3022824t3 + 3557868t2
2264664t + 1680198
16

112s

t

22.28

9

6

500
1
23) 2

 12

1207 5 + 3285 4

t + 94563t 166383t + 305151t+499401t2
323589t + 276798
38059

2

7215 + 8238

7 13 + 63 12
7

12s

2s

t + 6t + 51t + 200t + 915t + 2526t + 7735t+15138t5 + 33435t4 + 44220t3 + 63891t2 + 43938t + 47094
1
37 )

12

1068 + 1158

10

500

6

3s

76 5 + 283 4tt
34350t + 8130t2

10

t

t

4 7 + 30 6

1
23) 2

t

2
0s

t

43 3 + 135 2

1s

8s

 24

2810s

KAPITEL 6. BEISPIELE

84
K
f (t )n

jDK j)

r2

RK

log10 (

ClK

C
CK0
tC
tCK
tR
1
Q (2 2 ; 13 )
24
12
35.34
34260599.80
24
23
22
21
20
19
t + 2t 21t 40t + 211t + 382t
1313t182244t17 + 5639t16 + 9034t15
17477t14
13
12
11
10
25920t + 40507t + 55092t
68957t83134t9+94247t8 + 99640t7
72553t6
72922t5 + 74467t4+34828t3
15621t2
14718t + 8191

tV

0

500

Q

t

1
(2 35 )35

Q (47 )

t

(

458s

{

3100s

35

17

64.28

2 956 1018

262862B

70s

{

4100s

46

23

75.24

2 8612 1017

111s

{

3300s

13

9s



:

3567s
1

2
500

47

79476Bgesamt

=t

1) (

0s



:

4170s
695

1)
360214B

1000

120s

3531s

Tabelle 6.4: Beispiele groeren Grades.
K
f (t)
Q ((

t

C

1
1234577) 2

t

;

1
32)

jDK j)

RK

ClK

tC

tCK

tR

tV gesamt

2

14.34

2.63

21

5s

280s

940s

1s

n

r2

CK0
4

log10 (

0

4 + 617287 2 + 95261736025

13085B

800

1226s

8
4
18.89
7513.29; 5 )
t8 + 4716t6 + 8328466t4 + 6527679671t2 + 1915873990801

Q ((14711) 2

500

Q ()

t

t

12 + 36 10t22693B

270s

2600s

1600s

12

6

23.56

30696.62tttt + 46655t + 1296t + 36t + 1+1679544

t

1144
2s

3

500

19721B

2

50s

970s

815s

4472s

5

9 + 1296 8 + 108 7 + 46657 6 + 2592 5

4

 65526s

Tabelle 6.5: Beispiele mit groerer Klassengruppe.

 170

1841s

Symbolverzeichnis
B
CK
ClK
ClKS
DK
EPK , EPK (x)
K
F

p

H
HK
HKS
IK
IKS
L
MK
N (a)
oK
PK
SK
RK

S
S
T (x)
U
TUK
UK
UKS
a, b, c, ,hKhSKS (x)
p2

Relationsbasismatrix der S -Einheiten ; : : : ; mIdealschranke fur K
Klassengruppe von K , ClK = IK =HK
S -Klassengruppe von K , ClKS = IKS =HKS
Diskriminante von K
Eulerprodukt und Anfang des Eulerprodukts von K
Algebraischer Zahlkorper
Endlicher Korper mit p Elementen
Klassengruppenmatrix der S -Einheiten ; : : : ; mHauptidealgruppe von K
HK \ IKS
Idealgruppe von K
Von den Primidealen aus S erzeugte Idealgruppe
Logarithmenabbildung
Minkowskischranke von K
Norm von a 2 IKMaximalordnung von K
Primideale des Zahlkorpers K
S kombiniert mit der Logarithmenabbildung L
Regulator von K
Faktorbasis: endliche Menge von Primidealen
Smith Normalform von H
T -Norm von x 2 K
Einheitenmatrix der S -Einheiten ; : : : ; mTorsionseinheitengruppe von K
Einheitengruppe von K
K  \ IKS
Ideale von K
algebraische Zahlen aus K
Klassenzahl von K
S -Klassenzahl von K
gleich (p1 (x); : : : ; ps (x))t wobei S = fp ; : : : ; psg
exponentielle Bewertung zum Primideal p
1

1

2

1

1

85

KAPITEL 6. BEISPIELE

86
p, q

,  i( )K (s)
f (t)
n
r,r
wK
1

2

Primideale von K
Nullstellen von f (t)Dedekindsche Zetafunktion von K
K de nierendes Polynom
Grad von K
Signatur von K
Anzahl der Torsionseinheiten von K

Literaturverzeichnis[1] E. Bach: Explicit bounds for primality testing and related problems ; Math.
Comp. 55 (1990); 355-380[2] E. Bach: Improved approximations for Euler products ; CMS Conf. Proc. v.
15 (1995); 13-28[3] J. Buchmann: A subexponential algorithm for the determination of classgroups and regulators of algebraic number elds ; Seminaire de Theorie desNombres, Paris 1988-1989; Birkhauser; 1990; 27-41[4] J. Buchmann und H. C. Williams: On the computation of the class numberof an algebraic number eld ; Mathematics of Computation 53, 188; 1989;
679-688[5] H. Cohen: A Course in Computational Algebraic Number Theory ; SpringerVerlag; Berlin - Heidelberg - New York; 1993
[6] L. J. Goldstein: A generalization of the Siegel-Wal sz theorem ; Transactionsof the American Mathematical Society 149; Providence; 1970; 417-429[7] J. Hafner und K. McCurley: A rigorous subexponential algorithm for computation of class groups ; J. Amer. Math. Soc. 2; 1989; 837-850[8] E. Horowitz, S. Sahni, S. Anderson-Freed: Grundlagen von Datenstrukturen ;International Thomson Publishing GmbH; Bonn; 1994
[9] KANT group: KANT V4 ; erscheint im J. Symb. Comput.
[10] A. K. Lenstra und H. W. Lenstra, Jr.: The developement of the number eld
sieve ; Springer-Verlag; Berlin - Heidelberg - New York; 1993[11] K. Meyberg: Algebra, Teil I ; Carl Hanser Verlag; Munchen - Wien; 1980
[12] W. Narkiewicz: Elementary and Analytic Theory of Algebraic Numbers ;Springer-Verlag; PWN; Polish Scienti c Publishers; Warszawa; 1990
[13] J. Neukirch: Algebraische Zahlentheorie ; Springer-Verlag; Berlin - Heidelberg - New York; 1992
87

88

LITERATURVERZEICHNIS

[14] J. Oesterle: Versions e ectives du Theoreme de Chebotarev
sous l'Hypothesede Riemann generalisee ; Asterisque 61; 1979; 165-167[15] M. Pohst: Computational Algebraic Number Theory ; Birkhauser; Basel Boston - Berlin; 1993[16] M. Pohst und H. Zassenhaus: Algorithmic Algebraic Number Theory ; Cambridge University Press; 1989
 die Berechnung von Klassenzahlen und[17] M. Pohst und H. Zassenhaus: Uber
Klassengruppen algebraischer Zahlkorper ; J. Reine Angew. Math. 361; 1985;
50-72[18] P. Ribenboim: Algebraic Numbers ; Wiley-Interscience; New York - London- Sydney; 1972[19] J. B. Rosser und L. Schoenfeld: Approximate formulas for some functionsof prime numbers ; Illinois J. Math. 6; 1962; 64-94[20] E. Scheid: Ein neuer Algorithmus zur Berechnung der Klassenzahl algebraischer Zahlkorper ; Diplomarbeit; Saarbrucken; 1993[21] J. Graf v. Schmettow: Beitrage zur Klassengruppenberechung ; Dissertation;Dusseldorf; 1991
 Grundeinheitenberechnung in algebraischen Zahlkor[22] K. Wildanger: Uberpern ; Diplomarbeit; Dusseldorf; 1993[23] A. Wintner: A factorization of the densities of ideals in algebraic number
elds ; American Journal of Mathematics 68; 1946; 273-284[24] K. Wiertelak: On the density of some sets of primes II ; Acta Arithmetica
34; 1978; 197-210[25] H. Zantema: Class numbers and units ; Computational Methods in Number
Theory; Part II; Mathematisch Centrum; Amsterdam; 1987; 213-234