Mathematics Unlimited
2001 and Beyond
Björn Engquist, Wilfried Schmid (Herausgeber)
Springer Verlag, Berlin, Heidelberg, New York, 2001, 1236 Seiten, 59,95 $
ISBN 3-540-66913-2
Dieses Buch wurde speziell zum Millenniumswechsel aufgelegt und soll den Stand der mathematischen Forschung zu Beginn des dritten Jahrtausends festhalten. Gleich vorneweg möchte ich sagen, dass das Buch diesen Zweck m. E. ohne Einschränkung erfüllt.
Auf Grund des Umfangs des vorliegenden Buchs möchte ich mich in diesem Referat allerdings auf eine kurze Beschreibung derjenigen Artikel beschränken, die sich mit Themen der Computeralgebra beschäftigen. Das ist angesichts des Leserkreises des Rundbriefs naturgemäß angemessen.
Man sollte annehmen, dass Computeralgebra als eine moderne computerorientierte Wissenschaft in diesem Buch eine wichtige Rolle spielen wird. Und in der Tat werden wir nicht enttäuscht. Eine beträchtliche Anzahl der Artikel des Bandes beschäftigt sich mit Themen, die sich hier einordnen lassen. Es handelt sich hierbei um mindestens 10 von insgesamt 63 Artikeln, die ich nun kurz beschreiben will.
David H. Bailey, Jonathan M. Borwein: Experimental Mathematics: Recent Developments and Future Outlook.
Computeralgebrasysteme ermöglichen mathematische Experimente. In diesem Artikel werden insbesondere Algorithmen behandelt, mit denen sich ganzzahlige Beziehungen zwischen gegebenen reellen oder komplexen Zahlen auffinden lassen. Hierbei spielt insbesondere der berühmte LLL-Gitterreduktions-Algorithmus eine Rolle. Ein Resultat derartiger Berechnungen ist die Darstellung
mit welcher jede hexadezimale (und damit auch jede binäre) Ziffer von π einzeln - ohne Kenntnis der Vorgängerziffern - berechnet werden kann. Diese Identität wurde mit den erwähnten Methoden erst in den 1990ern entdeckt. Natürlich wurde Formel (1) dazu verwendet, Rekordbinärziffern von π zu berechnen.
Die Autoren liefern weitere Beispiele von Ergebnissen, welche mit dieser Methode gefunden wurden. Schließlich geben sie ein warnendes Beispiel, dass nicht jede experimentelle Vermutung auch stimmen muss: Während für k = 0,...,5
ist, ist für k = 6
Dies weicht nur um 10-11 von π/2 ab!
Achtung: Dieser Artikel wurde offenbar per e-mail übermittelt und enthält einige Schreibfehler, die vom e-mail-Transport herrühren.
Arjeh M. Cohen: Communicating Mathematics Across the Web.
In diesem Artikel kommt das Wort Computeralgebra bereits in der Einleitung vor. Der Autor entwickelt an der Fragestellung der mathematischen Kommunikation mit verschiedenen Computeralgebrasystemen das Bedürfnis nach einer Metasprache. Beispielsweise gibt er konkrete Beispiele von teilweise falschen Ergebnissen bestimmter Computeralgebrasysteme, welche es wünschenswert erscheinen lassen, Probleme interaktiv von mehreren Systemen gleichzeitig lösen zu lassen. Dies führt zum OpenMath-Projekt.
Der Autor führt aus, wie eine Kombination von Computeralgebra und Fehlerkontrolle am besten über das World Wide Web realisiert werden kann, und gibt schließlich einen Überblick über das OpenMath-Projekt.
Henri Cohen: Computational Aspects of Number Theory.
Zahlentheorie hat sich seit der Entdeckung asymmetrischer Verschlüsselungsverfahren von einer Disziplin der reinen Mathematik zu einem anwendungsorientierten Fachgebiet hin entwickelt. Diese Entwicklung geht einher mit der größeren Leistungsfähigkeit heutiger Computer, welche algorithmische Rechnungen begünstigen.
Die Sicherheit von Verschlüsselungsverfahren wie dem RSA-Verfahren hängt essentiell mit der Schwierigkeit zusammen, große natürliche Zahlen zu faktorisieren. Gute Faktorisierungsalgorithmen können das RSA-Verfahren brechen. Daher gibt es einen Forschungsboom auf diesem Gebiet mit z. T. durchaus erstaunlichen Ergebnissen. Über derartige Methoden wird ein historischer Überblick gegeben.
Es werden zunächst Primzahltests behandelt. Nach dem Fermattest wird die Benutzung zyklotomischer Körper und elliptischer Kurven betrachtet. Es folgen Faktorisierungsmethoden: der Pollardsche -Test, Shanks Babystep-Giantstep-Methode, Lenstras Elliptische-Kurven-Methode, Pollards p-1-Methode, Faktorbasen sowie Zahlkörpermethoden.
Nach Einführung quadratischer Körper werden weitere moderne zahlentheoretische Algorithmen betrachtet. Der LLL-Algorithmus eignet sich - wie im Beitrag von Bailey und Borwein gesehen - zur Bestimmung Q-linearer Abhängigkeiten, läßt sich auch zur Idealreduktion einsetzen und ist für die Faktorisierung von Polynomen von Bedeutung. Algorithmen zur Bestimmung der Anzahl der Punkte elliptischer Kurven über endlichen Körpern folgen. Die Arbeit schließt mit einer Liste Some Challenges for the Twenty-First Century.
Oded Goldreich: Computational Complexity.
Die Möglichkeit, mathematische Algorithmen in Computerprogramme umzusetzen, hat zum Entstehen des Gebiets der Komplexitätstheorie geführt. Der Autor spricht über den Begriff der Berechenbarkeit, über Turingmaschinen und über Effizienz. Es wird genau erklärt, was ein polynomialer Algorithmus ist. Die Komplexitätsklassen P und NP werden eingeführt und die Frage P ≠ NP wird diskutiert. NP-vollständige Probleme werden erörtert. Der Autor macht klar, dass es genau dann Einwegfunktionen gibt - welche Kryptosysteme wie RSA erst sicher machen -, falls die zentrale Vermutung P ≠ NP richtig ist. Diese Zusammenhänge zwischen der Komplexitätstheorie und der Kryptographie werden eingehend untersucht.
Neal Koblitz: Cryptography.
Die Kryptographie wurde 1976 durch die Einführung des Konzepts eines asymmetrischen Verschlüsselungsverfahrens durch Diffie und Hellman revolutioniert. Rivest, Shamir und Adleman entwickelten 1978 als erste ein solches Verfahren, das RSA-Verfahren. Dieses Verfahren wird ausführlich behandelt, Hashfunktionen sowie digitale Signaturen werden eingeführt. Diskrete Logarithmen, das Diffie-Hellmansche Schlüsselaustauschverfahren und der digitale Signatur-Algorithmus (DSA) werden behandelt. Das Rechnen in elliptischen Kurven macht asymmetrische Verschlüsselungsverfahren häufig sicherer.
Schließlich wird die Kryptoanalyse, also das Brechen kryptographischer Verfahren, betrachtet, welche im Falle des RSA-Algorithmus auf die Faktorisierung großer ganzer Zahlen hinausläuft. Das Zahlkörpersieb wird vorgestellt und der Xedni-Algorithmus wird betrachtet. Abschließende Bemerkungen über die Forschungskultur in der Kryptographie beruhen auf Erfahrungen des Autors, welche durchaus zu denken geben.
Maxim Kontsevich, Don Zagier: Periods.
Die algebraischen Zahlen A bilden üblicherweise die höchste Stufe in der Hierarchie endlich darstellbarer komplexer Zahlen:
In dieser Arbeit wird zwischen A und C noch eine weitere Hierarchie eingefügt, die also auch transzendente Zahlen enthält, welche sich aber dennoch geeignet endlich darstellen lassen, die sogenannten Perioden. Eine Zahl heißt eine Periode, falls sich ihr Real- und ihr Imaginärteil jeweils durch absolut konvergente bestimmte Integrale rationaler Funktionen mit rationalen Koeffizienten darstellen lassen, mit Integrationsgebieten in Rn, welche durch polynomiale Ungleichungen mit rationalen Koeffizienten beschrieben werden. Es zeigt sich sofort, dass algebraische Zahlen Perioden sind.
Aber auch die transzendente Zahl
ist eine Periode, während vermutet wird, dass die Eulersche Zahl e keine Periode ist. Es gibt aber viele weitere Perioden: Logarithmen algebraischer Zahlen, elliptische Integrale oder auch
Man kann zeigen, dass die Menge der Perioden eine Algebra bildet, Summe und Produkt von Perioden sind also wieder Perioden.
Der sehr interessante Artikel untersucht Identitäten zwischen Perioden und stellt Perioden mit Differentialgleichungen und L-Funktionen in Zusammenhang.
Hans Petter Langtangen, Aslad Tveito: How Should We Prepare the Students of Science and Technology for a Life in the Computer Age?
Heutige mathematische Software macht die Nutzung numerischer Tafeln obsolet und ermöglicht Unterricht auf höherem Niveau als früher. Dies wird aber leider noch weitgehend ignoriert. Der Autor fordert eine völlige Umorientierung des Lehrbetriebs. Im Gegensatz zum Status Quo dürfen die Studenten erwarten, vom ersten Studientag an mit modernster Computertechnologie unter Berücksichtigung realistischer Fragestellungen aus den Anwendungen vertraut gemacht zu werden. Die Analysisausbildung profitiert aus numerischen Experimenten zu den Begriffen Differentiation, Integration, gewöhnliche Differentialgleichungen, Grenzwerte, Newtonverfahren. Graphische Darstellungen runden das Bild ab. Einige dieser Beispiele werden ausgeführt und die zentrale Rolle, die mathematische Software bei der Ausbildung spielen kann, wird erarbeitet.
Leider beschäftigt sich dieser Artikel - trotz des allgemein gehaltenen Titels - praktisch ausschließlich mit numerischen Fragestellungen, obwohl die Systeme Mathematica und Maple neben Matlab durchaus genannt werden.
Yiannis N. Moschovakis: What Is an Algorithm?
Algorithmen werden in einem allgemeinen informatischen Framework meist im Zusammenhang mit Rechenmaschinen, beispielsweise Turingmaschinen, erklärt. Dies ist nicht sonderlich intuitiv. Unsere intuitive Vorstellung eines Algorithmus ist eher die einer rekursiven Definition, während das Maschinenmodell auf Implementierungen, welche spezielle Algorithmen darstellen, abzielt.
Während heute kaum jemand an der Gültigkeit der Church-Turingschen These ,,Eine Funktion f : N → N ist berechenbar genau dann, wenn sie von einer Turingmaschine berechnet werden kann'' zweifelt, so stellt der Autor jedoch heraus, dass beispielsweise wichtige Aspekte der Komplexitätstheorie von der Theorie der Turingmaschinen nicht erfasst werden.
In dem vorliegenden Artikel wird eine möglichst weitgehende Definition einer Rechenmaschine gegeben. Am Beispiel des Sortierens wird gezeigt, dass Maschinenmodelle Komplexitätsfragen unzureichend beantworten können. Dann werden stetige rekursive Definitionen und Algorithmen behandelt. Unstetige Algorithmen runden das Bild ab. Der Artikel schließt mit einer Liste von Problemen im Zusammenhang mit der Definition eines Algorithmus.
Gerard van der Geer: Error-Correcting Codes and Curves over Finite Fields.
Der Artikel beginnt mit den endlichen Körpern Fq, es werden algebraische Kurven erklärt und Kurven über endlichen Körpern betrachtet. Die Frage nach der Anzahl der Punkte einer Kurve über einem endlichen Körper schließt sich an.
Fehlerkorrigierende Codes und Hamming-Abstand werden eingeführt, und es folgen einige Beispielklassen solcher Codes mit ihren Eigenschaften.
Jan van Leeuwen, Jiri Wiedermann: The Turing Machine Paradigm in Contemporary Computing.
In diesem Artikel wird beschrieben, warum die Nutzung heutiger Computer nicht mehr vollständig durch Turingmaschinen beschrieben werden kann. Hierzu wird zunächst ausführlich erklärt, was eine Turingmaschine ist, und es wird gezeigt, dass die folgenden Eigenschaften moderner Computertechnologie diesem Paradigma nicht entsprechen:
- non-uniformity of programs (Softwareupgrades etc. lassen sich nicht durch endliche Programme beschreiben)
- interaction of machines (z. B. über das Internet vernetzte Computer)
- infinity of operation (Input- und Outputdaten strömen permanent)
und zwar treten diese Effekte alle gleichzeitig auf. In diesem Sinne ist auch die Church-Turingsche These heute nicht mehr gültig. Man beachte, dass dies hauptsächlich den zugrundeliegenden Begriff der Berechenbarkeit berührt.
Der Autor gibt zwei Modelle einer erweiterten Turingmaschine, welche auch den Begriff des Orakels erweitert, nämlich die site machine bzw. die interactive Turing machine with advice. Diese Konzepte sind im wesentlichen gleichwertig und lassen eine Beschreibung der obigen Effekte zu. Aus diesem neuen Paradigma ergibt sich eine Neuformulierung der Church-Turingschen These.
Man möge mir nachsehen, wenn ich diese Auswahl nach persönlichen Gesichtspunkten getroffen habe und Ihr Lieblingsbeitrag fehlen sollte.
Zusammenfassend lässt sich sagen, dass das referierte Buch für mich kaum einen Wunsch offenlässt. Nur eines möchte ich bemängeln: Das Buch ist so dick - dicker als jedes andere Buch, das ich kenne - dass ich dieses Referat nur schreiben konnte, weil ich die mich interessierenden Artikel kopierte (das Buch lässt sich wegen seiner Dicke auch noch extrem schlecht kopieren!). Das Gesamtwerk ist nämlich praktisch überhaupt nicht transportabel. Da tröstet auch der wirklich extrem günstige Preis nicht darüber weg.
Rezension: Wolfram Koepf (Kassel) aus Computeralgebra-Rundbrief, Nr. 29 - Oktober 2001