# Is factoring polynomials easier than factoring integers? [duplicate]

I was reading the book Algebra: Chapter 0 , by Paolo Aluffi, and came across the following assertion, in page 290, Exercise 5.9:

It is in fact much harder to factor integers than integers polynomials.

What I want to know is:

1. What exactly is the meaning of easier.
2. Why is that so? Because it seems quite unintuitive for me that finding a factorization of a high degree polynomial (with a lot of big integer coefficients) should be easier than factoring the degree of polynomial itself.
-

## marked as duplicate by egreg, Sami Ben Romdhane, Chris Godsil, ml0105, Sanath K. DevalapurkarApr 27 '14 at 3:07

One observation that might help motivate the claim is that repeated factors of integer polynomials are easily found (taking the GCD with the formal derivative), while no such simple method is known to find repeated factors of integers themselves. – hardmath Apr 21 '14 at 21:31
A polynomial also gives you more hints. Let $n$ be the degree of a polynomial in $x$. You get the sum of the roots as the coefficient of $x^{n-1}$. You get the sum of products of (self-avoiding) pairs of roots (with multiplicities) as $x^{n-2}$. ... and so on until ... You get the product of the roots as the constant coefficient. For an integer, you get a slab of bits with a large number of (unknown) internal carries (relative to performing elementary school multiplication), which provides vastly less traction. – Eric Towers Apr 22 '14 at 5:46

The precise meaning is that there are faster algorithms to factor a polynomial with $n$ coefficients each with $m$ bits than an integer with $n\cdot m$ bits. It is of course easier to factor the number $n$ itself--but this is not the correct comparison, because the number of bits required to express $n$ is much smaller than the number of bits required to express the polynomial.
For polynomials, there are algorithms which can factor the polynomial in an amount of time polynomial in $n\cdot m$. The strategy is essentially to recursively factor the polynomial over $\mathbb F_{p^n}$ for larger and larger $n$ and different values of $p$, and using this piece together a factorization over the integers. A more thorough discussion can be found on this Wikipedia page.
For integers, no algorithm is known that has runtime polynomial in $n\cdot m$. The best known algorithm is the horrendously complicated General Number Field Sieve.