2
$\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$
  • $\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 '16 at 8:00
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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