Computeralgebra: Skript zur Vorlesung (Sommersemester 2008 Heidelberg)

Description

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