Wofür Primzahltest gedacht ist
Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist. Die ersten lauten 2, 3, 5, 7, 11, 13, 17, 19 … – und nein, die 1 zählt bewusst nicht dazu. Ist Ihre Zahl keine Primzahl, lässt sie sich in Teiler zerlegen, und genau diese Primfaktorzerlegung blendet der Rechner ein. Kleine Zahlen prüft er durch Probeteilung, für große nutzt er einen deterministischen Miller-Rabin-Test, der bis weit in Billionenhöhe zuverlässig entscheidet.
Bedienung
- Tragen Sie die zu prüfende ganze Zahl ein.
- Ab in den Prüfkessel mit „Prüfen“.
- Steht da, ob es eine Primzahl ist – und sonst die Zerlegung samt Nachbar-Primzahlen.
Typische Anwendungen: Kryptografie: Kandidaten-Primzahlen für RSA auf Tauglichkeit prüfen., Schule: Teiler und Primzahlen im Unterricht wiedererkennen., Informatik: Primzahlen als Hash-Größen wählen, um Kollisionen zu drücken..
Fragen und Antworten
Was genau ist eine Primzahl?
Eine natürliche Zahl > 1, die nur durch 1 und sich selbst teilbar ist.
Ist die 1 eine Primzahl?
Nein, die Reihe fängt per Definition bei der 2 an.
Warum ist 2 die einzige gerade Primzahl?
Jede andere gerade Zahl ist durch 2 teilbar.
Wie sicher ist der Test bei großen Zahlen?
Bis rund 3,3·10^24 exakt, weil deterministisch.
Einschränkungen
Ganze Zahlen ab 2. Der Miller-Rabin-Test ist hier deterministisch abgesichert für alle Zahlen unterhalb von etwa 3,3·10^24, darüber wird es ein Schätzwert.
Was das Werkzeug kann
Zuverlässiger Primzahltest auch für sehr große Zahlen, Miller-Rabin-Test für große Werte, Probeteilung für kleine, Vorhergehende und nachfolgende Primzahl, Bei Nicht-Primzahlen die zugehörige Primfaktorzerlegung, Sofortige Antwort ohne Wartezeit
Diese Werkzeuge passen: