######################## PROBLÈME 2: #########################

#@# 3)

with(numtheory):
PL := proc(N)
  local res, L, p, e, z, A, a, certif;

  if (N < 2) then RETURN(false); fi;
  if (N = 2) then RETURN(true); fi;
  A := rand(2..N-1);  #@# on suppose N > 2
  L := ifactors(N - 1)[2];
  res := NULL;
  for z in L do
    p := z[1]; certif := PL(p);
    for i to 100 do #@# évite une boucle infinie si N non premier
      a := A();
      b := a &^ ((N - 1)/p) mod N;
      if (b <> 1) then
        if (b &^ p mod N <> 1) then RETURN(false); fi;
        break;
      fi;
    od;
    if (i > 100) then RETURN("ECHEC"); fi;
    res := res, [p, a, certif]
  od:
  res;
end: