Needs["Algebra`PolynomialPowerMod`"]

Clear[Faktoren]
Faktoren[a_, x_, p_, s_] := 
      Module[{tab, k, bliste, restliste, pos}, 
tab = 
          Table[k, {k, 0, p - 1}]; 
bliste = 
          tab; 
Do[
bliste = 
            Flatten[Outer[Plus, bliste, tab*x^k]], {k, 
            s}]; 
bliste = 
          Complement[bliste, {0}]; 
restliste = 
          Map[PolynomialRemainder[a, #, x, Modulus -> p] &, 
            bliste]; 
pos = 
          Position[restliste, 0]; 
Table[
          bliste[[pos[[k, 1]]]], {k, 1, 
            Length[pos]}]
]

Faktoren[(x^4) + x + 1, x, 2, 2]

Factor[(x^4) + x + 1]