Michael O. Rabin: Der Mann, der Computer mit dem Zufall vertraut machte

Im Alter von etwa zehn oder elf Jahren löste Michael Rabin im britischen Mandatsgebiet Palästina ein Geometrieproblem, an dem ältere Schüler gescheitert waren – ein frühes Anzeichen für einen Geist, der den Rest des Jahrhunderts damit verbringen sollte, elegante und unerwartete Wege durch Probleme zu finden, von denen alle anderen annahmen, sie erforderten absolute Gewissheit. Rabins Markenzeichen, das sich durch die Automatentheorie, Kryptographie und Zahlentheorie zog, war die Erkenntnis, dass eine Maschine, der man erlaubt zu raten oder eine Münze zu werfen, leistungsfähiger statt unzuverlässiger werden könnte – eine Idee, die als fast ketzerisch galt, als er sie erstmals vorschlug.

Von Breslau in ein Rabbinerhaus in Palästina

Rabin wurde am 1. September 1931 in Breslau, damals Deutschland und heute Wrocław, Polen, geboren. Sein Vater, ein Rabbiner, zog 1935 mit der Familie nach Palästina, noch vor den schlimmsten Ereignissen in Europa. Er besuchte die Hebrew Reali School in Haifa, studierte bei dem Mathematiker Elisha Netanyahu, der später Professor am Technion wurde, und arbeitete bereits als Teenager an fortgeschrittenen Mathematikkursen. Er erwarb 1953 einen Master-Abschluss in Mathematik an der Hebräischen Universität Jerusalem mit einer Arbeit, die ein ursprünglich von Emmy Noether aufgeworfenes offenes Problem löste, bevor er für ein Doktorat nach Princeton in die USA ging, das er 1957 unter dem Logiker Alonzo Church abschloss.

Eine Maschine, die raten kann

Rabins bedeutendste frühe Arbeit, die er zusammen mit Dana Scott verfasste und 1959 unter dem Titel „Finite Automata and Their Decision Problems“ veröffentlichte, führte das Konzept des nichtdeterministischen endlichen Automaten ein – eine theoretische Maschine, die bei einer Eingabe effektiv in mehrere Kopien ihrer selbst verzweigen und mehrere mögliche Rechenwege gleichzeitig verfolgen konnte. Die Arbeit bewies, dass diese nichtdeterministischen Maschinen, obwohl sie weitaus leistungsfähiger erschienen, in ihrer Rechenleistung exakt äquivalent zu gewöhnlichen deterministischen Maschinen waren – ein fundamentales Ergebnis, das die Sicht der Informatik auf die Berechnung selbst veränderte. Die Association for Computing Machinery verlieh Rabin und Scott 1976 speziell für diese Arbeit den Turing Award – die höchste Auszeichnung der Informatik für eine theoretische Arbeit, die Rabin verfasste, als er noch keine dreißig Jahre alt war.

Dem Zufall Zuverlässigkeit beibringen

Rabin kehrte immer wieder zu einer verwandten, seltsameren Idee zurück: dass die bewusste Einbringung von Zufall in eine Berechnung diese schneller oder einfacher machen könnte, ohne sie unzuverlässig zu machen. Bei den Bell Labs führte er um 1960 probabilistische Automaten ein, die Münzwürfe nutzten, um Zustandsübergänge zu entscheiden, und zeigte, dass sie bestimmte Sprachen mit exponentiell weniger Zuständen darstellen konnten als jede deterministische Maschine. Diese Intuition reifte 1975 zum Miller-Rabin-Primalitätstest heran, einem randomisierten Algorithmus – aufbauend auf früheren deterministischen Arbeiten von Gary Miller –, um festzustellen, ob eine riesige Zahl eine Primzahl ist. Er ist schnell und zuverlässig genug, um die Verschlüsselungssysteme des modernen Internets zu stützen; Rabins Version beseitigte insbesondere Millers Abhängigkeit von der unbewiesenen verallgemeinerten Riemannschen Vermutung. Der Kanellakis Award 2003 würdigte den gemeinsamen Beitrag von Miller, Rabin, Robert Solovay und Volker Strassen zu dieser Forschungsrichtung.

Schlösser aus schwieriger Mathematik

