Miller-Rabin - Eigene Impl. findet nicht jede Primzahl...

[Der_Unwissende]

Hi,
ich hab mir deinen Code + Pseudocode noch nicht angeschaut, aber mal als Mögliche Antwort vorweg (hoffe ich verwechsel hier nicht Miller-Rabin mit einem ganz anderen), es handelt sich um einen Pseudoprimzahltest. Du versuchst doch (und jetzt weißt du gleich ob ich mich irre) Zeugen für die Zerlegbarkeit (in Primfaktoren) deiner zu testenden Zahl zu finden. Hm, Basis wird zufällig gewählt und dann, weiß ich gar nicht mehr

Jedenfalls gibt es eine Fehlerrate, die von dieser Zufälligkeit (der Basis) abhängt oder anders gesagt, die Ermittlung deiner Zeugen (wie auch immer das da war), ist hier der einzigste Kritische Punkt. Der Algorithmus ist so gut, weil er recht schnell approximiert (aber eben nicht mehr). Du wirst also Fehler haben, aber die Wahrscheinlichkeit ist sehr sehr gering.

Da bei dir aber trotzdem welche auftreten (genug um bemerkt zu werden), schau ich gleich mal.
Falls ich von einem falschen Algo rede, sorry, dann vergiß alles was ich gesagt habe.

Gruß Der Unwissende