Computeralgebra: Skript zur Vorlesung (Sommersemester 2008 Heidelberg)

Einleitung 1
Inhaltverzeichnis 3
I Schnelle Algorithmen 7
1 Elementare Grundoperationen 9
1.1 Gewöhnliche Addition und Subtraktion . . . . . . . . . . . . . . . . . 9
1.2 Die gewöhnliche Multiplikation . . . . . . . . . . . . . . . . . . . . . 11
1.3 Division mit Rest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Die Karatsuba-Multiplikation . . . . . . . . . . . . . . . . . . . . . . 15
2 Diskrete Fouriertransformation 19
2.1 Diskrete Fourier-Transformierte . . . . . . . . . . . . . . . . . . . . . 19
2.2 Die inverse diskrete Fouriertransformation . . . . . . . . . . . . . . . 21
2.3 Schnelle Polynommultiplikation . . . . . . . . . . . . . . . . . . . . . 23
2.4 Schnelle Polynomdivision mit Rest . . . . . . . . . . . . . . . . . . . 24
3 Schnelle Multiplikation und Division mit Rest ganzer Zahlen 29
3.1 Modulare diskrete Fouriertransformation . . . . . . . . . . . . . . . . 29
3.2 Schnelle Multiplikation ganzer Zahlen . . . . . . . . . . . . . . . . . . 31
3.3 Schnelle Division mit Rest ganzer Zahlen . . . . . . . . . . . . . . . . 34
3.4 Schnelles Potenzieren natürlicher Zahlen . . . . . . . . . . . . . . . . 35
4 Der Euklidische Algorithmus 37
4.1 Euklidische Ringe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Komplexität des Euklidischen Algorithmus . . . . . . . . . . . . . . . 40
4.3 Der schnelle Euklidische Algorithmus . . . . . . . . . . . . . . . . . . 41
4.4 Rechnen mit rationalen Zahlen und Funktionen . . . . . . . . . . . . 44
5 Resultanten 45
5.1 Sylvestermatrix und Resultante . . . . . . . . . . . . . . . . . . . . . 45
5.2 Produktformel für die Resultante . . . . . . . . . . . . . . . . . . . . 49
5.3 Die Diskriminante eines Polynoms . . . . . . . . . . . . . . . . . . . . 52
5.4 Eliminationsverfahren für nichtlineare
Gleichungssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6 Subresultanten 55
6.1 Polynomrestfolgen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.2 Subresultanten und Bézoutkoeffizienten . . . . . . . . . . . . . . . . . 58
6.3 Koeffizientenwachstum . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.4 Der Euklidische Algorithmus in Z[T] . . . . . . . . . . . . . . . . . . 62
7 Die modulare Methode 65
7.1 Der Hauptsatz über simultane Kongruenzen . . . . . . . . . . . . . . 65
7.2 Polynomwertberechnung und Interpolation . . . . . . . . . . . . . . . 68
7.3 Modulares Rechnen mit ganzen Zahlen . . . . . . . . . . . . . . . . . 70
8 Der modulare Euklidische Algorithmus 73
8.1 Geeignete Primzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
8.2 Koeffizientenschranken für Teilerpolynome . . . . . . . . . . . . . . . 75
8.3 Der modulare ggT-Algorithmus . . . . . . . . . . . . . . . . . . . . . 77
9 Rechnen mit algebraischen Zahlen 81
9.1 Zahlkörper und endliche Körper . . . . . . . . . . . . . . . . . . . . . 81
9.2 Rechnen im Körper aller algebraischen Zahlen . . . . . . . . . . . . . 83
9.3 Wurzeltrennung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
9.4 Sturmsche Ketten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
10 Gitterbasisreduktion 91
10.1 Reduzierte Gitterbasen . . . . . . . . . . . . . . . . . . . . . . . . . . 91
10.2 Konstruktion einer reduzierten Gitterbasis . . . . . . . . . . . . . . . 94
10.3 Konstruktion des Minimalpolynoms einer algebraischen Zahl . . . . . 96
II Primzerlegung 103
11 Primzahlen 105
11.1 Erzeugung von Primzahlen . . . . . . . . . . . . . . . . . . . . . . . . 105
11.2 Pollard’s ρ-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
11.3 Der Algorithmus von Pollard und Strassen . . . . . . . . . . . . . . . 112
12 Die Sätze von Fermat und Euler 115
12.1 Restklassenringe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
12.2 Quadratische Reste . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
12.3 Das Eulersche Kriterium . . . . . . . . . . . . . . . . . . . . . . . . . 119
13 Der Primzahltest von Miller-Rabin 125
13.1 Strenge Pseudoprimzahlen . . . . . . . . . . . . . . . . . . . . . . . . 125
13.2 Der Satz von Rabin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
13.3 Bemerkungen zur Erweiterten Riemannschen Vermutung . . . . . . . 131
14 Der AKS-Primzahltest 135
14.1 Vorbemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
14.2 p-ähnliche Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
14.3 Der AKS-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . 141
15 Quadratdifferenzenverfahren 145
15.1 Die Quadratdifferenzenmethode von Fermat . . . . . . . . . . . . . . 145
15.2 Exkurs über Kettenbrüche . . . . . . . . . . . . . . . . . . . . . . . . 147
15.3 Das Primzerlegungsverfahren von Lehman . . . . . . . . . . . . . . . 149
15.4 Das Kettenbruch-Faktorisierungsverfahren von Lehmer . . . . . . . . 151
16 Der Algorithmus von Dixon 153
16.1 Faktorenbasen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
16.2 Einige relative Häufigkeiten . . . . . . . . . . . . . . . . . . . . . . . 155
16.3 Der Satz von Dixon . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
17 Das Quadratische Sieb 161
17.1 Das einfache Quadratische Sieb . . . . . . . . . . . . . . . . . . . . . 161
17.2 Laufzeitabschätzung für das Quadratische Sieb . . . . . . . . . . . . . 162
17.3 Das verteilte Quadratische Sieb . . . . . . . . . . . . . . . . . . . . . 164
17.4 Schnelles Lösen quadratischer Gleichungen . . . . . . . . . . . . . . . 165
18 Primpolynomzerlegung über endlichen Körpern 169
18.1 Teilfaktorisierungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
18.2 Der Berlekamp-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . 173
18.3 Eine Variante für große q . . . . . . . . . . . . . . . . . . . . . . . . . 176
18.4 Nullstellenberechung über endlichen Körpern . . . . . . . . . . . . . . 178
19 Die Hensel’sche Methode 181
19.1 Das Hensel’sche Lemma . . . . . . . . . . . . . . . . . . . . . . . . . 181
19.2 Primzerlegung in Z p [T] . . . . . . . . . . . . . . . . . . . . . . . . . . 184
19.3 Primzerlegung in Z[T] . . . . . . . . . . . . . . . . . . . . . . . . . . 185
20 Faktorisierung multivariater Polynome 191
20.1 Das Homomorphieprinzip . . . . . . . . . . . . . . . . . . . . . . . . 191
20.2 Das mehrdimensionale Hensel’sche Lemma . . . . . . . . . . . . . . . 192
20.3 Die rekursive Methode von Wang . . . . . . . . . . . . . . . . . . . . 194
III Algebraische Gleichungssysteme 197
21 Gröbner-Basen 199
21.1 Monomordnungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
21.2 Charakterisierung von Gröbner-Basen . . . . . . . . . . . . . . . . . . 201
21.3 Existenz von Gröbner-Basen . . . . . . . . . . . . . . . . . . . . . . . 204
21.4 Reduzierte Gröbner-Basen . . . . . . . . . . . . . . . . . . . . . . . . 205
22 Der Buchberger-Algorithmus 209
22.1 Differenzenpolynome . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
22.2 Konstruktion einer Gröbner-Basis . . . . . . . . . . . . . . . . . . . . 211
22.3 Syzygien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
22.4 Der erweiterte Buchberger-Algorithmus . . . . . . . . . . . . . . . . . 217
23 Eliminationstheorie 219
23.1 Eliminationsideale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
23.2 Der Ergänzungssatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
23.3 Ideale der Dimension Null . . . . . . . . . . . . . . . . . . . . . . . . 222
24 Elementare Idealoperationen 225
24.1 Durchschnitt von Idealen . . . . . . . . . . . . . . . . . . . . . . . . . 225
24.2 Quotient von Idealen und Radikalzugehörigkeit . . . . . . . . . . . . 226
24.3 Teilringzugehörigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
24.4 Simultane Kongruenzen . . . . . . . . . . . . . . . . . . . . . . . . . . 229
25 Gröbner-Basen und Lineare Algebra in Noetherschen Ringen 233
25.1 Allgemeine Gröbner-Basen . . . . . . . . . . . . . . . . . . . . . . . . 233
25.2 Der allgemeine Buchberger-Algorithmus . . . . . . . . . . . . . . . . 235
25.3 Ringe mit konstruktiver linearer Algebra . . . . . . . . . . . . . . . . 238
Literaturverzeichnis 240