Primzahlen – Grundlagen und Bedeutung
Die Atome der natürlichen Zahlen und ihre Anwendungen
Primzahlen sind natürliche Zahlen größer als 1, die nur durch 1 und sich selbst teilbar sind. Sie gelten als die „Atome" der Arithmetik: Der Fundamentalsatz der Arithmetik besagt, dass jede natürliche Zahl größer als 1 eindeutig als Produkt von Primzahlen darstellbar ist. Diese Eigenschaft macht Primzahlen zur Grundlage der modernen Zahlentheorie und Kryptographie.
Der effizienteste Primzahltest für mittelgroße Zahlen ist der Trial-Division-Algorithmus: Man prüft alle Teiler von 2 bis zur Quadratwurzel der zu prüfenden Zahl. Ist keiner ein Teiler, ist die Zahl prim. Für n = 17: √17 ≈ 4,1, also teste 2, 3, 4 – keiner teilt 17 → 17 ist prim. Für große Zahlen (über 10⁷) werden probabilistische Tests wie Miller-Rabin verwendet, die deutlich schneller sind.
Die Primfaktorzerlegung schreibt jede zusammengesetzte Zahl als Produkt ihrer Primfaktoren. Für 12: 12 = 2 × 2 × 3. Diese Zerlegung ist die Basis für die Berechnung von GGT und KGV. Der RSA-Verschlüsselungsalgorithmus, der das Internet sichert, basiert auf der Tatsache, dass die Primfaktorzerlegung großer Zahlen (hunderte Stellen) praktisch unmöglich ist – selbst für moderne Supercomputer.
Bekannte Primzahlreihen: Die Menge der Primzahlen unter 100 umfasst 25 Zahlen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Die Mersenne-Primzahlen(Zahlen der Form 2ⁿ − 1, z. B. 31 = 2⁵ − 1) sind für die Suche nach besonders großen Primzahlen relevant. Die aktuell größte bekannte Primzahl hat über 40 Millionen Dezimalstellen und ist eine Mersenne-Primzahl.