Frage von elenano, 548

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

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von NoHumanBeing, 471

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.)

Kommentar von lks72 ,

Wenn der Test aber NICHT PRIM liefert, dann ist die Zahl sicher zusammengesetzt.

Kommentar von NoHumanBeing ,

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).

Kommentar von elenano ,

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.

Kommentar von NoHumanBeing ,

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.

Antwort
von lks72, 369

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.

Antwort
von Roderic, 330

Der einzig 100%ige Beweis ist, die beiden nicht primitiven Teiler anzugeben, die deine Nicht Primzahl teilen.

Kommentar von elenano ,

Ja, aber wie kann man diese herausfinden?

Kommentar von NoHumanBeing ,

Mit einem Faktorisierungsverfahren.

Im einfachsten Fall per Probedivision. Fortgeschrittener sind etwa die Pollard-Rho-Methode oder das Zahlkörpersieb (number field sieve).

Antwort
von 55555555555555, 48

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.

Kommentar von YStoll ,

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.

Antwort
von Delveng, 270

Eine Zahl ist ein Primzahl, wenn sich diese Zahl nur durch sich selbst und durch die Zahl 1 teilbar ist.

Trifft das nicht zu, dann ist die fragliche Zahl keine Primzahl.

Kommentar von elenano ,

Das hilft mir jetzt nicht wirklich weiter. Das war mir ja bereits bekannt. Ich wollte wissen, ob es Methoden gibt, zu beweisen, dass die Zahl durch etwas anderes als 1 und sich selbst teilbar ist.

Kommentar von 55555555555555 ,

Du hast vergessen zu erwähnen, dass 1 KEINE Primzahl ist.

Antwort
von gustav2724, 303

Ich weiß ni wie mans beweisen kann, aber hier http://de.numberempire.com kannst du deine Zahl eingeben und sehen, ob es eine Primzahl ist.

Antwort
von pbheu, 240

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...

Kommentar von pbheu ,

ach, vergessen, guckst du hier:

https://de.wikipedia.org/wiki/Primzahltest

(erwarte nicht, dass ich das verstehe)

Keine passende Antwort gefunden?

Fragen Sie die Community