21
\$\begingroup\$

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
Improve this question
\$\endgroup\$
15
  • 12
    \$\begingroup\$ From some quick googling this is a hard problem regardless of golfing. \$\endgroup\$ Commented Mar 20, 2015 at 18:15
  • 7
    \$\begingroup\$ Am I correct in thinking that by prime you mean irreducible? If so then this is basically a variant on this question about factoring polynomials, and I suspect that it won't attract any answers which don't factor. \$\endgroup\$ Commented Mar 20, 2015 at 19:20
  • 1
    \$\begingroup\$ According to this recent paper, "We are interested in the question of deciding whether a given polynomial is irreducible or not. Consequently, a simple test or criterion which would give this information is desirable. Unfortunately, no such criterion which will apply to all the classes of polynomials has yet been devised". \$\endgroup\$ Commented Mar 20, 2015 at 19:43
  • 2
    \$\begingroup\$ @AlexA., there are many many "if" tests which work for some polynomials, but the question is asking for an "if and only if" test which works for all polynomials. \$\endgroup\$ Commented Mar 20, 2015 at 20:07
  • 2
    \$\begingroup\$ This is a nice problem! Note that usually polynomials are only prime relative to a base ring (or field). In particular, if the field is the complex numbers, then no polynomial of degree greater than 2 is prime. So I would specify whether you want Rational (probably the most straightforward) Integer (this will involve some integer factoring as well), or modulo some number m. If m is prime, then there are rather easy algorithms. Otherwise things are a bit more tricky...(but feasible) \$\endgroup\$ Commented Mar 20, 2015 at 20:46

2 Answers 2

Reset to default
6
+500
\$\begingroup\$

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} (* {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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

PARI/GP, 155 148 135 130 120 111 bytes

This returns the truthy value 1 when a polynomial is irreducible and the special falsy value gnil (which is treated as 0 when you try to use it) when the polynomial is reducible.

(P,d=poldegree(P),B=3^d*norml2(P)^2,t=B*2+1)->for(i=0,t^d,Q=Pol([n-B|n<-digits(i,t)])&&i%t-B&&P%Q==0&&return);1

Test case

%(x^2+x+1)

returns 1 (true). The other examples work similarly.

Note that this is extremely slow. An irreducible polynomial of degree d with coefficients between -m and m will require constructing around 3d2 * (d+1)d * m4d potential polynomial factors. Reducible polynomials are a bit faster.

PARI/GP, 16 bytes, cheap as hell

Technically not disallowed (noting that the command doesn't factor or equation-solve):

polisirreducible

Ungolfed version of #1

This version checks all possible factors up to the Beauzamy bound, so it's very slow. It's still faster than the golfed version, which checks further to save characters.

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 }
Improve this answer
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Hmmmm... I'm pretty sure that this command does factor and/or solve equations under the hood. (Also, if a challenge disallows certain built-ins is kinda implied that a built-in that just solves the problem is also not in the spirit of the challenge.) \$\endgroup\$ Commented Apr 30, 2015 at 18:05
  • \$\begingroup\$ @MartinBüttner: I think that the first answer fits the letter, but not the spirit, of the challenge's rules. That's why I wrote the second version, which is a legitimate solution. It can check that x^4+1 (which is famously reducible mod any prime) is irreducible in 86 milliseconds. If nothing else others can adapt and golf this version. \$\endgroup\$ Commented Apr 30, 2015 at 18:07
  • 1
    \$\begingroup\$ The first answer falls in a loophole which is banned by default: Using built-in functions to do the work. Please remove it from your answer, or at least indicate that it is not a valid solution. \$\endgroup\$ Commented Apr 30, 2015 at 18:17
  • 5
    \$\begingroup\$ @isaacg That is not currently a valid standard loophole (due to the vote breakdown +44/-29). Charles, if you agree that only the second answer is really legitimate, then you should include its byte count instead. \$\endgroup\$ Commented Apr 30, 2015 at 18:22
  • \$\begingroup\$ @MartinBüttner: I don't -- I think both are legitimate by the rules of this question and the general loopholes thread. But I added a comment to point out the issue. \$\endgroup\$ Commented Apr 30, 2015 at 18:27

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.