Factor a polynomial over a finite field or the integers

Question

Without using any built-in factoring/polynomial functions, factor a polynomial completely into irreducibles over the integers or a finite field.

Input

Your program/function will receive some prime (or zero) number n as input. The field/ring is the finite field of that order (ie Z/nZ), or just Z if n is 0. Your program may fail if n is not 0 or a prime. The polynomial will be in F[x].

Your program/function will also receive the polynomial as input.

There is some flexibility in the input, be sure to specify how you intend to receive input. For example, the polynomial could be input as a list of coefficients, or in the form most people expect (ex:50x^3 + x^2), or some other reasonable form. Or the format of inputting the field/ring could also be different.

Output

Your program/function will output the polynomial factored completely. You may leave multiple roots expanded (ie (x + 1)(x + 1) instead of (x + 1)^2). You may remove whitespace between binary operators. You may replace juxtaposition with *. You may insert whitespace in weird places. You may reorder the factors into whatever order you want. The x term could just be (x). x can be written as x^1; however the constant term may not have x^0. Extraneous + signs are allowable. You may not have a term with a 0 in front, they must be left out. The leading term of each factor must be positive, negative signs must be outside.

Test cases, your program should be able to produce output for each of these in reasonable time (say, <= 2 hours):

Input: 2, x^3 + x^2 + x + 1

Output: (x + 1)^3

Input: 0, x^3 + x^2 + x + 1

Output: (x + 1)(x^2 + 1)

Input: 0, 6x^4 – 11x^3 + 8x^2 – 33x – 30

Output: (3x + 2)(2x - 5)(x^2 + 3)

Input: 5, x^4 + 4x^3 + 4x^2 + x

Output: x(x + 4)(x + 4)(x + 1)

Input: 0, x^5 + 5x^3 + x^2 + 4x + 1

Output: (x^3 + 4x + 1)(x^2 + 1)

_{Special thanks to Peter Taylor for critiquing my test cases}

Answer 1

GolfScript (222 bytes)

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

Online demo

Notes

1. 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].
2. 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.
3. 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.
4. 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.