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;

[negaH]

Zitat:

Nur waren danach alle anderen Zahlen zusammengesetzt. Wie kann das sein? Hängt der Fehler wirklich an der Größe der Variabeln?

x := (d * d) mod n

wenn D vom Typ Cardinal ist wie groß darf er maximal sein damit das Resultat von D * D noch in einen Cardinal reinpasst ?

Am besten mal mit D = 2,4,8,16,32,64 usw. testen, sprich also mit D = 2^i wenn i von 0 bis 31 geht.

Oder andersrum

Wenn a = b^2 dann ist b = a^0.5 = Sqrt(a).

Ergo was ergibt Sqrt(MaxInt) und was ergibt Sqrt(MaxCardinal).

D darf also niemals größer als Sqrt(2^32) = 2^16 sein. Wenn aber nun D modular N genommen wird kann D nur dann größer als 2^16 werden wenn N ebenfalls größer 2^16 ist. Ergo: mit deiner Implementation kannst du nur bis 2^16 ordentlich arbeiten.

Ich hatte es Klaus schon per PN mitgeteilt, schau mal hier rein

http://www.delphipraxis.net/internal...prime&start=20
http://dennishomepage.gugs-cats.dk/IsPrimeChallenge.htm
http://primes.utm.edu/prove/prove2_3.html


Gruß Hagen