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