Die Lehmer's in Berkeley

Dies ist eine kurze Geschichte einer außergewöhnlichen Wissenschafterfamilie und der Entwicklung eines Algorithmus zur Erzeugung von Zufallszahlen sowie dessen, in Folge der Weiterentwicklung, unsachgemäßer Implementierung. Der genannte Algorithmus hat den Weg in eine Fülle von Anwendung gefunden, vom Einarmigen Banditen bis zu Microsoft Excel lässt sich die Palette der Einsätze beschreiben (Link). Diese einfache Idee zeigt aber auch, wie wichtig eine fundamentale Ausbildung in der Informatik ist, und wie es ohne fundiertes Grundlagenwissen in der Folge zu fatalen Fehlern kommen kann.

Wir starten in den USA an der University of California in Berkeley. Dort arbeiteten und forschten Derrik Norman Lehmer (1867-1938), sein Sohn Derrik Henry Lehmer (1905-1991) und dessen Frau Emma Trotskaia Lehmer (1906-). Alle drei waren sie Spezialisten in einer mathematischen Disziplin, der Zahlentheorie, genannt “die Königin der Mathematik”.

Derrik N. Lehmer beschäftigte sich intensiv mit der Fragestellung der Faktorisierung von Zahlen. Faktorisierung bedeutet die Zerlegung von ganzen Zahlen in ein eindeutig gegebenes Produkt von Primzahlen. Hier ein einfaches Beispiel: Die Zahl 12 lässt sich in eindeutiger Weise als Produkt der ersten beiden Primzahlen 2 und 3 darstellen, nämlich 12 = 2 ^. 2 ^. 3 = 2^{2 .} 3. Etwas komplizierter, die Zahl 234234 lässt sich durch die Primzahlen 2, 3, 7, 11 und 13 faktorisieren, und zwar 234234 = 2 ^. 3^{2 .} 7 ^. 11 ^. 13² . Die Primzahlen sind hierbei die Bausteine aus denen sich jede beliebige Zahl in Form eines Produktes darstellen lässt. Eine Primzahl selbst ist nicht mehr teilbar oder gleichbedeutend damit, nicht mehr als Produkt von ganzen Zahlen darstellbar. Es ist im Allgemeinen sehr schwierig so eine Faktor - Zerlegung von sehr großen Zahlen anzugeben, zum Beispiel einer Zahl mit 500 Dezimalstellen. In ähnlicher Weise ist es sehr schwer nachzuweisen ob eine große Zahl eine Primzahl ist oder nicht. Die Problematik der Faktorisierung wurde viel später, erst in den vergangenen Jahren sehr populär, da man die Schwierigkeit der Zerlegung großer Zahlen in Produkte ausgenutzt hat um geeignete Verfahren zur Verschlüsselung von Informationen zu entwickeln. Ein Beispiel dafür ist der RSA Algorithmus (siehe Links unten).

Das Bild oben zeigt ein Resultat von Lehmer’s Arbeit und zwar die Publikation von Faktor-Tabellen der ersten 10 Millionen Zahlen (Carnegie Institution of Washington, 1909). Dies war in der damaligen Zeit nicht ganz so einfach wie im Computerzeitalter heute, wie man vielleicht aus dem abgebildeten Auszug eines „händisch“ gerechneten Nachweises einer Primzahleigenschaft seines Sohnes aus dem Jahr 1932 vermuten kann.

D.N.Lehmer war neben seiner akademischen Karriere begeisterter Musiker und Poet. Er veröffentlichte neben vielen Liedern drei größere musikalische Werke (zwei davon Opern) und mehrere Gedichtbände. Er war auch wesentlicher Förderer der Karriere seines Sohnes D.H.Lehmer welcher durch seinen Vater auch dessen Studentin Emma Trotskaia, seine spätere Frau, kennen gelernt hat.

