Wie kann man beweisen, dass eine Zahl keine Primzahl ist?
Hallo,
gibt es da Methoden, wenn die Zahl ungerade ist und so riesig, dass man nicht mit dem Taschenrechner jede mal durchprobieren kann?
Vielen Dank
5 Antworten
Es gibt statistische Primzahltests. Die geben Dir aber nur eine gewisse Wahrscheinlichkeit an, dass die Zahl eine Primzahl ist. Diese Wahrscheinlichkeit lässt sich aber steigern (durch zusätzlichen Rechenaufwand).
Such mal nach Miller-Rabin-Test.
Wenn Du "absolute Sicherheit" haben willst, musst Du sie durch einen Faktorisierungsalgorithmus jagen, der kein so genanntes "Monte-Carlo-Verfahren" ist. (Ein "Monte-Carlo-Verfahren" ist ein Algorithmus, der auch mit einer gewissen Wahrscheinlichkeit ein falsches Ergebnis liefern darf.)
Genau! Aber wenn er diese Aussage nicht liefert, weiß man nichts. Die Zahl könnte prim sein ... oder auch nicht.
Das heißt der Test hat als "Primzahltest" sozusagen "false positives" (erkennt zusammengesetzte Zahlen mit einer gewissen Wahrscheinlichkeit "fälschlicherweise" als prim), jedoch keine "false negatives" (erkennt Primzahlen nicht "fälschlicherweise" als zusammengesetzt).
Ist die Frage, ob der auch bei einer über 4000 Ziffern langen Zahl funktioniert/ ich bei einer so großen Zahl diesen Test machen kann.
Bei 4096 Bit (binären Ziffern) langen Zahlen funktioniert es auf jeden Fall, weil die als Schlüssel für RSA verwendet werden. 4000 Dezimalstellen ist natürlich "etwas" größer.
Soweit ich weiß, ist dem Algorithmus die Länge der Zahl aber grundsätzlich "egal". Möglicherweise steigt die Laufzeit an, aber ich denke, es ist von der Seite durchaus noch möglich, auch das noch auf einem "normalen" Rechner herauszubekommen. Die Herausforderung wird sein, mit der Zahl überhaupt Arithmetik betreiben zu können. Musst mal überprüfen, ob die normalen "arbitrary precision arithmetic"-Bibiliotheken dafür ausreichen. Ich denke schon.
Unter Java könntest Du etwa den Datentyp "java.math.BigInteger" verwenden oder unter .NET "System.Numerics.BigInteger".
Java hat sogar den entsprechenden Algorithmus bereits implementiert in einer Methode namens ".isProbablyPrime()". Wenn die "false" zurückliefert, ist die Zahl definitiv zusammengesetzt. Wenn sie "true" zurückliefert, die Zahl "vermutlich" prim.
wenn du eine riesenzahl hast, schau erst mal, ob sie gerade oder ungerade ist. ist sie gerade, ist es keine primzahl (damit sind die hälfte alles möglichkeiten schonmal weg)
dummerweise ist die hälfte von unendlich auch unendlich...
ach, vergessen, guckst du hier:
https://de.wikipedia.org/wiki/Primzahltest
(erwarte nicht, dass ich das verstehe)
Du benutzt einen der nicht deterministischen primzahltests, zum Beispiel Miller Rabin, solovay strassen etc. Wenn der Algorithmus NICHT PRIM liefert, dann ist die Zahl sicher zusammengesetzt. Liefert der Test aber PRIM , dann ist die Zahl nur mit einer bestimmten Wahrscheinlichkeit prim.
Bei folgender Zahl kann man auf den ersten Blick sehen, dass esKEINE Primzahl ist:
8347258347589023456476575892769565672897928567892753478568237562378567865782364578634786578
Wieso?
Weil eine Primzahl immer auf eine der folgenden Zahlen endet:
* 1 (ACHTUNG: Die Zahl "1" alleine ist per Definition keine Primzahl)
* 3
* 7
* 9
Als nächstes kannst du auf die letzten beiden Zahlen achten. Wennsich die letzten beiden Zahlen teilen lassen, zum Beispiel bei 61237827 (nämlich durch 3 und 9), dannentferne diese beiden Zahlen. Übrig bleibt 612378. Letzte Zahl ist gerade und somit ist 61237827 und 612378 beides KEINEPrimzahl.
Das Spielchen lässt sich beliebig oft wiederholen.
Beispiel: 5236633321
Die 21 ist teilbar durch 3 und 7. Also weg damit. Übrig bleibt 52366333. Die 33 ist teilbar durch 3 und 11. Also auch weg damit. Übrigbleibt 523663. Als nächstes bemerkstdu, dass die 63 auch teilbar ist durch mehrere Zahlen und entfernst sie auch.
Übrig bleibt 5236 – KEINE Primzahl da gerade.
Ich hoffe, ich konnte helfen.
So leicht funktioniert das (leider) nicht.
ist 1427 prim?
die letzten beiden Ziffern, 27 sind, wie bei dir, als Zahl zusammengesetzt durch 3 und 9 ( und 1 und 27) teilbar.
Außerdem ist 14 gerade.
1427 ist trotzdem eine Primzahl.
Der einzig 100%ige Beweis ist, die beiden nicht primitiven Teiler anzugeben, die deine Nicht Primzahl teilen.
Mit einem Faktorisierungsverfahren.
Im einfachsten Fall per Probedivision. Fortgeschrittener sind etwa die Pollard-Rho-Methode oder das Zahlkörpersieb (number field sieve).
Wenn der Test aber NICHT PRIM liefert, dann ist die Zahl sicher zusammengesetzt.