Nun, es fehlen mal wieder jegliche Hinweise und Kommentare, was was ist. Liefert witness true wenn a ein Zeuge für die Nichtprimalität von n ist (das wäre die Standarddefinition)? Gleiche Frage für millerrabin.
Auf jeden Fall ist die Schleife
Delphi-Quellcode:
for i:=1 to s-1 do begin
a:=mathe.Zufall(mathe,'0',mathe.Differenz(n,'1'));
if witness(a,n)=false then begin
result:=false;
exit;
end
else begin
result:=true;
exit;
end;
end;
Blödsinn da sie nach dem ersten witness immer verlassen wird. (Bem: Deine boolean-Konstruktionen und Einrückungen sind auch nicht besonders übersichtlich)
Delphi-Quellcode:
result := witness(a,n);
exit;
tut genau das gleiche.
Soviel zur falschen Logik. Ein weiterer Hinweis: Normalerweise würde ich am Ende von witness erwarten, daß x mit n-1 vergleichen wird und nicht x mit 1. Also etwa:
if f<>mathe.Differenz(n,'1')) then result := (nicht prim).
Wobei für (nicht prim) steht für Deine Wahl was witness eigentlich zurückliefert.
Gammatester
PS: Quadrieren sollte man auch statt mit
x :=mathe.PotenzModulo(f,'2',n);
besser und schneller mit
x := ProduktModulo(f, f, n);