D.H.Lehmer beschäftigte sich wie sein Vater mit zahlentheoretischen Fragestellungen. Er entwickelte sich zu einer führenden Autorität in der Zahlentheorie und folglich auch in der sich damals rasch entwickelnden Computerwissen-schaft. Neben persönlichen wissenschaftlichen Interessen bearbeiteten die drei Lehmer‘s auch viele gemeinsame Fragestellungen als Beispiel seien wichtige Beiträge zur Erforschung des berühmten Problems von Fermat: „Fermat‘s Letztem Satz“ erwähnt, welcher nach 350 ungelösten Jahren, erst im Jahre 1993 durch Andrew Wiles gelöst wurde (siehe Links).

Ein weiterer wissenschaftlicher Erfolg der Lehmer‘s war die Entwicklung von elektromechanischen Maschinen zur Faktorisierung von Zahlen (siehe Bilder unten). D.H.Lehmer entwickelte verschiedenste Verfahren basierend auf Fahrradketten, Filmspulen, Zahnrädern in Kombination mit elektronischem Antrieb und Steuerung um geeignete Faktoren von großen Zahlen zu finden.

Die Funktionsweise dieser Maschinen beruht auf einem bereits sehr alten mathematischen Prinzip des Griechen Eratosthenes um 230 v.Chr. Erwähnenswert dabei ist, dass die erste mechanische Realisierung dieser Methode von einem Österreicher namens Anton Felkel stammt, welcher im Jahre 1776 mit Hilfe seines Verfahren eine Faktorentabelle bis zur Zahl 408.000 publizierte. Aber dies ist eine andere spannende Geschichte (siehe Links).

D.H. Lehmer war in den folgenden Jahren (~1945-1955) wesentlich an der Entwicklung der ENIAC (Electronic Numeric Integrator and Calculator), einer der ersten sehr großen Rechenmaschinen (siehe Info-Box unten) beteiligt. ENIAC rechnete nicht wie heutige Computer mit Binärzahlen sondern im Dezimalsystem und wurde hauptsächlich für physikalische Berechnungen und Simulationen verwendet. Speziell für diese Maschine hat D.H.Lehmer einen einfachen arithmetischen Algorithmus zur Erzeugung von Zufallszahlen vorgeschlagen welche als Basis für Simulationen benötigt wurden. Die Idee dieses Algorithmus ist unmittelbar mit Lehmer‘s zahlentheoretischer Erfahrung verbunden. Lehmer‘s Zufallsgenerator funktioniert in der ursprünglichen Version folgendermaßen: Wir betrachten die Zahlen n = 1,2,3,... und berechnen dazu die Potenzen a_n, wobei a = 23. Als „Zufallszahl“ wird der Rest x_n verwendet der bei Division von an durch m = 10⁸+1 = 100000001. entsteht. Somit erhält man eine Folge von „Resten“ kleiner m. Dividiert man diese Folge von Zahlen durch den „Modul“ m, dann erhält man Werte u_n = x_n / m die zwischen 0 und 1 liegen und in ihrem Verhalten sehr zufällig, und zwischen 0 und 1 gleichmäßig verteilt erscheinen (siehe Info-Box 3 unten).

Zitat (Math. Rev. 1952): By repeating this process he (D.H. Lehmer) generates a sequence un which he shows has a repetition period of 5.882.352 (= (10⁸+1)/17 – 1). An IBM 602A was used to generate 5000 numbers of such a sequence. Four standard tests (unspecified) were applied to check the „randomness“, and the sequence passed all four. The author observes, however, that all of the members of the sequence he chose were divisible by 17.

