2
$\begingroup$

For instance, given the polynomial expression $xy + x + y + 1$ it will output $(x+1)(y+1)$.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ You mean factorization, right? $\endgroup$ – Karolis Juodelė Apr 21 '14 at 6:11
4
$\begingroup$

"Brute-force" in the context of factoring polynomials may involve factoring of integers, which is a hard problem. Factoring polynomials is easier, e.g. look up "FACTORING MULTIVARIATE POLYNOMIALS VIA PARTIAL DIFFERENTIAL EQUATIONS" by Gao, and "Factoring Multivariate polynomials over the integers" by Wang and Rothschild.

$\endgroup$
  • $\begingroup$ Are you saying that since you can represent integers with polynomials, for instance $1 + X + X^2$ to represent $7$ (in binary), that finding the optimal polynomial would be a superset of the problem of integer factoring? $\endgroup$ – EnjoysMath Apr 21 '14 at 18:12
  • 1
    $\begingroup$ @EnjoysMath No I'm saying the opposite, I'm saying that finding a polynomial factorization (or determining that a polynomial is irreducible) is easier than factoring an integer or determining that it's prime. Just because a polynomial is irreducible doesn't mean the polynomial always produces prime values, and just because an integer is not prime doesn't mean it will be easy to find a non-trivial polynomial that the integer satisfies that can be factored. $\endgroup$ – user2566092 Apr 21 '14 at 18:16

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