Indische Informatiker haben eine Methode ausgearbeitet, mit der ein Computer eine Primzahl eindeutig identifizieren kann. Dies ist ein uraltes Problem der Mathematik und seine Lösung ein entscheidender Schritt nicht zuletzt für die Kryptografie.
Aktuelle Verschlüsselungstechniken setzen zwei Schlüssel ein: Einen öffentlichen und einen privaten. Dazu wird eine mathematische Funktion benötigt, die nicht umkehrbar sein darf. Eine solche Funktion wurde 1977 von Ronald Rivest, Adi Shamir und Leonard Adleman gefunden. Die nach ihren Initialen benannte Methode RSA beruht auf der Multiplikation von großen Primzahlen. Wenn sie ausreichend groß gewählt werden, kann auch ein Supercomputer die Verschlüsselung nur unter erheblichem Zeit- und Rechenaufwand knacken.
Das Problem: Die aktuell eingesetzten Algorithmen zum Test einer Primzahl können kein eindeutiges Ergebnis zeitigen. Die von Professor Manindra Agrawal und seinen Studenten Neeraj Kayal und Nitin Saxena vom Indian Institute of Technology in Kanpur präsentierte Funktion jedoch soll todsicher sein und stets ein konkretes Ergebnis liefern. Die Funktion trägt den Titel „Primes is in P“ und ist bislang nur als Arbeitspapier veröffentlicht worden.
Kollegen von Agrawal bezeichnen die Methode als bahnbrechend: „Die größte Schwachstelle herkömmlicher Kryptografiesoftware ist, dass sie eine Primzahl nicht mit Bestimmtheit als solche erkennen kann“, erläuterte beispielsweise Eric Allender, Informatik-Professor an der State University of New Jersey. „Der neue Algorithms beantwortet eine fundamentale Frage, der man seit mehreren Jahrhunderten auf der Spur ist.“
Allerdings ist mit einer sofortigen Nutzung der neuen Methode nicht zu rechnen. „Unser Algorithmus ist langsamer als die schnellsten bereits bekannten Testmethoden“, erläuterte Agrawal. Experten gehen davon aus, dass herkömmliche Verschlüsselungssoftware weiterhin eingesetzt wird. Mit der bestehenden vergleichsweise geringen Unsicherheit könnten viele Anwender gut leben. „Es handelt sich (beim neuen Algorithmus) um ein theoretisches Konzept und stellt als solches einen ersten Schritt dar“, erklärte Allender. „Wir sprechen hier von einem Türöffner. Nun sind Verfeinerungen und Verbesserungen von Nöten, um das ganze praktisch umsetzen zu können.“
Neueste Kommentare
1 Kommentar zu Krypto-Wissenschaftler knacken Primzahlenproblem
Kommentar hinzufügenVielen Dank für Ihren Kommentar.
Ihr Kommentar wurde gespeichert und wartet auf Moderation.
Kommentar zum Artikel
Diesen Artikel sollte man nicht allzu ernst nehmen. Das Ergebnis der indischen Mathematiker ist sensationell, aber aus anderen als den dargestellten Gründen.
Für die Belange der kryptografischen Anwendung sind die bekannten Algorithmen zum Beweis oder dem Ausschluß der Primzahleigenschaft einer vorgelegten natürlichen Zahl völlig ausreichend. Sie besitzen sogar in allen
getesteten Bereichen polynomiale Laufzeit, nur konnte man es nicht beweisen.
Ein Beweis würde dann existieren, wenn
die sog. "Erweiterte Riemannsche Vermutung" bewiesen wäre.
Die indischen Mathematiker haben dagegen das erste die mathematische Strenge und Ästhetik befriedigende Verfahren gefunden und den Beweis der Lösbarkeit des Primzahlproblems in Polynomzeit geliefert. Das ist ein Triumph in einer jahrhundertelangen Suche, von Gauß als für die Würde der Mathematik unbedingt notwendig gefordert, und in erster Linie ein Erkenntnisgewinn.