Anzeige
Anzeige
1 Monat GRATIS testen, danach für nur 9,90€/Monat!

Astronomie|Physik Technik|Digitales

Mathematiker verbessern die legendäre Formel, mit der die Briten Enigma knackten

Ohne eine mathematische Formel mit dem Namen Good-Turing-Schätzer hätte der Zweite Weltkrieg vielleicht um Jahre länger gedauert. Mit ihrer Hilfe knackten die Briten die deutsche Verschlüsselungsmaschine Enigma. Mathematiker der Universität von Kalifornien in San Diego haben diese Formel jetzt verbessert und schlagen ein Maß für die Zuverlässigkeit derartiger Formeln vor. Alon Orlitsky und seine Kollegen präsentieren ihre Arbeit im Fachmagazin Science (Bd. 302, S. 427).

Den Briten war das so genannte Kenngruppenbuch der Deutschen in die Hände gefallen. Dieses Buch enthielt alle möglichen Geheimschlüssel, die man bei der Verschlüsselung mit Enigma benutzte. Außerdem waren von früher entschlüsselten Nachrichten die Buchseiten bekannt, von denen verschiedene U-Boot-Kommandanten jeweils Schlüssel entnommen hatten. Ziel der Briten war es, für jeden U-Boot-Kommandanten eine Wahrscheinlichkeitsverteilung der Buchseiten zu bekommen, von denen er Geheimschlüssel entnahm.

Eine einfache Methode, zu solch einer Wahrscheinlichkeitsverteilung zu kommen, ist naheliegend. Angenommen, wir wollen solch eine Verteilung über die Vogelarten bekommen, die unseren Garten besuchen. Wir zählen und bestimmen die nächsten 1.000 Vögel, die wir im Garten sehen, und registrieren beispielsweise 253 Spatzen, 108 Rotkehlchen, 62 Krähen und viele andere Arten bis hin zu Arten, von denen nur ein einziges Mitglied unter den tausend Vögeln war.

Die Rechnung ist zunächst einfach: Die Häufigkeit der Spatzen beträgt beispielsweise 25,3 Prozent, die von Arten, von denen nur ein Mitglied vertreten war, 0,1 Prozent. Aber was ist mit Arten, die unter den 1000 Vögeln überhaupt nicht vertreten waren, von denen wir aber wissen, dass sie unseren Garten dann und wann auch mal besuchen? Nach bisheriger Rechnungsmethode wäre deren Häufigkeit Null. Eine exaktere Häufigkeitsangabe für seltene Vögel könnte man so nur bekommen, wenn man statt Tausend 10.000 oder gar 100.000 Vögel beobachten würde.

Den Engländern standen während des Zweiten Weltkrieges aber nur begrenzte Informationen über die Schlüsselwahl der U-Boot-Kommandanten zur Verfügung. Doch der britische Mathematiker Alan Turing fand zusammen mit seinem Kollegen I.J. Good eine Formel, den Good-Turing-Schätzer, die die wahren Wahrscheinlichkeiten sehr viel realistischer wiedergibt. Nach dem Krieg veröffentlichte Good die Formel und erwähnte, das Turing sie intuitiv aufgestellt hatte.

Anzeige

Inzwischen gibt es zwar einige Teilerklärungen dafür, warum die Formel in vielen Fällen gut funktioniert, aber es fehlte ein objektives Maß für ihre Leistungsfähigkeit. Zudem weiß man, dass sie in bestimmten Fällen schlechte Ergebnisse liefert. Orlitsky und seine Kollegen haben nun eine Formel entwickelt, die in allen Fällen zuverlässige Ergebnisse liefert. Zudem schlagen sie ein Maß für die Bewertung der Zuverlässigkeit solcher Formeln vor.

„Obwohl die neue Schätzformel noch
beträchtlich vereinfacht und weiterentwickelt werden muss, hoffen wir, dass sie zur Verbesserung von Spracherkennungssoftware beitragen kann und ebenfalls dabei helfen wird, Software zur gezielten Datensuche zu verbessern“, sagt Orlitsky. Ein weiterer Anwendungsbereich ist die Rettung teilweise verlorener Information, beispielsweise von einer zerstörten Computerfestplatte.

Axel Tillemans
Anzeige
Anzeige

Videoportal zur deutschen Forschung

Dossiers

Aktueller Buchtipp

Sonderpublikation in Zusammenarbeit  mit der Baden-Württemberg Stiftung
Jetzt ist morgen
Wie Forscher aus dem Südwesten die digitale Zukunft gestalten

Wissenschaftslexikon

Hel|den|rol|le  〈f. 19; Theat.〉 Rolle eines Helden

Schwamm  〈m. 1u〉 1 weiches, poriges Gerät, das Wasser aufnimmt, zum Waschen u. Säubern 2 Angehöriger eines Tierstammes mit sehr verschieden gestalteten, festsitzenden Arten, die aus lockeren Zellansammlungen bestehen: Porifera; … mehr

En|te|ro|sko|pie  auch:  En|te|ros|ko|pie  〈f. 19; Med.〉 Untersuchung des Darms mit dem Enteroskop … mehr

» im Lexikon stöbern
Anzeige
Anzeige
[class^="wpforms-"]
[class^="wpforms-"]
[class^="wpforms-"]
[class^="wpforms-"]
[class^="wpforms-"]
[class^="wpforms-"]