Care should be taken with
finite fields, as factoring a
polynomial means finding factors like (x-a) and factors like (x^2+1) over Z_3.
I mean that if you check that a polynomial doesn't evaluate as 0 on any x, it doesn't mean it hasn't got any factors.