Miller-Rabin primzahltest

[gammatester]

Also die schnelle direkte Übertragung meiner Routine nach StringMatheLib scheint doch zu funktionieren:

Delphi-Quellcode:

{---------------------------------------------------------------------------}
procedure miller_rabin(n: string; t: longint; var prime: boolean);
  {-Miller-Rabin test of n, security parameter t, from HAC p. 139 Alg.4.24}
var
  n1,n2, y, r, x: string;
  s,j: longint;
Begin

  n := Mathe.Normalisieren(n);
  if (n='2') or (n='3')  or (n='5') then begin
    prime := true;
    exit;
  end;

  prime := false;
  if Mathe.istGerade(n) or (Mathe.Vergleich(n, '6') <= 0) then exit;

  {get n1 = n - 1}
  {get n2 = n - 2}
  n1 := n;
  Mathe.Minus1(n1);
  n2 := n1;
  Mathe.Minus1(n2);

  {calculate r,s with n-1=2^s*r}
  r := n1;
  s := 0;
  while Mathe.istGerade(r) do begin
    r := Mathe.Quotient(r,'2');
    inc(s);
  end;

  while t>0 do begin
    {generate a in the range 2<=a<n-1, calculate y = a^r mod n}
    y := Mathe.Zufallszahl('2', n2);
    y := Mathe.PotenzModulo(y,r,n);
    {if y<>1 and y<>n-1 do}
    if (y<>'1') and (y<>n1) then begin
      j := 1;
      while (j <= s-1) and (y<>n1) do begin
        y := Mathe.ProduktModulo(y,y,n);
        {if y=1 then composite}
        if y='1' then exit;
        inc(j);
      end;
      {if y<>n1 then composite}
      if y<>n1 then exit;
    end;
    dec(t);
  end;
  {probably prime now}
  prime := true;
end;

{---------------------------------------------------------------------------}
procedure TForm1.Button1Click(Sender: TObject);
  {-Testcode für miller_rabin}
var
  prime: boolean;
  n: string;
begin
  n := Mathe.Normalisieren(Edit1.Text);
  Edit1.Text := n;
  miller_rabin(n,3,prime);
  if prime then button1.Caption := 'Prime' else button1.Caption := 'NOT prime'
end;

Ein paar kleine "Einschränkungen", die aber bei StringMatheLib garantiert nicht zum Tragen kommen: der Sicherheitsparameter t ist im Longint-Bereich, außerdem muss s von n-1 = 2^s*r im Longint-Bereich sein.

In der Praxis benutzt man allerdings Miller-Rabin nicht für kleine Zahlen, ohne vorher Probedivisionen mit einigen kleine Primzahlen zu machen, mindestens bis 100 besser zB alle 16Bit-Primzahlen.

Gammatester