How to factor polynomials? I am wondering if there is a methodical, algorithmic, brain-dead way to factor polynomials. For example:
$x^6 - 14x^{5} + 73x^{4} - 188x^{3} + 256x^{2} - 176x^{1} + 48$
can be written as
$(x-1)^2 (x-2)^3 (x-6)$
But how do you actually get there?
 A: If you will accept a "brain-dead" method, why not just appeal to computer algebra, such as Mathematica?
Factor[x^6 - 14 x^5 + 73 x^4 - 188 x^3 + 256 x^2 - 176 x^1 + 48]

$(x-6) (x-2)^3 (x-1)^2$
or
Factor[-20284203008 + 12410729472 x + 2524112000 x^2 - 
  1341562640 x^3 - 334176180 x^4 + 12601652 x^5 + 12198347 x^6 + 
  1767405 x^7 + 127690 x^8 + 5150 x^9 + 111 x^10 + x^11]

$(x-4) (x-2)^2 (x+8)^3 (x+19)^5$
A: The problem of factoring polynomials is in general difficult and/or labor-intensive, but for the sake of concreteness, I'll indicate one way to factor the example polynomial that uses a few methods (caution: these methods do not apply to all polynomials!).
The Rational Root Theorem says that any (reduced form) rational root $\frac{s}{t}$ of a polynomial $$p(x) := a_n x^n + \cdots + a_1 x + a_0$$ satisfies $s \mid a_0$ and $t \mid a_n$. In particular, if the polynomial is monic (i.e., $a_n = 1$) any rational root is in fact an integer, and all such roots are factors of $a_0$. In our case, the possible integer roots of
$$q(x) := x^6 - 14x^{5} + 73x^{4} - 188x^{3} + 256x^{2} - 176x + 48$$
are just the factors of $48$.
There are, unfortunately, 20 of these (counting sign), but we can simplify our search considerably by observing that the signs of the coefficients of $q(x)$ alternate with degree, and hence the signs of $q(-x)$ are all the same (in this case positive). So, $q(-0) > 0$ and $q(-x)$ is increasing on $[0, \infty)$; hence all of the roots of $q(-x)$ are negative, or equivalently, all of the roots of $q(x)$ (rational or otherwise) are positive, reducing the list of integers to check by one-half.
If we start with the largest factors of $a_0 = 48$ and work down, we find that the largest root of $q$ is $6$, and so $(x - 6)$ is a factor of $q(x)$. Polynomial long division gives that
$$q(x) = (x - 6) r(x) ,$$ where $$r(x) := x^5-8 x^4+25 x^3-38 x^2+28 x-8,$$
and we can see that by starting with the largest factors of $a_0$ we produce the smallest constant terms after polynomial long division, reducing more the list of possibilities to check at the next step. Indeed, $8$ only has four positive factors to check. (Of course, if you're checking this without calculator assistance, it is generally more computationally intensive to evaluate $p(x)$ for integers $x$ large in magnitude than ones small in magnitude, in which case working from largest to smallest need not be optimal.)
Checking shows that $r(8), r(4) \neq 0$, and so any integer roots of $r$ are $1$, $2$. On the other hand, for any polynomial $p$, the product of the roots (counting multiplicity) is $(-1)^{\deg p} a_0$. So if we know in advance that all of the roots of $q$ are integers, so are all the roots $b_j$ of $r$, and if the multiplicity of $2$ as a root of $r$ is $k$, the multiplicity of $1$ is $5 - k$, and by the above we have that $-(-8) = 1^{5 - k} 2^k = 2^k$. Thus, $k = 3$, and so we conclude that
$$q(x) = (x - 6) (x - 2)^3 (x - 1)^2 $$
as desired. Note that this method only required evaluating a polynomial $8$ times and a carrying out a single polynomial long division (and again, knowing in advance that all of the roots of $p$ were integers).
Caution Several of the techniques here can only be applied when the given polynomial has certain properties. Most importantly, (1) not all roots of a real polynomial need be rational (indeed, none need be, as is the case for $x^2 - 2$), and (2) not all roots of a real polynomial need even be real (as in the case of $x^2 + 1$), and correspondingly, a polynomial need not be factorable over $\Bbb R$. In general, factoring a polynomial over $\Bbb Q$ or $\Bbb R$ is difficult and/or labor-intensive (and in the latter case there's a question of what form one wants). See the Wikipedia article, Factorization of Polynomials, for more information.
A: Since in your comments you mention that you would like to apply polynomial factorization to the study of linear recurrences, I assume that you are looking for a general algorithm to factor a polynomial over $\Bbb{C}$ (cfr. this). You can always factor over $\Bbb{Z}$ a reducible polynomial with integer coefficients, but there isn't any general way to find the complex roots of an irreducible polynomial in $\Bbb{Z}[X]$, let alone a "brain-dead" one. Thus I'm going to propose a simple algorithm to obtain a partial factorization.
First, recall that every polynomial with complex coefficients factors completely over $\Bbb{C}$ as a product of polynomials of degree $1$, and that $r$ is a root of a polynomial $f(X)$ if and only if $X-r \mid f(X)$. This means that the problem of factoring a polynomial over $\Bbb{C}$ is equivalent to finding its (complex) roots. So here's what you can always do, given a polynomial $f(X) \in \Bbb{C}[X]$:


*

*Define empty lists $\Lambda$ and $\Lambda'$.

*If $f(X)$ has integer coefficients, compute any rational roots (e.g. with a greedy algorithm based on the rational root theorem, see Travis's answer).


*

*Add them to $\Lambda$.

*Continue with $f'(X) = f(X) / \prod_{\lambda \in \Lambda} (X - \lambda)$.


*If $\deg f' = 0$ jump to the last step.

*If $\deg f' \leq 4$ compute its roots using the appropriate formula by radicals.


*

*Add them to $\Lambda$.

*Set $f'(X) = 1$ and jump to the last step.


*Optional: Use your favourite numerical method(s) to approximate the roots of $f'(X)$.


*

*Add them to $\Lambda'$.


*Output $f'(X) \prod_{\lambda \in \Lambda} (X - \lambda)$ and $\Lambda'$.


Note 1: There are some sophisticated algorithms to factor a polynomial over the integers which you could use instead of point 2. Then you'd have to repeat points 3 to 5 for every non-linear factor you find.
Note 2: If you're bent to venture outside the algebraic realm, you can add a step 4' to look for an analytic closed-form expression of the roots of quintic and sextic polynomials.
Note 3: In some cases it may be possible to determine algorithmically if the Galois group of (the splitting field of) $f'$ is solvable and, if it is, find the roots of $f'$ by radicals. This was done for sextic polynomials, but I'm not aware of more general results.

As far as I know, polynomial factorization in Mathematica (and, by extension, in WolframAlpha) revolves around the aptly-named Factor function. This function factors a polynomial over the ring of algebraic integers of a user-specified number field, and it defaults to factoring over $\Bbb{Z}$. You can use it only for step 2 above, like I mentioned in note 1.
You can also use Solve to find the roots of a generic polynomial of degree $\leq 4$ and those of a few polynomials of higher degree, but that's it as far as exact methods go.
For example, WolframAlpha will produce only numerical approximations for the roots of $x^5-4x+2$ and for those of $x^7+x+1$.
