Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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.
share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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
up vote 13 down vote accepted

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.

One reason this might seem surprising is that it is much easier to write a correct integer factorization algorithm than a correct polynomial factorization algorithm. It turns out that if you replace "correct" with "fast", the opposite is true.

share|cite|improve this answer
No, the precise meaning depends on the model of computation employed, sparse vs. dense, straight-line programs, etc. – Bill Dubuque Apr 21 '14 at 22:24

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