Schneller Primzahltest

News: Schneller Primzahltest

Kleine Zahlen lassen sich durch ein wenig systematisches Probieren noch relativ schnell als Primzahl überführen. Bei Größeren klappt es nur noch mit Tricks oder dem Computer. Aber selbst dieser kommt bei einigen Tausend Stellen gehörig ins Schleudern, es sei denn, er verwendet den neuen Algorithmus dreier indischer Informatiker.

Thorsten Krome

Schon früh konnten sich die Menschen an der Suche nach Primzahlen begeistern – jener Zahlen, die nur die Eins und sich selbst als Teiler besitzen. So liefert das Sieb des Eratosthenes (etwa 240 vor Christus) völlig korrekt die Serie von Primzahlen. Besonders effizient ist der Algorithmus jedoch nicht, da die Zeit zur Überprüfung einer Zahl n exponentiell von der Problemgröße also ihrer Stellenzahl abhängt. Und auch das systematische Probieren potenzieller Teiler von 2 bis √(n) wird bei großen Zahlen schnell recht mühselig.

Etwas schneller und eleganter funktioniert es mit dem Test, den Pierre de Fermat (1601 bis 1665) erfand. In der einfachsten Version muss dazu lediglich geprüft werden, ob die mutmaßliche Primzahl n Teiler von 2^n-1-1 ist. Wie Fermat beweisen konnte, trifft das nämlich für alle ungeraden Primzahlen zu. Bleibt also ein Rest, so kann man sich sicher sein, dass die Zahl keine Primzahl ist. Geht die Rechnung allerdings glatt auf, so ist es zwar sehr wahrscheinlich, dass n prim ist, doch eine endgültige Aussage lässt sich noch nicht treffen. Denn dazu müsste sich n eigentlich für beliebige natürliche Zahlen a als Teiler von 2^a-1-1 beweisen – ein erheblicher Aufwand, der sich oftmals nicht rechnet, zumal es seltene zusammengesetzte Zahlen gibt, die den Fermattest zu jeder Basis bestehen. Sicherheit gab es bisher also nur in exponentieller Zeit.

Aber Rettung scheint in Sicht, denn Manindra Agrawal, Neeraj Kayal und Nitin Saxena vom Indian Institute of Technology in Kanpur stellen nun einen Algorithmus vor, der auch bei sehr großen Primzahlen nicht schlapp macht, oder gerade hier seine Stärken ausspielt. Zwar basiert er, wie andere moderne Suchalgorithmen für Primzahlen auch, auf einer Art Fermat-Test, doch reduziert er zunächst einmal durch eine trickreiche Kombination vorangehender Proben die Zahl der Test-Durchläufe auf ein erträgliches Maß. Wer jetzt seitenweise komplizierte Ausdrücke und mathematische Formeln vermutet, der wird überrascht sein, wie einfach der Algorithmus aufgebaut ist. In gerade mal 13 Zeilen präsentiert sich das Werk der Informatiker.

Dabei reichen ihnen fünf Verzweigungen und zwei Schleifen, um Zahlenpaare zu finden, die gewissen Bedingungen genügen. Geht die Suche leer aus, dann ist die Eingabe eine Primzahl. Bei kleinen Zahlen ist das Verfahren zwar herkömmlichen Algorithmen nicht überlegen. Bei sehr, sehr großen Zahlen kann die Suche jedoch deutlich schneller erledigt sein, da der Algorithmus mit polynomialer Zeit auskommt, das heißt, die Rechenzeit wächst in Abhängigkeit der Problemgröße nicht ganz so schnell wie bei den sonst gängigen Verfahren.

Von einer "erfreulichen Überraschung" spricht denn auch Carl Pomerance, seines Zeichens Zahlentheoriker an den Bell Labs in Murray Hill, angesichts der Tatsache, dass ein solch einfacher Algorithmus all die Jahre übersehen wurde. Kryptographen könnten der Entdeckung indes mit gemischten Gefühlen gegenüberstehen. Schließlich baut die Sicherheit vieler Verschlüsselungsverfahren (zumindest der so genannten RSA-Verfahren) darauf, dass auch sehr schnelle Computer lange brauchen, um eine große Zahl in ihre Primfaktoren zu zerlegen. Zwar ist von Primfaktorzerlegung noch nicht die Rede, aber wer weiß, was noch möglich ist? Oder wie Pomerance fragt: "Was haben wir noch übersehen?"