Primzahlentest bis unendlich Stellen

Question

Ich wollte mal fragen, ob es online einen Primzahlentester gibt, der mir Primzahlen bis unendlich Stellen prüft, er sollte schon schnell sein.

Das auch ein Computer bei 1000 Stellen einige Minuten bis Stunden braucht ist mir klar, aber ich möchte nicht, dass der Tester für 20 Stellen jetzt eine Viertelstunde braucht.

Kann mir bitte wer einen Link unten antworten, das würde mir sehr weiterhelfen.

LG Lampenschirm

Answer 1

Auf Primalität testet man besonders gerne Zahlen mit einer besonderen Struktur. (z.B. 2^p-1 mit einer Primzahl p). Dann gibt es manchmal Verfahren (z.B. von Lucas), die es erlauben die Primalität in vertretbarer Zeit zu  bestätigen oder zu widerlegen. Allgemein aber kann die Zerlegung sehr großer Zahlen auch nach vielen Stunden, Tagen oder sogar Jahren nicht von modernen Großrechenanlage geleistet werden. Genau darauf beruhen einige Verschlüsselungsverfahren (z.B. RSA-Verschlüsselung).

Comments

Danke für die Recherche, aber kannst du mir trotzdem so etwas empfehlen?

---

Ich weiß nicht, was mit "so etwas" gemeint ist. Empfehlen kann ich eine Beschäftigung mit dem Thema "Elementare Zahlentheorie" z.B. von Padberg. Vielen Dank für die Auszeichnung.

Answer 2

Da diese Frage noch nicht zufriedenstellend beantwortet wurde, möchte ich

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

vorstellen.

Bis etwa 70 Stellen kann jede Zahl relativ schnell untersucht werden.

Oft wird jedoch einfach nur mit dem ECM-Algorithmus gesucht, wo es manchmal schnellere gibt.
Beispiel:

3761844347944019380812448477142805854310131054241322463562897739716154279181742220781

Faktorisierer       | Berechnungszeit
---------------------+--------------------------
Pollard.., Williams, > 1 h (nicht abgewartet!)
Carmich...,              > 1 h (nicht abgewartet!)
Mathematica           > 1 h (nicht abgewartet!)
alpertron.com         18 min 48  s
yafu\siqs 8 Threads         55.7 s
Fermat GMP 1 Thread           1.01s

Noch was zur Stellenanzahl:

Wenn sich eine zu untersuchende Zahl für den Carmichael-Test eignet, sind 9000 Stellen kein Problem!

Wenn es jedoch eine echte RSA-Zahl ist, gibt es bereits 260stellige wie

https://en.wikipedia.org/wiki/RSA_numbers#RSA-260

die bis heute nicht gefunden wurden (also Jahre Suchzeit mit schnellen Computern)!!!

Grüße

Mittlerweile habe ich noch etwa 10 weitere Algorithmen gefunden (oder bekannte programmiert), die alle meist zwischen

diesen beiden Extremen liegen. Ich starte einfach alle 16 parallel und beobachte, welcher am schnellsten antwortet

(aber lokal, also nicht online)