Primzahlen sind die Bausteine der ganzen Zahlen: Jede ganze Zahl über 1 ist entweder eine Primzahl oder ein eindeutiges Produkt von Primzahlen. Dieser Rechner testet die Primalität, faktorisiert Zahlen und listet Primzahlen in einem Bereich auf – und zwar sogar für Zahlen, die viel zu groß für eine Tabellenkalkulation sind, und zwar unter Verwendung desselben Miller-Rabin-Tests, der der modernen Kryptographie zugrunde liegt.
Was macht eine Zahl zu einer Primzahl?
Eine Primzahl hat genau zwei positive Teiler: 1 und sich selbst. Diese Definition schließt 1 (die nur einen Teiler hat) und 0 (die durch alles teilbar ist) aus, daher ist die kleinste Primzahl 2 – und es ist die einzige gerade Primzahl, da jede andere gerade Zahl durch 2 teilbar ist.
Um eine Zahl von Hand zu überprüfen, müssen Sie nur Teiler bis zu ihrer Quadratwurzel testen. Wenn keine ganze Zahl von 2 bis √n n teilt, dann ist n eine Primzahl. Aus diesem Grund benötigt 97 nur vier Probeabteilungen (2, 3, 5, 7) statt fünfundneunzig.
Faktorisierung und das Sieb
Der Grundsatz der Arithmetik garantiert, dass jede ganze Zahl über 1 auf genau eine Weise in Primzahlen zerlegt wird. Die Primfaktorzerlegung ermöglicht alles, von der Reduzierung von Brüchen bis hin zur Suche nach den kleinsten gemeinsamen Vielfachen. Dieses Werkzeug verwendet Probedivision, um den kleinsten Primfaktor wiederholt abzutrennen, bis nur noch 1 übrig bleibt.
Um alle Primzahlen in einem Bereich zu finden, ist die schnellste klassische Methode das Sieb von Eratosthenes: Listen Sie die Zahlen auf und streichen Sie dann die Vielfachen von 2, dann von 3, dann von 5 usw. durch. Was überlebt, ist erstklassig. Ein segmentiertes Sieb wendet die gleiche Idee nur auf das von Ihnen gewünschte Fenster an, wodurch es auch über Millionen von Zahlen hinweg schnell bleibt.
Große Zahlen und Kryptographie
Eine Probeteilung ist aussichtslos, sobald die Zahlen groß werden – das Testen einer 60-stelligen Zahl würde länger dauern als das Alter des Universums. Stattdessen wechselt dieser Rechner zum Miller-Rabin-Test, der modulare Potenzierung verwendet, um die Primalität in Sekundenbruchteilen zu bestimmen. Mit einem festen Satz von Zeugenbasen ist der Test für jede Zahl unter 3,3 × 10²⁴ nachweislich genau.
Dies ist wichtig, weil große Primzahlen die Grundlage der Public-Key-Kryptographie sind. Bei der RSA-Verschlüsselung werden zwei enorme Primzahlen miteinander multipliziert, um einen öffentlichen Schlüssel zu bilden. Seine Sicherheit beruht auf der Tatsache, dass es außerordentlich schwierig ist, das Produkt wieder in diese Primzahlen zu zerlegen, obwohl es einfach ist, einen Kandidaten auf Primzahl zu testen. Die Asymmetrie zwischen schnellem Primalitätstest und langsamem Faktorisieren ist genau das, was den verschlüsselten Datenverkehr sicher hält.