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

[Der_Unwissende]

Ok, ich muss sagen ich seh auch keinen Fehler.
Bei welcher Zahl klappt es denn immer nicht?

Kann mir nur vorstellen, das die Rundung beim Finden des Zeugen irgendeinen Nebeneffekt hat (geliebte Floating Points).
Aber du kannst den Algorithmus etwas umschreiben :

Delphi-Quellcode:

  t := 0; 
  u := n-1; 

  while ((u mod 2) = 0) do 
    begin 
      u := u shr 1; 
      Inc(t); 
    end;

Sollte zwar nicht wirklich etwas verändern, aber gut. Hatte erst überlegt, dass du so natürlich das Aufrunden verlieren würdest, aber ich bin mir halt nicht sicher, ob da schon ein Fehler drin steckt.

Die Idee ist es doch, dass n-1 eine gerade Zahl ist. t >= 1, damit 2^{t} >= 2 und damit wiederum bin(n-1) = bin(u) shl t, mit bin (x) = Binärdarstellung von x. Also musst du nur die Binärdarstellung von (n-1) nehmen und die 0en bis zur ersten eins zählen. Und eigentlich würde ich sagen machst du genau das (und dir war sicherlich auch die Idee klar, wollte es nur sagen um meinen Gedankengang nachvollziehbarer zu machen).
Wenn ich immer um eine Stelle nach Rechts verschiebe, hm, runde ich doch immer ab? Bei Round hingegen würde ich teilweise auch abrunden. Allerdings dürfte es (da nur solange geshiftet wird, wie die letzte Stelle 0 ist) gar keine Rundung geben. Also ist es nur aus Performancegründen sinnvoll zu shiften (anders gesagt es ist völlig für den A...).

Hm, ne, dann seh ich den Fehler erst recht nicht. Keine Ahnung warum es nicht macht was es soll. Vielleicht doch jmd. anderes?

Gruß Der Unwissende