Can Fermat's prime test be implemented efficiently? I tried

File: 1487877149754.jpg (38KB, 362x346px) Image search: [Google]

38KB, 362x346px

Can Fermat's prime test be implemented efficiently?
I tried it it, and it only works up to n=13, for n=17 there is an integer overflow.
(pascal code following)

program fermat;

var n : uint64;
var a : uint64;
var prime : boolean = true;

//power of a and b
function pot(a,b:uint64):uint64;
var i,d: uint64;
begin 
  d:=1; 
  for i:=1 to b do d:=d*a;
  writeln(a, ' ', b, ': ', d); //manually check where the overflow occurs
  pot:=d;
end;


begin

  write('Enter a number n: ');
  readln(n);

  a := 1;

  while a <> (n-1) do begin

    a := a+1;
    if (n mod a) = 0 then //if not coprime, it can't be a prime
      begin
        prime := false; 
        break;
      end;
    
    if (pot(a, (n-1)) mod n) <> 1 then //fermat's little theorem
      begin
        prime := false; 
        break;
      end;

  end;
  
  writeln('Prime state of ', n, ':', prime);

end.