Klagenfurt/Wien - Können Sie die Primzahlen 761 und 1913 multiplizieren? (Diese Zahlen heißen so, weil sie nur durch sich selbst und durch 1 teilbar sind.) Mit einem Taschenrechner eine Sekundenaufgabe: 761 mal 1913 gleich 1,455.793. Der umgekehrte Weg, aus einem Produkt die zwei multiplizierten Primzahlen abzuleiten, ist ungleich schwieriger. Das ist wie bei jemandem, der ein Glas Salz und ein Glas Zucker vor sich stehen hat: Den Inhalt beider Gläser in ein Gefäß zu schütten ist in Sekunden erledigt. Wer aber vermag, aus dem Gemisch wieder Salz und Zucker zu trennen? Während das Mischen von Salz und Zucker eine Kinderei ist, stellt das Multiplizieren großer Primzahlen eine der brisantesten Aufgaben der Erwachsenenwelt dar: Zahlen wie 1,455.793 dienen nämlich als Grundlage zur so guten Chiffrierung von Botschaften, dass sie niemand mehr lesen kann -- mit Ausnahme derjenigen, welche die Teiler 761 und 1913 kennen. Denn nur mit deren Hilfe lassen sich die codierten Mitteilungen entschlüsseln. Der berüchtigte Briefbombenleger Franz Fuchs bediente sich dieser Verschlüsselungsmethode: Er multiplizierte zwei riesengroße Primzahlen und chiffrierte mit dem Produkt seine irren Botschaften der "Bajuwarischen Befreiungsarmee". Dekodieren dauert Detail am Rande: Fuchs ging dabei ungeschickt -- oder absichtlich ungeschickt -- vor, indem er zwei etwa gleich große Primzahlen verwendete und so den Mathematikern in der Polizei die Entdeckung dieser Teiler aus dem vorgelegten Produkt erheblich erleichterte: Statt Monate, wie es bei solchen Dekodierungsaufgaben die Regel ist, benötigten sie bloß Tage. Für Geschäftsgeheimnisse und Geheimdienste ist die sichere Verschlüsselung von Botschaften das tägliche Brot. Darum benötigen sie die Kenntnis von Primzahlen, von sehr großen Primzahlen, idealerweise von Primzahlen, die nur sie kennen. Fragt sich nur: Gibt es genügend viele Primzahlen? Mit einem raffinierten Argument bewies der griechische Mathematiker Euklid schon vor 2300 Jahren, dass es unendlich viele Primzahlen gibt. Ihre Fülle ist bemerkenswert groß: Zwischen eins und einer Million gibt es etwa 78.498. Wie die Medizin Diagnosen für Krankheiten hat, so hat die Mathematik Tests für Primzahlen entwickelt. Will man sicher testen, muss man teure, komplizierte Prozesse auf sich nehmen. Winfried Müller, Mathematiker an der Universität Klagenfurt, untersucht im Rahmen eines FWF-Projekts die Qualität von Primzahltests. Ein solcher Test lautet zum Beispiel: Man multipliziere die Zahl zwei siebenmal mit sich und dividiere das Ergebnis (128) durch sieben. Dabei bleibt zwei als Rest -- und dies, wie der Jurist und Hobbymathematiker Pierre de Fermat schon vor mehr als 300 Jahren feststellte, weil sieben eine Primzahl ist. Wenn man 2 neunmal mit sich multipliziert und das Ergebnis 512 durch 9 dividiert, bleibt der Rest 8 und nicht 2 -- neun ist eben keine Primzahl. Wenn man 2 elfmal mit sich multipliziert und das Ergebnis 2048 durch 11 dividiert, bleibt wieder der Rest 2. Klar: 11 ist eine Primzahl. Für den binär rechnenden Computer wäre dies ein idealer Test: Wenn man 2 zum Beispiel 341-mal mit sich multipliziert, ist dies, im Dualsystem geschrieben, einfach nur eine 1 gefolgt von 341 Nullen. Dividiert man diese Zahl durch 341, bleibt der Rest 2 -- aber leider: 341 ist keine Primzahl, sondern als Produkt von 11 mit 31 eine Pseudoprimzahl. Hier würde der Test also irren. Einen Primzahltest zu finden, der einfach, aber wasserdicht ist -- Millionen verdiente man damit. (DER STANDARD, Print-Ausgabe, 2. 10. 2001)