Man weiss Folgendes: Das Produkt aus dem Alter des Kapitäns (in Jahren), der Anzahl seiner Kinder und der Länge seines Schiffes (in Metern) beträgt 15933 Wie alt ist der Kapitän? Die alte Scherzfrage, mag der Leser denken. Weit gefehlt! Versucht man nämlich drei Zahlen zu finden, die miteinander multipliziert 15 933 ergeben, zeigt sich Erstaunliches.
Bei der Zerlegung einer Zahl in möglichst viele Faktoren bleiben am Schluss nur Primzahlen übrig – Zahlen grösser eins, die sich nur durch sich selber und durch eins teilen lassen. Für die Zahl 126 zum Beispiellauten die Primfaktoren 2x3x3x7. Alle anderen Zerlegungen von 126, etwa 9x 14 oder 6×21, enthalten Faktoren, die sich in die genannten Primzahlen weiterzerlegen lassen. Jeder Zahl kann man also eine eindeutige Menge von Primfaktoren zuordnen.
Um die Primfaktoren von 15 933 zu suchen, nimmt man am besten eine Liste der Primzahlen von 2 an aufwärts und probiert der Reihe nach, ob man 15933 durch sie teilen kann. Erweist sich hier bereits die 3 als brauchbarer Teiler, muss man sich für weitere Erfolge bis 47 und 113 gedulden. Und siehe da: Diese drei Primzahlen (und nur diese) ergeben miteinander multipliziert 15933.
Auf die vermeintliche Scherzfrage gibt es also eine ernsthafte Antwort: als Alter des Kapitäns kommt nur 47 in Frage. Und wie die beiden anderen Primfaktoren der Anzahl Kinder sowie der Länge des Schiffes zuzuordnen sind, ist in diesem Fall auch eindeutig.
Mit der Eindeutigkeit der Primzahlzerlegung arbeitet heute das wohl sicherste System zur Verschlüsselung von Nachrichten. Nimmt man zwei sehr grosse Primzahlen, zum Beispiel solche mit je 70 Stellen, und multipliziert sie miteinander, ergibt sich eine zusammen-gesetzte Zahl mit etwa 140 Stellen. Derart grosse Primzahlen lassen sich mit Computerhilfe leicht finden und auch multiplizieren. Für den umgekehrten Schritt -das Aufspüren der zwei Primfaktoren bei Kenntnis der zusammengesetzten Riesenzahl – gibt es aber kein praktikables mathematisches Verfahren.
Dieser Sachverhalt wird bei Verschlüsselungsverfahren nun ausgenutzt: Eine geheime Botschaft, die mit Hilfe der zusammengesetzten Zahl codiert und übermittelt wird, kann vom legitimen Empfänger nur dechiffriert werden, weil er die beiden Primfaktoren kennt.