3
$\begingroup$

It is easy to construct a polynomial of degree four with integer coefficients that doesn't have any real roots, if it has a real root then it can be factored by division by $x-a$ where $a$ is the root (maybe it's difficult to find the root, if it is not an integer number, but there are a lot of techniques for this).

To construct such a polynomial we can multiply two irreducible (with no real roots also) quadratic polynomials. Then I want to factor this polynomial without knowing any of this two quadratic irreducible polynomials, what is the best approach for solving this?

I constructed this polynomial

$x^4+2x^3-5x^2-6x+21$

Computers (wolfram alpha, etc) can factor this, but how?

And what is the field of algebra that I have to study to answer such questions?

Thank you

$\endgroup$
1
  • $\begingroup$ A formula exists for the roots of a general quartic polynomial, which is one way WolframAlpha might go about factoring: en.wikipedia.org/wiki/… $\endgroup$
    – Kaj Hansen
    Jan 14, 2016 at 8:00

1 Answer 1

1
$\begingroup$

The basic idea is to factor the polynomial over $\mathbb F_p$ for one or more suitable primes $p$, and attempt to lift these factorizations to factorizations over $\mathbb Z$. There are bounds on the size of the primes $p$ one needs to consider, making this an effective algorithm.

Over $\mathbb F_p$ one can first do a number of preliminary reductions, to reduce the problem to one where the polynomial $f$ to be factored is square-free and all irreducible factors are of fixed degree $d$. A simple way to proceed is then the (probabilistic) method of Cantor and Zassenhaus: If one takes a random monic polynomial $g$ of degree $\le 2d-1$, then the gcd of $f$ and $g$ will be a non-trivial factor of $f$ with probability about $1/2$. So, just proceed taking random $g$'s and computing the gcd with $f$, until you have a complete factorization. Other algorithms (e.g., Berlekamp) exist for this final step.

The book A Course in Computational Algebraic Number Theory by H. Cohen treats these problems in Chapter 3.4 (Factorization of Polynomials Modulo $p$) and Chapter 3.5 (Factorization of Polynomials over $\mathbb Z$ or $\mathbb Q$). These two chapters don't require any knowledge of algebraic number theory, and are easy to skim through or read.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .