Wann ist JAVAs BigInteger.nextProbablePrime() keine echte Primzahl?

Question

Die unter http://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html beschriebene Funktion liefert nach Angabe einer Startzahl die nächste Primzahl.

Das geht jedoch selbst bei 10000 stelligen Zahlen so schnell, dass das Ergebnis nicht immer 100% richtig sein kann.

Das Beschreibt auch die Doku mit Fehler bei 2^{-100} = 7.8..e-31.

Mich interessieren nun die 0,00000...000078%, wo was falsch sein soll!

3^20957+2972344 scheint ein solcher Fall zu sein.

(10000 Stellen!)

Ich suche aber kleinere Zahlen... habe auch schon ein Suchprogramm laufen.

Möchte sich jemand an der Suche beteiligen?

Comments

Gerade hat https://www.alpertron.com.ar/ECM.HTM

3^20957+2972344

mit einem NICHT-PRP-Test als Primzahl bestätigt.

Damit war mein Bauchgefühl falsch.

Vermutlich müssen es noch mehr stellen sein...

Answer 1

Es gibt mehrere probabilistische Primzahltests. Welche zusammengesetzten Zahlen faelschlicherweise als prim deklariert werden, haengt nicht nur von der Zahl, sondern auch von der Methode ab. Und natuerlich auch davon, ob der Test mit Zufallszahlen arbeitet oder nicht.

Die Wahrscheinlichkeit, dass eine Nichtprimzahl als Primzahl verkauft wird, ist kleiner als zweimal hintereinander ein Sechser im Lotto.

Wie bist Du auf 3²⁰⁹⁵⁷+2972344 gekommen und warum ist das keine Primzahl?

Comments

Mehrere Tests zeigen, dass 3^20957+2972344

"Probably prime" ist. Also mit sehr hoher Wahrscheinlichkeit eine Primzahl.

Kein mir bekannter "strenger Test" ist bei Ihr bis heute fertig geworden.

In diesem Bereich (oberhalb 8000 Stellen) könnten erste Fehler (z.B. RSA Zahl aus 2 Faktoren) auftreten.

(drauf gekommen: reines "Bauchgefühl")