Primzahl prüfen und Primfaktorzerlegung

Primzahltest und Primfaktorzerlegung

Mit diesem Werkzeug können Sie jede ganze Zahl auf Primzahl prüfen und gleichzeitig die Primfaktorzerlegung sehen. Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist: 2, 3, 5, 7, 11, 13 und so weiter. Jede andere Zahl größer als 1 lässt sich eindeutig als Produkt von Primzahlen schreiben, etwa 360 = 2³ × 3² × 5. Aus der Zerlegung folgt auch die Anzahl der Teiler einer Zahl: Man addiert zu jedem Exponenten 1 und multipliziert, bei 360 also 4 × 3 × 2 = 24 Teiler.

Als Primzahltest dient das Miller-Rabin-Verfahren mit den ersten 13 Primzahlen als Basen. Für Zahlen unter 3,3 · 10²⁴ ist das Ergebnis damit beweisbar korrekt, darüber eine Aussage mit verschwindend kleiner Irrtumswahrscheinlichkeit. Zum Primfaktoren berechnen nutzt das Werkzeug zuerst Probedivision durch alle Primzahlen bis 10.000 und dann Pollards Rho-Methode in der Variante von Brent. Gerechnet wird mit BigInt, also ohne Rundungsfehler auch bei sehr großen Zahlen. Zusätzlich erscheinen die vorherige und die nächste Primzahl sowie die eulersche Phi-Funktion.

Grenzen: Zahlen, deren zwei kleinste Primfaktoren beide mehr als etwa 12 Stellen haben, lassen sich im Browser nicht in vertretbarer Zeit zerlegen. Genau darauf beruht die Sicherheit von RSA. In diesem Fall meldet das Werkzeug den nicht zerlegten Rest. Für gemeinsame Teiler mehrerer Zahlen nutzen Sie den ggT- und kgV-Rechner.