Without using any built-in factoring/polynomial functions, factor a polynomial completely into irreducibles over the integers or a finite field.
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
0. Your program may fail if
n is not
0 or a prime. The polynomial will be in
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.
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 can be written as
x^1; however the constant term may not have
+ 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):
2, x^3 + x^2 + x + 1
(x + 1)^3
0, x^3 + x^2 + x + 1
(x + 1)(x^2 + 1)
0, 6x^4 – 11x^3 + 8x^2 – 33x – 30
(3x + 2)(2x - 5)(x^2 + 3)
5, x^4 + 4x^3 + 4x^2 + x
x(x + 4)(x + 4)(x + 1)
0, x^5 + 5x^3 + x^2 + 4x + 1
(x^3 + 4x + 1)(x^2 + 1)
Special thanks to Peter Taylor for critiquing my test cases