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