Primfaktorzerlegung-Rechner
Zerlegen Sie jede Zahl in ihre Primfaktoren (z. B. 360 = 2³ × 3² × 5) und prüfen Sie, ob eine Zahl eine Primzahl ist.
1.180 Aufrufe
So funktioniert es
Primfaktorzerlegung bedeutet, eine Zahl als Produkt ihrer primen Bausteine zu schreiben — zum Beispiel 60 = 2² × 3 × 5. Der Fundamentalsatz der Arithmetik garantiert, dass jede ganze Zahl größer als 1 genau eine solche Zerlegung besitzt (abgesehen von der Reihenfolge der Faktoren): Es gibt nur einen Weg, 60 in Primfaktoren zu zerlegen, egal in welcher Reihenfolge Sie zu teilen versuchen. Diese Eindeutigkeit macht die Primfaktorzerlegung zu einer sinnvollen, wohldefinierten Operation und nicht zu einer Frage der Wahl.
Das Tool findet sie durch Probedivision: Zuerst teilt es so oft wie möglich durch 2 heraus (und zählt, wie oft 2 glatt hineingeht), dann geht es zu ungeraden Kandidaten über — 3, 5, 7, 9, 11 … — und teilt jeden so oft heraus, wie er passt, bis zur Quadratwurzel dessen, was noch übrig ist. Beispielrechnung für 360: dreimal durch 2 teilen (360→180→90→45, also 2³), dann ist 45 ungerade — zweimal durch 3 teilen (45→15→5, also 3²), dann bleibt 5 übrig und ist selbst prim (5¹). Ergebnis: 360 = 2³ × 3² × 5, und die Rückmultiplikation — 8 × 9 × 5 — bestätigt 360. Teilt kein Kandidat bis √n die verbleibende Zahl glatt, ist diese verbleibende Zahl selbst prim und schließt die Zerlegung ab.
Was Sie wissen sollten
Kleine und mittelgroße Zahlen lassen sich auf diese Weise nahezu sofort zerlegen. Doch derselbe Probedivisions-Ansatz wird für sehr große Zahlen — Hunderte von Stellen — rechnerisch extrem aufwendig, weil die Zahl der zu prüfenden Kandidaten enorm wächst, und es ist für klassische Rechner kein bekannter effizienter (polynomialzeitlicher) Algorithmus für allgemeine ganze Zahlen bekannt. Diese Asymmetrie — zwei große Primzahlen zu multiplizieren ist schnell, ihr Produkt wieder in die Faktoren zu zerlegen ist langsam — ist nicht nur eine Kuriosität, sondern genau die Sicherheitsgrundlage der RSA-Public-Key-Kryptografie: Ein öffentlicher Schlüssel wird aus dem Produkt zweier riesiger geheimer Primzahlen gebildet, und die Verschlüsselung zu brechen würde erfordern, dieses Produkt zu faktorisieren — bei den heute verwendeten Schlüsselgrößen derzeit undurchführbar.
- Die 1 hat überhaupt keine Primfaktorzerlegung — sie ist weder prim noch zusammengesetzt, und die Konvention des "leeren Produkts" behandelt sie als Sonderfall.
- Eine Zahl, die die Probedivision bis zu ihrer eigenen Quadratwurzel übersteht, ohne dass etwas sie teilt, ist per Definition prim.
- Über die Kryptografie hinaus liegt die Zerlegung dem Kürzen von Brüchen, dem Finden des größten gemeinsamen Teilers (ggT) und des kleinsten gemeinsamen Vielfachen (kgV) sowie der Bestimmung, wie viele Teiler eine Zahl hat, zugrunde.
Häufig gestellte Fragen
Ist 1 eine Primzahl?
Nein. Primzahlen haben genau zwei verschiedene positive Teiler; die 1 hat nur einen (sich selbst). Der Ausschluss der 1 hält Primfaktorzerlegungen eindeutig — der Fundamentalsatz der Arithmetik würde sonst zusammenbrechen, da man jede Zerlegung mit beliebig vielen zusätzlichen Faktoren von 1 auffüllen könnte.
Wofür wird die Faktorisierung verwendet?
Zum Kürzen von Brüchen, zum Finden des ggT und kgV zweier Zahlen, und — am bekanntesten — sie ist die Grundlage der RSA-Kryptografie, bei der die Schwierigkeit, das Produkt zweier riesiger Primzahlen zu faktorisieren, den verschlüsselten Internetverkehr sicher hält.
Warum gilt die Faktorisierung großer Zahlen als "schwer"?
Probedivision und ihre Verfeinerungen müssen eine Anzahl von Kandidaten prüfen, die mit der Größe der Eingabe sehr schnell wächst. Es ist kein effizienter klassischer Algorithmus bekannt, um eine beliebige große Zahl schnell zu faktorisieren — anders als die Multiplikation, die im Prinzip in beide Richtungen schnell ist. Genau diese Lücke nutzen Kryptografen aus.
Wie hängt die Faktorisierung mit der RSA-Verschlüsselung zusammen?
Ein öffentlicher RSA-Schlüssel wird durch die Multiplikation zweier großer, zufällig gewählter Primzahlen abgeleitet. Jeder kann sie multiplizieren, um den öffentlichen Schlüssel zu erhalten, aber diesen Schritt umzukehren — das Produkt zurück in seine beiden Primfaktoren zu zerlegen — ist die rechnerische Mauer, die den privaten Schlüssel schützt.
Was passiert, wenn ich direkt eine Primzahl eingebe?
Das Tool findet keinen Teiler bis zur Quadratwurzel und meldet daher die Zahl selbst als einzigen Primfaktor, hoch zur ersten Potenz — das bestätigt, dass sie prim und nicht zusammengesetzt ist.
Ähnliche Tools
Problem melden
Primfaktorzerlegung-Rechner
Kommentare
Noch keine Kommentare — schreiben Sie den ersten!