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

program Fermat;
{$APPTYPE CONSOLE}
uses
  SysUtils;

var
   n, k: Integer;

// 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;

   result := result mod m;
end;

//Fermat test
//retrun: true - probably prime
//        false - not prime
function FermatTest(n: Integer; k: Integer): Boolean;
var
   a, i: Integer;
begin

   Randomize;

   if (n<4) then
   begin
      result := true;
      exit;
   end;

   for i:=1 to k do
   begin
      a := Random(n-2)+2;
      if power_modulo_fast(a, n-1, n) <> 1 then
      begin
         result := false;
         exit;
      end;
   end;

   result := true;
end;

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

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

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

   readln;

end.