//
// Test pierwszości - test Millera-Rabina
//
// www.algorytm.org
// (c)2007 Tomasz Lubinski
//

program Miller_Rabin;
{$APPTYPE CONSOLE}
uses
  SysUtils;

var
   n, k: Integer;

powerOf2 : array [0..30] of Integer =
   ( 1,  2,  4,  8,  16,  32,  64,
     128,  256,  512,  1024, 2048, 4096, 8192,
     16384, 32768, 65536, 131072, 262144, 524288, 1048576,
     2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728,
     268435456, 536870912, 1073741824 );

// calculates a^b mod m
function power_modulo_fast(a: Integer; b: Integer; m: Integer): Integer;
var
   i: Integer;
   x: Int64;
begin
   result := 1;
   x := a mod m;

   i := 1;
   while (i<=b) do
      begin
         x := x mod m;
         if ((b and i) <> 0) then
            begin
               result := (result * x) mod m;
            end;
         x := x * x;
         i := i shl 1;
      end;
end;

//Miller-Rabin test
//retrun: true - probably prime
//        false - not prime
function MillerRabinTest(n: Integer; k: Integer): Boolean;
var
   s, s2, a, d, i, r: Integer;
   prime: Boolean;
begin

   if (n<4) then
   begin
      Result := true;
      exit;
   end;
   if (n mod 2) = 0 then
   begin
      Result := false;
      exit;
   end;

   s := 0;
   s2 := 1;

   // calculate s and d
   while ((s2 and (n-1)) = 0) do
   begin
      s  := s + 1;
      s2 := s2 * 2;
   end;
   d := n div s2;

   // try k times
   randomize();
   for i:=1 to k do
   begin
      a := Random(n-2)+2;
      if power_modulo_fast(a, d, n) <> 1 then
      begin
         prime := false;
         for r:=0 to s-1 do
         begin
            if power_modulo_fast(a, powerOf2[r]*d, n) = n - 1 then
            begin
               prime := true;
               break;
            end;
         end;
         if prime = false then
         begin
            Result := false;
            exit;
         end;
      end;
   end;

   Result := true;
end;

begin
   writeln('Podaj liczbe do sprawdzenia.');
   readln(n);

   writeln('Podaj dokladnosc sprawdzenia.');
   readln(k);

   if MillerRabinTest(n, k) then
      writeln('Liczba jest prawdopodobnie pierwsza.')
   else
      writeln('Liczba jest zlozona.');

   readln;

end.