Factor a polynomial over a finite field or the integers

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

• I think this is giving me a flashback to some of the harder undergraduate maths. Am I even heading in the right direction here? – Digital Trauma Oct 4 '14 at 16:40
• This reminds me of the time I had nightmares trying to print polynomials correctly... – Sp3000 Oct 17 '14 at 7:57
• Sorry that I did not understand, but what is the first input number supposed to do ? or how does it affects the output ? – Optimizer Oct 27 '14 at 7:27
• @Optimizer The first input number determines what field/the integers you are working over. If the number is nonzero, you are working over the finite field of that order. A finite field of order p has the elements {0, 1, ... , p-1} and it is under addition/multiplication mod p. Basically, reduce any coefficient by mod p and you're good. Also, note that if it has a root, ie linear factor, one of {0, ... , p-1} will produce 0 (mod p) when it is plugged into the polynomial. – Justin Oct 27 '14 at 7:31
• @flawr, the standard approach to factoring over Z is to factor over Z/pZ for a suitable p and then Hensel lift. However, the golfable approach is probably (and this is certainly the route I'm looking at) to use a simple bound on the height of the factors and brute force it. – Peter Taylor Oct 27 '14 at 16:29

~.@: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;][]-{'('\.,:x;{.`'+'\+'x^'x(:x+x!!*+\!!*}%')'}/