--
-- Test pierwszosci - test Fermata
--
-- www.algorytm.org
-- (c)2007 Tomasz Lubinski
--

with Text_IO;
use Text_IO;

with Interfaces;
use Interfaces;

with Ada.Numerics.Discrete_Random;

procedure Fermat is
	
   -- calculates a^b mod n
   function power_modulo_fast(a: Integer; b: Unsigned_32; m: Integer) return Integer is
      i: Unsigned_32;
      result: Integer := 1;
	 x: Integer := a mod m;
   begin
      i := 1;
      while i<=b loop
         x := x mod m;
         if (b and i) /= 0 then
            result := result * x;
            result := result mod m;
         end if;
         x := x*x;
         i := i * 2;
      end loop;
      return (result mod m);
   end;
   
   -- Fermat test
   -- retrun: true - probably prime
   --         false - not prime
   function FermatTest(n: Positive; k: Positive) return Boolean is
      subtype Rand_Range is Positive range 2 .. n-1;
      package Random_Gen is new Ada.Numerics.Discrete_Random (Rand_Range);
      use Random_Gen;
      a: Positive;
      g : Generator;
   begin
   
      if n<4 then
         return TRUE;
      end if;

      Reset(g);
      for i in 1 .. k loop
         a := Random(g);
         if power_modulo_fast(a, Unsigned_32(n-1), n) /= 1 then
            return FALSE;
         end if;
      end loop;
      
      return TRUE;
   end;


begin

   -- check 13
   if FermatTest(13, 3) then
      Put_Line("13 jest pradopodobnie liczba pierwsza");
   else
      Put_Line("13 nie jest liczba pierwsza");
   end if;

   -- check 27
   if FermatTest(27, 3) then
      Put_Line("27 jest pradopodobnie liczba pierwsza");
   else
      Put_Line("27 nie jest liczba pierwsza");
   end if;

end;