[Question]
  [
Given a polynomial, determine whether it's prime.
A polynomial is `ax^n + bx^(n-1) + ... + dx^3 + ex^2 + fx + g`, where each term is a constant number (the coefficient) multiplied by a nonnegative integer power of `x`. The highest power with a nonzero coefficient is called the degree. For this challenge, we only consider polynomials of at least degree 1. That is, each polynomial contains some `x`. Also, we only use polynomials with integer coefficients.
Polynomials can be multiplied. For example, `(x+3)(2x^2-2x+3)` equals `2x^3+4x^2-3x+9`. Thus, `2x^3+4x^2-3x+9` can be factored into `x+3` and `2x^2-2x+3`, so it is composite.
Other polynomials can not be factored. For example, `2x^2-2x+3` is not the product of any two polynomials (ignoring constant polynomials or those with non-integer coefficients). Hence, it is prime (also known as irreducible).
## Rules
* Input and output can be through any standard way.
* Input can be a string like `2x^2-2x+3`, a list of coeffecients like `{2,-2,3}`, or any similar means.
* Output is either a truthy value if it's prime, or a falsey value if it's composite. You must yield the same truthy value for all primes, and the same falsey value for all composite polynomials.
* The input will be of at least degree 1 and at most degree 10.
* You may not use built-in tools for factorization (of integers or expressions) or equation solving.
## Examples
### True - prime
```
x+3
-2x
x^2+x+1
x^3-3x-1
-2x^6-3x^4+2
3x^9-8x^8-3x^7+2x^3-10
```
### False - composite
```
x^2
x^2+2x+1
x^4+2x^3+3x^2+2x+1
-3x^7+5x^6-2x
x^9-8x^8+7x^7+19x^6-10x^5-35x^4-14x^3+36x^2+16x-12
```
  
[Answer]
# Mathematica, 224 bytes
```
f@p_:=(e=p~Exponent~x;r=Range[⌈e/-4⌉,(e+2)/4];e<2||FreeQ[PolynomialRemainder[p,Thread@{r,#}~InterpolatingPolynomial~x,x]&/@Tuples[#~Join~-#&[Join@@Position[#/Range@Abs@#,_Integer]]&/@#]~DeleteCases~{(a_)..},0|{}]&[p/.x->r])
```
---
**Explanation**:
[Kronecker's method](https://en.wikipedia.org/wiki/Factorization_of_polynomials#Classical_methods) is used here. This method generates certain lower degree polynomials and tests whether there exists a factor of the original polynomial.
**Test cases**:
```
f/@{x+3, -2x, x^2+x+1, x^3-3x-1, -2x^6-3x^4+2, 3x^9-8x^8-3x^7+2x^3-10}
(* {True, True, True, True, True, True} *)
f/@{x^2, x^2+2x+1, x^4+2x^3+3x^2+2x+1, -3x^7+5x^6-2x, x^9-8x^8+7x^7+19x^6-10x^5-35x^4-14x^3+36x^2+16x-12}
(* {False, False, False, False, False} *)
```
It takes 14s on my laptop to conclude that `3x^9-8x^8-3x^7+2x^3-10` is prime.
[Answer]
## PARI/GP, 16 bytes, cheap as hell
For some reason this wasn't disallowed (noting that the command doesn't factor or equation-solve):
```
polisirreducible
```
Test case
```
%(x^2+x+1)
```
returns `1` (true). The other examples work similarly.
But to show that this is solvable the hard way, here's a full solution.
## Less cheap, but sloooooooooow
There's really no point golfing this.
```
Beauzamy(P)=
{
  my(d=poldegree(P),s,c);
  s=sum(i=0,d,polcoeff(P,i)^2/binomial(d,i));
  c = 3^(3/2 + d);
  c *= s / (4*d*Pi);
  abs(c * pollead(P))
}
factorpol(P)=
{
  my(B=Beauzamy(P)\1, t=B*2+1, d=poldegree(P)\2, Q);
  for(i=0,t^(d+1)-1,
    Q=Pol(apply(n->n-B, digits(i,t)));
    if(Q && poldegree(Q) && P%Q==0, return(Q))
  );
  0
}
irr(P)=
{
  factorpol(P)==0
}
```
Edit: Commenters have pointed out that the first method may be disallowed by good taste, the spirit of the rules, the Geneva Convention, standard loophole rules, etc. I don't agree, but in any case I posted the second version along with the first and certainly it seems acceptable.
]