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

[St.Pauli]

So, ich habe mir alles nochmal angeschaut - der Code ist genau der gleiche wie der Pseudocode. Ich habe die Funktion Bin mal geändert, ich glaube die erste hatte nicht richtig funktioniert, jedoch brachte auch dies keinen merkbaren Unterschied.

Schließlich habe ich mal die Variabel-Typen von Integer auf LongWord gesetzt und auf einmal zeigte mir der Code alle Primzahlen bis 65.517 korrekt an! Nur waren danach alle anderen Zahlen zusammengesetzt. Wie kann das sein? Hängt der Fehler wirklich an der Größe der Variabeln?



Nochmal der aktuelle Code:

Delphi-Quellcode:

function Bin(n: Integer):string;
begin
  repeat
    Insert(IntToStr(n mod 2), Result, 1);
    n := n shr 1;
  until
    (n = 0);
end;

function modular_exponentiation(a,b,n : Integer) : Integer;
VAR c, d, i : Integer;
    b_bin : string;
begin
    c := 0;
    d := 1;

    b_bin := Bin(b);

    for i := 1 to Length(b_bin) do
      begin
        c := 2*c;
        d := (d*d) mod n;

        IF (b_bin[i] = '1') THEN
          begin
            d := (d*a) mod n;
            Inc(c);
          end;

      end;

    Result := d;
end;

function witness(a, n : Integer) : boolean;
VAR f, x, i, t, u : Integer;
begin
  Result := False;

  // n-1 = 2^t * u

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

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


  x := modular_exponentiation(a, u, n);


  for i := 1 to t do
    begin
      f := x;
      x := (f*f) mod n;

      IF (x = 1) AND (f <> 1) AND (f <> n-1) THEN
        begin
          Result := True;
          exit;
        end;

    end;

  IF NOT Result THEN
    Result := (x <> 1);
end;

function Miller_Rabin(n, s : Integer) : boolean;
VAR i, a : Integer;
begin
  Result := True;

  Randomize;

  for i := 1 to s do
    begin
      a := Random(n-1) + 1;

      IF (witness(a, n)) THEN
        Result := False;

    end;

end;