Prime polynomials

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 1

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 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}
(* {True, True, True, True, True} *)

It takes 14s on my laptop to conclude that 3x^9-8x^8-3x^7+2x^3-10 is prime.

Answer 2

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.