fermatscher primzahltest
-
Hallo,
ich hae mir gerade den http://de.wikipedia.org/wiki/Fermatscher_Primzahltest artikel zum fermatschen primzahltest durchgelesen, und habe eine frage zum determistischen verfahren. in dem artikel wird geschrieben, dass man bis zur 341 nur zur basis 2 testen muss, bis zur 1104 die basen 2 und 3 usw.
jetzt habe ich mich gefragt, wie man darauf kommt, dass man nur diese basen testen muss und wie man diese herausbekommt?mfg
vario-500
-
Wie man da drauf kommt, steht im Abschnitt da drüber erklärt. Und so wie ich das verstehe ist das Ergebnis durch Ausprobieren entstanden.
-
hmm ok danke, ich dachte es gibt da noch irgendein anderen weg, der dort nicht beschrieben ist.
-
Es ist ausprobieren. Halt mit dem Vorteil, daß nur einer mit einem Großrechner mal durchtestet und ab dann alle einen schnellen(!) Primzahlentest haben, soweit der eine vorher getestet hat.
SPRP ist nich netter als nur PRP. Und gar nicht spürbar teurer. Oder gar billiger? Weiß jetzt nicht, aber viel wirksamer.
Das ist die klassische Seite dazu:
http://primes.utm.edu/glossary/xpage/StrongPRP.htmlManchmal reicht auich eine Grafikkarte:
http://www.groupsrv.com/science/about456371.html
(Und dort sie Links, oder google(fast primetest sprp cuda)Außerdem sehenswert ist das hashen hier:
http://www.mersenneforum.org/showthread.php?t=12209Und man kann riskieren, an die GRH zu glauben und für noch nicht ausgelotete Zahlenbereiche das hier nehmen:
http://en.wikipedia.org/wiki/Miller–Rabin_primality_test#Deterministic_variants_of_the_testEine SPRP(2)-Liste bis AFAIR 10^15 steht auch im Netz.
-
danke erstmal für die links
das im ersten beschriebene mit dem sprp ist doch nur der miller-rabin-test, oder?
hier stellt sich wieder die frage bei mir, wie man dann auf die nummern kommt, die das ganze determistisch zu machen. ich denke mal ausprobieren, aber ich kann mir gerade nicht so genau vorstellen, wie man das macht. ich würde jetzt mal tippen, dass man erstmal jede zahl mit der basis 2 mit dem miller-rabin-test durchprobiert, und wenn dann auf ne pseudoprimzahl trifft, probiert man das ganze mit der basis 3, vorausgesetzt man hat alle primzahlen schon gegeben mit den man vergleichen kann. jedoch kann ich mir dann nicht erklären, wie man auf die basen 2,3 und 61 zum beispiel kommt.
-
vario-500 schrieb:
danke erstmal für die links
das im ersten beschriebene mit dem sprp ist doch nur der miller-rabin-test, oder?miller-rabin benutzt den SPRP-Test.
hier stellt sich wieder die frage bei mir, wie man dann auf die nummern kommt, die das ganze determistisch zu machen. ich denke mal ausprobieren, aber ich kann mir gerade nicht so genau vorstellen, wie man das macht.
Einfach die SPRPs zur Basis 2 ausrechnen und abspeichern. Und zur Basis 3 und so noch ein paar. Dann die Listen vergleichen, welche die erste Zahl ist, die in allen Listen vorkommt.
ich würde jetzt mal tippen, dass man erstmal jede zahl mit der basis 2 mit dem miller-rabin-test durchprobiert, und wenn dann auf ne pseudoprimzahl trifft, probiert man das ganze mit der basis 3, vorausgesetzt man hat alle primzahlen schon gegeben mit den man vergleichen kann.
Ja.
jedoch kann ich mir dann nicht erklären, wie man auf die basen 2,3 und 61 zum beispiel kommt.
Ausprobieren, ja, es kostet viel Rechenzeit.
