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 15 933. 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 Beispiel lauten die Primfaktoren 2 × 3 × 3 × 7. Alle anderen Zerlegungen von 126, etwa 9 × 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 15 933 durch sie teilen kann. Erweist sich 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 15 933.
Auf die vermeintliche Scherzfrage gibt es also nur 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 zusammengesetzte 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 solchen Verschlüsselungsverfahren 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.