polynomial factorization
Factoring 60 into 2 * 2 * 3 * 5 breaks a number into its irreducible building blocks. Polynomial factorization does the same for polynomials: it rewrites x^4 - 1 as (x - 1)(x + 1)(x^2 + 1), a product of pieces that cannot be broken down further over the chosen number system. It is the symbolic analogue of prime factorization, and one of the showpiece abilities of a computer-algebra system.
What counts as 'irreducible' depends on where the coefficients live. Over the rationals, x^2 + 1 does not factor; over the complex numbers it splits into (x - i)(x + i). Surprisingly, factoring polynomials with integer coefficients is far easier than factoring integers (which underpins cryptography) — efficient algorithms exist. A modern factorizer works in clever stages: first take out repeated factors using the polynomial GCD of the polynomial and its derivative (square-free factorization); then factor the square-free part modulo a small prime, where finite-field methods (Berlekamp's and Cantor-Zassenhaus's algorithms) work fast; and finally lift those modular factors back up to integer factors using Hensel lifting, the p-adic version of Newton's method. The same factor-mod-a-prime-and-lift strategy threads through much of exact computation.
Factorization matters everywhere exact structure is wanted: simplifying expressions, finding exact roots, integrating rational functions (partial fractions need the denominator factored), and solving equations symbolically. The honest cautions are familiar. Factoring is genuinely harder than the GCD and can be slow on high-degree, many-variable polynomials, and the answer depends entirely on the coefficient domain you ask about — 'irreducible' over the rationals, the reals, and the complexes give three different factorizations of the same polynomial. And as always in computer algebra, intermediate coefficients can swell, which is exactly why the work is pushed into finite fields and lifted back.
Factor x^4 - 1. As a difference of squares it is (x^2 - 1)(x^2 + 1), and x^2 - 1 splits again into (x - 1)(x + 1). Over the rationals the full factorization is (x - 1)(x + 1)(x^2 + 1) — x^2 + 1 is irreducible there. Allow complex coefficients and it factors further into (x - 1)(x + 1)(x - i)(x + i).
The same polynomial factors differently over the rationals and the complexes.
Factoring integer-coefficient polynomials is, perhaps counterintuitively, much easier than factoring large integers — the hardness behind RSA does not carry over. But the result is only meaningful relative to a stated coefficient domain, and high-degree multivariate cases can still be expensive.