Ist deine Zahl eine Primzahl?

So funktioniert es

Eine Primzahl ist eine ganze Zahl größer als 1, deren einzige Teiler 1 und sie selbst sind: 2, 3, 5, 7, 11 und so weiter. Jede andere Zahl größer als 1 ist zusammengesetzt und lässt sich bis auf die Reihenfolge eindeutig als Produkt von Primzahlen schreiben: 1200 = 2⁴ × 3 × 5². Die Zahlen 0 und 1 sind weder prim noch zusammengesetzt.

Für große Zahlen wäre die Division durch alle möglichen Faktoren viel zu langsam. Deshalb wird der Miller-Rabin-Test verwendet. Er sucht bei Potenzen einer Basis a nach einem Muster, dem jede Primzahl folgen muss. Zusammengesetzte Zahlen verletzen es meist; eine solche Basis heißt Zeuge. Unter etwa 3,3 × 10²⁴ erkennen die ersten 13 Primzahlen als feste Basen nachweislich jede zusammengesetzte Zahl. Dort ist „Primzahl“ also bewiesen. Darüber ist keine feste Auswahl bewiesen. Besteht eine Zahl 20 Basen, erscheint „Wahrscheinlich Primzahl“: praktisch sehr sicher, aber kein Beweis. „Keine Primzahl“ ist immer bewiesen.

Primfaktoren werden durch Probedivision gefunden, die bis 10¹⁵ (eine Billiarde) sofort fertig ist. Darüber wird eine zusammengesetzte Zahl als solche erkannt, hier aber nicht zerlegt. Das ist kein Zufall: Primzahlen zu erkennen ist viel leichter, als ihre Faktoren zu finden. Darauf beruht ein großer Teil moderner Verschlüsselung.