Dieser Algorithmus, genannt der Lineare Kongruenzgenerator, wurde im Laufe der Zeit weiterentwickelt und modernisiert. Dabei waren D.H.Lehmer und viele weitere namhafte Mathematiker und Informatiker beteiligt unter anderem auch Donald Knuth der „Papst der Informatik“. Es wurden wichtige Grundvoraussetzungen für die Zahlen die diesen Zufallszahlengenerator definieren festgelegt. Um ein Beispiel zu nennen: einer der am weitesten verbreiteten Generatoren ist definiert durch die Zahlen a = 75 = 16807 und m = 2³¹-1 welche den Algorithmus wie beim Ursprungsgenerator von Lehmer definieren. Die Zahlen a und m haben in diesem Fall besondere Eigenschaften, und zwar ist m ist eine Primzahl welche in einem 32-bit Computer als Integer darstellbar ist, und a so gewählt, dass der Algorithmus spezielle Periodizitätseigenschaften besitzt. Die Implementierung der Berechnung der Reste bei der Division durch m wurde in Integer-Arithmetik realisiert. Letzterer Generator mit dem Namen „Minimal Standard“ wurde 1969 für das IBM System/360 entwickelt und hat sich im Laufe der Zeit weit verbreitet und ist immer noch in Verwendung. Der Primzahl-Modul hat wesentlichen Einfluss auf die Qualität der Verteilung der Zahlen des Generators.

RANDU

An dieser Stelle kommen wir zu einem wichtigen Ereignis in der Geschichte der Zufallszahlengeneratoren: Informatiker bei IBM haben Anfang der 70-iger Jahren versucht den Algorithmus effizienter zu implementieren. Dazu wurde als Modul an Stelle einer Primzahl die 2er Potenz m = 2³¹ verwendet und der „Multiplikator“ a in der Nähe einer 2er Potenz, nämlich a = 2¹⁶+3 gewählt. Diese besondere Wahl ermöglicht es die Erzeugung der Zahlenfolge durch Shift-Operationen wesentlich zu beschleunigen. Dieser Generator mit dem Namen RANDU wurde zwar anfänglich getestet, man hat aber eine wichtige Fehlerquelle übersehen. Teilt man die Folge von RANDU Zufallszahlen in 3er Blöcke (u₁, u₂, u₃), (u₄, u₅, u₆), (u₇, u₈, u₉), ... , dann liegen die dadurch entstandenen Punkte (x, y, z) nicht wie erwartet zufällig verteilt in einem 3-dimensionalen Quader sondern sie weisen eine sehr auffällige regelmäßige Struktur auf und liegen auf nur 15 Ebenen verteilt (siehe Bild). Dies bedeutet, dass man bei Verwendung von RANDU in drei-dimensionalen Simulationen völlig falsche Resultate erhalten würde. RANDU war ebenfalls wie der Minimal Standard Generator weit verbreitet. Diese geometrische Eigenschaft von RANDU lässt sich mathematisch nachweisen. Der Grund für diese 15 Ebenen liegt im Multiplikator a = 2¹⁶+3. Würde man z.B. nur den Modul in eine Primzahl wie m = 2³¹-1 ändern, ergäbe sich eine ähnlich schlechte Struktur. Der 2er Potenz Modul bei RANDU hat zusätzlichen negativen Einfluss. Und zwar wird durch diesen Modul die Verteilung der Bits der einzelnen Zufallszahlen sehr regelmäßig. Dies kann bei falscher Transformation der Zufallszahlen zu erheblichen Fehlern in Simulationen führen.

Einen positiven Effekt hatte die Erkenntnis über die Schwächen von RANDU. Der Lehmer Algorithmus wurde genauestens untersucht. Man entwickelte schnelle und theoretisch und praktisch sehr genau analysierte Zufallszahlengeneratoren basierend auf verschiedensten arithmetischen Verfahren. Weiters wurden spezielle Zufallszahlen-Verfahren für die Anwendung bei Verschlüsselungstechnologien entwickelt.

Trotzdem sollte man aus dieser Geschichte zwei wichtige Dinge lernen. Es ist nicht immer vorrangig, „effizienter und schneller“ zu sein. Die Anwendung von Algorithmen in der Informatik gehört wohlüberlegt und analysiert, bevor Implementierungen verwendet werden. Dazu ist ein fundiertes Grundlagenwissen notwendig. D.H. Lehmer hat durch seine Erfahrung in der Zahlentheorie sehr wohl über das Verhalten seiner Methode bescheid gewusst. Nur kam es in Folge der Verbreitung dieser Idee zu den Fehlern, und ähnliches passiert in unserer schnelllebigen „Cut and Paste“ Zeit sicherlich auch in vielen anderen Bereichen der Informatik auch.