BiggestExp := function(m,b)

   local exp;
    
      exp := 0;
      while IsInt((m/b^exp)) do
         exp := exp+1;
      od;
      return(exp-1);

end;    



IstZeuge := function(n,a)

   local L,d,z,Exp,xx,m;
 
       xx := BiggestExp(n-1,2);
       d := (n-1)/(2^xx); 
       z := [2,xx]; 
       Exp := [1..z[2]];
       return( (IntGcd(a,n)<>1) or ( not(IntPowerMod(a,d,n)=1) and not(ForAny([0..Length(Exp)-1], i-> IntPowerMod(a,d*2^i,n)=n-1))) );
end;



MillerRabin := function(n,anz)

    local Ze,ZListe,xx,b,T;

       if n=2 then
          return(false);
       fi;
       xx     := 1; Ze := 1;
       repeat
          b  := IstZeuge(n,Ze);
          repeat
             Ze := NextPrime(Ze) mod n;
          until (Ze <>0);
          xx := xx+1;
       until (xx=anz or b=true);

       ##b=true ---> n war NICHT prim, da das Ereignis, ein Zeuge gefunden zu haben, wahr ist(=TRUE)

       if b=true then
          Print("nicht prim \n");
       else
          Print("prim \n");
       fi;
    
       return(b);
      
  
end;