Rabins Kryptographie ging über das Testen von Primzahlen hinaus. 1978 entwickelte er das Rabin-Kryptosystem, das als erstes asymmetrisches Verschlüsselungsverfahren bekannt wurde, dessen Sicherheit mathematisch äquivalent zur Schwierigkeit der Faktorisierung großer Ganzzahlen bewiesen werden konnte – eine stärkere Garantie, als die meisten Kryptosysteme der damaligen Zeit beanspruchen konnten. 1981 formalisierte er den „Oblivious Transfer“, ein kryptographisches Protokoll, das es ermöglicht, Informationen so zu senden, dass der Absender nicht wissen kann, ob der Empfänger sie tatsächlich erhalten hat, was zu einem Baustein für sichere Mehrparteienberechnungen wurde. 1987 entwickelte er gemeinsam mit Richard Karp den Rabin-Karp-String-Suchalgorithmus, eine Rolling-Hash-Technik, die aufgrund ihrer Effizienz beim Auffinden eines Musters in großen Textmengen noch heute in Grundkursen für Algorithmen gelehrt wird.

Eine Karriere zwischen zwei Ländern

Rabins akademisches Leben verlief auf parallelen Wegen zwischen Israel und den Vereinigten Staaten. An der Hebräischen Universität Jerusalem stieg er Anfang dreißig vom Dozenten zum ordentlichen Professor auf, leitete das Institut für Mathematik und war von 1972 bis 1975 Rektor der Universität. In den USA hatte er ab 1981 die Gordon-McKay-Professur und später die Thomas-J.-Watson-Sr.-Professur in Harvard inne, neben Gastprofessuren am MIT, in Berkeley und an der Columbia University. Er wurde in die U.S. National Academy of Sciences, die American Academy of Arts and Sciences, die American Philosophical Society, die Französische Akademie der Wissenschaften und die Royal Society gewählt und erhielt 1995 den Israel-Preis sowie 2010 den Dan-David-Preis, neben Auszeichnungen wie dem IEEE Charles Babbage Award und dem Dijkstra-Preis.

Warum Michael als Genie bezeichnet wird

Rabins Status als Genie beruht auf einer erkennbaren Handschrift während einer fünfzigjährigen Karriere: Er identifizierte wiederholt, dass ein Problem, von dem man annahm, es erfordere Gewissheit, stattdessen schneller gelöst oder leistungsfähiger gemacht werden konnte, indem man absichtlich Zufall oder Nichtdeterminismus einführte – eine Erkenntnis, die Zeitgenossen zunächst als Kategorienfehler erschien, da Zufall weithin als Feind zuverlässiger Berechnung und nicht als Ressource dafür behandelt wurde. Diese Erkenntnis, unabhängig angewandt auf Automatentheorie, Primzahltests und das Design kryptographischer Protokolle, brachte Ergebnisse hervor, von denen jedes einzelne eine bedeutende Karriere markieren würde; mehrere davon hervorzubringen, war das, was das Turing-Award-Komitee und die Reihe späterer Kanellakis-, Babbage- und Dijkstra-Preise explizit würdigten. Es gibt kaum ernsthafte Gegenargumente: Im Gegensatz zu einigen Turing-Preisträgern, deren Ruf auf einer einzigen Arbeit beruht, ist Rabins Ruf auf unabhängig verifizierten, noch heute genutzten Ergebnissen über Jahrzehnte hinweg aufgebaut – der Miller-Rabin-Test läuft heute in kryptographischen Bibliotheken, nicht nur in Lehrbüchern. Wenn es einen Vorbehalt gibt, dann nur den, dass sein berühmtestes Einzelpapier, das mit Scott, aus einer echten Partnerschaft hervorging – eine Erinnerung daran, dass selbst die schärfste individuelle Erkenntnis in diesem Bereich normalerweise durch Zusammenarbeit und nicht durch einsames Genie zustande kam.

Vermächtnis

Rabin starb am 14. April 2026 im Alter von vierundneunzig Jahren. Er verbrachte seine letzten Jahre weiterhin als emeritierter Professor sowohl in Harvard als auch an der Hebräischen Universität. Seine Tochter Tal Rabin wurde selbst eine angesehene Kryptographin und trug die besondere Faszination der Familie für Zufall und Geheimhaltung in eine neue Generation. Die Algorithmen, die seinen Namen tragen – Miller-Rabin, Rabin-Karp, das Rabin-Kryptosystem – bleiben überall dort im aktiven, täglichen Gebrauch, wo ein Computer eine Zahl testen, eine Zeichenfolge suchen oder ein Geheimnis bewahren muss – ein seltener Fall von grundlegender theoretischer Informatik, die Jahrzehnte nach ihrer Entstehung noch immer sichtbare tägliche Arbeit leistet.