Factor a polynomial over a finite field or the integers
GolfScript (222 bytes)

~.@:q@.0\{abs+}/2@,2/)?*or:^{\1$^base{^q- 2/-}%.0=1=1$0=q&gt;+{{:D[1$.,2$,-)0:e;{.0=0D=%e|:e;(D(@\/:x@@[{x*~)}%\]zip{{+}*q!!{q%}*}%}*e+])0-{;0}{@;@\D.}if}do}*;\).^3$,)2/?&lt;}do;][[1]]-{'('\.,:x;{.`'+'\+'x^'x(:x+x!!*+\!!*}%')'}/


Online demo

Notes


The input format is n followed by a GolfScript array of coefficients from most to least significant. E.g. 0, x^5 + 5x^3 + x^2 + 4x + 1 should be formatted as 0 [1 0 5 1 4 1].
Over a finite field, there are only finitely many polynomials of sufficiently small degree to be relevant. However, this is not the case over Z. I handle Z by using a relaxed form of Mignotte's height bound. A great paper on height bounds in factoring is Bounds on Factors in Z[x], John Abbott, 2009 (link is to arxiv preprint; his CV says that it has been accepted by the Journal of Symbolic Computation). The most relaxed form given there is in terms of the L-2 norm, but to save bytes I relax further and use the L-1 norm instead. Then it's a case of brute forcing by trial division.
Over a finite field, every polynomial is a constant times a monic polynomial, so I only do trial division by monic polynomials and save a reciprocal in the field. However, Z is only a ring and so it's necessary to do trial division by non-monic candidate factors. I manage to get away with not implementing rational numbers by doing a leading factor division test and accumulating an "error" flag in e.
Both points 2 and 3 imply that the case of factoring over Z is generally slower, and can't be tested with the online demo. However, the slowest of the official test cases takes 10 minutes, which is well within the "reasonable" time limit.