Was ist eine Primzahl?
Eine Primzahl ist eine natürliche Zahl größer als 1, die sich nur durch 1 und sich selbst ohne Rest teilen lässt. Die kleinsten Primzahlen sind 2, 3, 5, 7, 11 und 13.
Die Zahl 1 ist keine Primzahl, da sie nur einen einzigen Teiler hat. Primzahlen haben immer genau zwei verschiedene Teiler. Alle anderen natürlichen Zahlen größer als 1 heißen zusammengesetzte Zahlen und lassen sich in Primfaktoren zerlegen.
Wie funktioniert der Primzahl-Rechner
Unser Primzahl-Rechner analysiert jede natürliche Zahl von 1 bis 1.000.000.000.000.000.
Eingaben
- Zahl eingeben: Eine ganze Zahl in das Eingabefeld eintragen und auf Primzahl berechnen klicken oder die Enter-Taste drücken.
Ergebnisse
Nach der Berechnung zeigt unser Rechner folgende Informationen:
- Primzahltest: Unser Rechner zeigt sofort an, ob die eingegebene Zahl eine Primzahl ist oder nicht. Das Ergebnis erscheint farbig: Grün für Primzahl, Rot für keine Primzahl, Orange für die Sonderstellung der 1.
- Teileranzahl: Bei Primzahlen immer 2 (1 und die Zahl selbst). Bei zusammengesetzten Zahlen wird die genaue Anzahl aller Teiler angezeigt.
- Primfaktorzerlegung: Zusammengesetzte Zahlen werden vollständig in ihre Primfaktoren zerlegt. Alle Rechenschritte sind einzeln aufgelistet.
- Benachbarte Primzahlen: Unser Rechner zeigt die nächste kleinere und größere Primzahl mit ihrem jeweiligen Abstand. Per Klick lässt sich von Primzahl zu Primzahl weiternavigieren.
Die Primzahl-Formeln
Der Rechner verwendet zwei Formeln: eine für die Primfaktorzerlegung und eine für die Teileranzahl.
1. Primfaktorzerlegung
Jede zusammengesetzte Zahl lässt sich eindeutig als Produkt von Primzahlen darstellen:
n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ
p₁, p₂, ... sind die Primfaktoren, a₁, a₂, ... ihre Exponenten. Zum Beispiel: 12 = 2² × 3¹ hat die Primfaktoren 2 (Exponent 2) und 3 (Exponent 1).
2. Teileranzahl
Die Anzahl aller Teiler ergibt sich direkt aus den Exponenten der Primfaktorzerlegung:
Teileranzahl = (a₁ + 1) × (a₂ + 1) × ... × (aₖ + 1)
Der Grund: Für jeden Primfaktor p mit Exponent a kann man p⁰, p¹, ..., pᵃ als Teiler wählen, also a + 1 Möglichkeiten. Für 12 = 2² × 3¹ ergibt das (2+1) × (1+1) = 6 Teiler: 1, 2, 3, 4, 6, 12.
Beispiele für die Primzahlprüfung
Die folgenden Beispiele zeigen, wie unser Rechner eine Zahl prüft und den Rechenweg darstellt.
Beispiel 1 (Primzahl)
Eingabe: 6.037
Der Rechner prüft 6.037 mit dem Miller-Rabin-Test. Dabei wird die Zahl gegen 12 mathematische Zeugen geprüft. Besteht sie alle 12 Tests, ist sie mit Sicherheit eine Primzahl.
Prüfmethode: Miller-Rabin (deterministisch)
Zeugen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
Ergebnis: Alle 12 Zeugen bestätigt → Primzahl
Teileranzahl: 2 (nur 1 und 6.037)
6.037 ist eine Primzahl. Die nächste Primzahl darunter ist 6.029 (Abstand: 8), die nächste darüber 6.043 (Abstand: 6).
Beispiel 2 (Keine Primzahl)
Eingabe: 8.579
Der Rechner versucht, 8.579 durch aufsteigende Primzahlen zu teilen. Erst 23 geht ohne Rest auf. Der verbleibende Quotient 373 ist eine Primzahl, damit ist die Zerlegung abgeschlossen.
8.579 ÷ 2 → kein Teiler
8.579 ÷ 3 → kein Teiler
8.579 ÷ 5 → kein Teiler
8.579 ÷ 7 → kein Teiler
8.579 ÷ 11 → kein Teiler
8.579 ÷ 13 → kein Teiler
8.579 ÷ 17 → kein Teiler
8.579 ÷ 19 → kein Teiler
8.579 ÷ 23 = 373
373 ist eine Primzahl → fertig
Ergebnis: 8.579 = 23 × 373
Teileranzahl: (1+1) × (1+1) = 4
8.579 hat genau 4 Teiler: 1, 23, 373 und 8.579. Die benachbarten Primzahlen sind 8.573 (Abstand: 6) und 8.581 (Abstand: 2).
Beispiel 3 (Vielfache Primfaktoren)
Eingabe: 720
720 lässt sich mehrfach durch dieselben Primzahlen teilen. Der Rechner dividiert so lange durch 2, bis kein Rest mehr bleibt, dann dasselbe mit 3 und 5.
720 ÷ 2 = 360
360 ÷ 2 = 180
180 ÷ 2 = 90
90 ÷ 2 = 45 → 2 erschöpft (2⁴)
45 ÷ 3 = 15
15 ÷ 3 = 5 → 3 erschöpft (3²)
5 ist eine Primzahl → fertig (5¹)
Ergebnis: 720 = 2⁴ × 3² × 5¹
Teileranzahl: (4+1) × (2+1) × (1+1) = 5 × 3 × 2 = 30
720 hat 30 Teiler. Jede Kombination aus 2⁰ bis 2⁴, 3⁰ bis 3² und 5⁰ bis 5¹ ergibt einen anderen Teiler.
Der Miller-Rabin-Primzahltest
Der Primzahltest in unserem Rechner verwendet den deterministischen Miller-Rabin-Test mit 12 festen Zeugen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 und 37.
Mit diesen 12 Zeugen liefert der Test für alle natürlichen Zahlen bis 3,3 × 10²⁴ garantiert korrekte Ergebnisse.
Das Grundprinzip basiert auf dem Kleinen Fermatschen Satz. Für eine Primzahl p und jede ganze Zahl a gilt:
a^(p-1) ≡ 1 (mod p)
Das ≡ steht für kongruent: Beide Seiten ergeben denselben Rest bei Division durch p. mod p bezeichnet diesen Divisionsrest.
Der Test schreibt p - 1 als 2ʳ × d (mit ungeradem d) und prüft für jeden Zeugen a, ob die Bedingung gilt. Schlägt sie für einen Zeugen fehl, ist die Zahl mit Sicherheit zusammengesetzt. Bestehen alle 12 Zeugen den Test, ist die Zahl eine Primzahl.
Der Test läuft in Millisekunden, selbst für sehr große Zahlen. Die Probedivision wird ausschließlich für die Primfaktorzerlegung zusammengesetzter Zahlen eingesetzt.
Primfaktorzerlegung mit Probedivision
Die Primfaktorzerlegung stellt eine zusammengesetzte Zahl als Produkt von Primzahlen dar. Der Fundamentalsatz der Arithmetik besagt, dass jede natürliche Zahl größer als 1 genau eine solche Darstellung besitzt.
Unser Rechner verwendet die Probedivision: Die Zahl wird nacheinander durch aufsteigende Primzahlen geteilt, bis der verbleibende Rest gleich 1 ist.
Teile durch 2, solange möglich
Teile durch 3, solange möglich
Teile durch 5, 7, 11, 13, ... (alle Primzahlen bis zur Wurzel von n)
Verbleibender Rest > 1: ist selbst eine Primzahl
Die Teileranzahl einer Zahl ergibt sich direkt aus ihrer Primfaktorzerlegung. Für n = p₁^a₁ × p₂^a₂ × ... gilt:
Teileranzahl = (a₁ + 1) × (a₂ + 1) × ...
Für 360 = 2³ × 3² × 5 ergibt das (3+1) × (2+1) × (1+1) = 24 Teiler.
Warum gibt es unendlich viele Primzahlen
Diese Frage beantwortete Euklid bereits um 300 v. Chr. durch einen Widerspruchsbeweis.
- Annahme: Es gibt nur endlich viele Primzahlen: p₁, p₂, ..., pₙ.
- Konstruktion: Man bildet die Zahl N = (p₁ × p₂ × ... × pₙ) + 1, also das Produkt aller angenommenen Primzahlen plus 1.
- Widerspruch: Bei Division von N durch jede bekannte Primzahl bleibt immer Rest 1. Also ist N entweder selbst eine Primzahl oder hat einen Primteiler, der nicht in der Liste steht. In beiden Fällen fehlt eine Primzahl in der Liste.
Das Argument gilt für jede endliche Liste, egal wie lang sie ist. Eine vollständige Liste aller Primzahlen kann es daher nicht geben.
Die genaue Verteilung der Primzahlen über die natürlichen Zahlen ist hingegen bis heute nicht vollständig geklärt. Die Riemannsche Hypothese macht präzise Aussagen über diese Verteilung und gilt als eines der bedeutendsten offenen Probleme der Mathematik.
Anwendungen von Primzahlen
Primzahlen sind die Grundlage moderner digitaler Sicherheit. Der Grund: Das Produkt zweier großer Primzahlen lässt sich leicht berechnen, aber praktisch nicht faktorisieren. Diese Asymmetrie nutzen viele kryptographische Verfahren.
- RSA-Verschlüsselung: Das verbreitetste asymmetrische Verschlüsselungsverfahren basiert auf dem Produkt zweier großer Primzahlen mit je 1.024 bis 4.096 Bit. Die Rückrechnung in die Ausgangsprimzahlen ist selbst für Hochleistungsrechner praktisch nicht durchführbar.
- Diffie-Hellman-Schlüsselaustausch: Zwei Parteien einigen sich über eine öffentlich bekannte Primzahl auf einen gemeinsamen geheimen Schlüssel, ohne diesen jemals direkt übertragen zu müssen.
- Kryptografische Hashfunktionen: Algorithmen wie SHA-256 nutzen modulare Arithmetik mit Primzahlen, um kollisionsresistente Prüfsummen für Passwörter, digitale Signaturen und Dateiintegrität zu erzeugen.
- Pseudozufallszahlgeneratoren: Kryptografisch sichere Generatoren (CSPRNG) verwenden Primzahlen für gleichmäßige und nicht vorhersagbare Zufallsverteilungen in Sicherheitsanwendungen.