20
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ I think this is giving me a flashback to some of the harder undergraduate maths. Am I even heading in the right direction here? \$\endgroup\$ – Digital Trauma Oct 4 '14 at 16:40
  • 1
    \$\begingroup\$ This reminds me of the time I had nightmares trying to print polynomials correctly... \$\endgroup\$ – Sp3000 Oct 17 '14 at 7:57
  • \$\begingroup\$ Sorry that I did not understand, but what is the first input number supposed to do ? or how does it affects the output ? \$\endgroup\$ – Optimizer Oct 27 '14 at 7:27
  • \$\begingroup\$ @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. \$\endgroup\$ – Justin Oct 27 '14 at 7:31
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Peter Taylor Oct 27 '14 at 16:29
17
+200
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.