IsIrreduciblePoly [f_, var_, p_] :=
Module [{n, i, f1,  canStillBeIrreducible,ggt},
   f1 = PolynomialMod [f, p];
   n = Deg [f1, var];
   canStillBeIrreducible = True;
   i = 1;
   While [canStillBeIrreducible && i <= (n/2),
      ggt = PolynomialExtendedGCDP [f1, var^(p^i) - var, var, p] [[1]];
      canStillBeIrreducible = (Deg [ggt, var] == 0);
      i = i+1;
   ];
   canStillBeIrreducible
]; 