probedivision -abbruch von schleife funktioniert nicht

[qwertz543221]

ich möchte folgende proceudre (probedivision)abrrechen und mit dem restlichen code weitermachen, doch wieso kann ich die schleife nicht beenden, wenn die abbruchbedingung erreicht ist?

Delphi-Quellcode:

function tform1.miller_rabin(n: ansistring; t: longint):boolean;
label l;
var
  n1,n2, y, r, x: string;
  s,j,i: longint;
const 
 primes:array[1..5]of string=('2','3','5','7');//in meinem fall deujtlich größer
   // probedivison 
function  probedivision(n:ansistring):boolean;
var
 I:longint;
begin
i:=1;
result:=true;
while i<=5{9549} do
begin
if mathe.modulo(n,primes[i])='0'
 then  
 begin
 result:=false;
 break;
 end
   else i:=i+1;
end;
end;

begin
result := false;
if Mathe.istGerade(n)
  then exit;

begin
{get n1 = n - 1} 
{get n2 = n - 2}
if probedivision(n)=true
 then
  begin
  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}
  result := true; 
end;
end;
end;

[hoika]

Hallo,


Breakpoint auf
if mathe.modulo(n,primes[i])='0'

und nachsehen, warum nicht 0 rauskommt.


Heiko

[qwertz543221]

passiert ist gar nichts, noch nicht einmal der breakpunkt hat gestoppt.

es muss null, rauskommen, denn die prüfmessage wird angezeigt.(habe ich nach der abfrage eingebaut)

[stahli]

Oha! ... sieht das in Deiner IDE auch so aus?

Rücke mal den Quelltext ordentlich zurecht, dann liest sich das schon mal leichter (und Fehler finden sich wie von selbst ).
Welche Schleife und Bedingung meinst Du genau?

Wenn die Bedingung erfüllt ist, wird der Compiler das auch berücksichtigen.
Also wird "break" mit Sicherheit gar nicht erreicht.

Stahli


[EDIT]
Wenn der Breakpoint nicht erreicht wird, ist sicher schon Mathe.istGerade(n) erfüllt und Exit ausgeführt...
Also Breakpoint auf die erste Zeile der Prozedur und sehen, was passiert.

[qwertz543221]

ich habe den break point auf den funktionskopf der inneren funktion gelegt, abbruch passierte trotzdem keiner - entschuldigt dei formatierung, ich stell es es gleich neu ein.

[DeddyH]

Du sollst den Breakpoint auf

Zitat:

if probedivision(n)=true

setzen und durchsteppen. Und lass mal die Abfrage auf true weg, die ist nicht nur unnötig, sondern kann auch falsche Ergebnisse liefern.

[qwertz543221]

ok habe ich gemacht - es funktioniert soweit. Danke

noch eine weitere frage:
ist es überhaupt günstig, erst probedivision bei der vordefinierten liste zu machen, bevor andere primzahltests angesetzt werden? - wenn nein, was wäre eine effizientere vorgehensweise?

[gammatester]

Zitat von qwertz543221:

ok habe ich gemacht - es funktioniert soweit. Danke

noch eine weitere frage:
ist es überhaupt günstig, erst probedivision bei der vordefinierten liste zu machen, bevor andere primzahltests angesetzt werden? - wenn nein, was wäre eine effizientere vorgehensweise?

Ich konnte mir eigentlich nicht vorstellen, daß man meine Miller-Rabin-Funktion so versauen kann.

Selbstverständlich hat die Probedivision in der Funktion nichts zu suchen, wenn man nicht wieder alle Bedeutungen auf den Kopf stellen will. Wenn Du Deine Funktion IsProbablePrime oder ähnlich genannt hättest, wäre es OK. Im übrigen würde man die Anzahl der Probedivisionen abhängig von Bitlänge von n machen.

Außerdem: Da Du aber, wie üblich offensichtlich völlig ahnungslos, einfach Code zusammenwürfelst, hast Du übersehen, daß Deine Primzahlliste selbstverständlich bei 3 anfangen (bzw die 2 nicht enthalten) sollte, da Du direkt vor der ersten Probedivision durch 2 ausgeschlossen hast, daß n gerade ist. Oder ist Dir nicht klar, daß "n mod 2 = 0" dasselbe bedeutet wie "n ist gerade"?