35
$\begingroup$

There seems to be a consensus that factorization of integers is hard (in some precise computational sense.) Is it known whether polynomial factorization is computationally easy or hard?

One thing I originally thought was that if we could factor polynomials easily, then we could factor $n$ by finding a polynomial $p(x)$ with $p(m)=n$ for some $m$, then "easily factorizing" $p$ to get $p(x)=q(x)\cdot r(x)$. Then $q(m)\cdot r(m)$ would be a factorization of $n$. But we wouldn't get any information if one of these happened to be 1.

Does anyone have a solution or a reference for this problem? (I searched online, but all I could find was how to do factorization like in high school problems.)

$\endgroup$
0

3 Answers 3

57
$\begingroup$

There is a polynomial time algorithm for factoring polynomials with rational coefficients (the LLL algorithm of Lenstra, Lenstra, and Lovasz), so factoring polynomials over the rationals is known to be "easy" (polynomial time is considered to make the problem "computationally easy", even if in practice it does not perform well). Of the known methods for factoring general integers, on the other hand, the best is the General number field sieve, which is believed to be super-polynomial and sub-exponential (the complexity of the algorithm is estimated heuristically), which is worse.

In general, this kind of problem tends to be easier for polynomials than for integers, thanks to the existence of the derivative. Thus, there is a fairly easy proof of "FLT for polynomials" (about one page long); it is trivial to detect if a polynomial is squarefree (and no such easy algorithm is known for integers), and so on.

Your idea for factoring integers with polynomials is very natural, but unfortunately fails in both directions: not every factorization of $n$ would be detected by a factorization of $p(x)$, and not every factorization of $p(x)$ would give a factorization of $n$. For example, $p(x) = x^2+x+1$ is irreducible over $\mathbb{Q}$ (even over $\mathbb{R}$), but $p(10) = 111 = 3\times 37$, so this factorization cannot be "detected" by factoring $p(x)$. On the other hand, $q(x) = x^4 - 1 = (x-1)(x^3+x^2+x+1)$ would not detect factors of $q(2)=15$. If you have to start rummaging around for polynomials, trying several to see if you can detect a nontrivial factorization, even if you eventually "hit" on one that gives the answer the ease of factoring the polynomial may be overshadowed by the difficulty in finding a "good" polynomial in the first place, so that the entire thing may be a wash.

$\endgroup$
2
  • $\begingroup$ Very interesting, +1. $\endgroup$ Mar 10, 2011 at 5:49
  • 5
    $\begingroup$ @Joseph: Yes: a polynomial $p(x)$ (over a UFD or field) is squarefree if and only if it is relatively prime to its derivative. Just write $p(x) = g^n(x)f(x)$ with $g$ and $f$ relatively prime; if $n\gt 1$, then $p'(x)=ng^{n-1}(x)g'(x)f(x)+f'(x)g^n(x)$ has $g(x)$ as a factor in common with $p(x)$. Conversely, if $p(x)$ is a common irreducible factor of $g$ and $g'$, $g(x)=p(x)q(x)$, then $p(x)$ divides $p'(x)q(x)$, so $p(x)$ divides $q(x)$ (being irreducible, it is relatively prime to $p'(x)$), so $p^2(x)$ divides $g(x)$. So it is trivial to see if a polynomial over a field is squarefree or not $\endgroup$ Mar 10, 2011 at 14:24
19
$\begingroup$

As was mentioned there are (theoretical) polynomial time algorithms for factoring polynomials such as LLL. However, they do not perform well in practice, so various other algorithms are typically employed (e.g. Berlekamp, Zippel's sparse modular, etc). For some references see my answer to a prior question here on the best ways to factor polynomials.

The method you propose seems related to an old method due to Bernoulli, Schubert, Kronecker, Hausmann, et al. You can find a nice presentation of this algorithm with worked examples in Sec.16.1 pp. 347ff in: Mora. Solving polynomial equation systems, I. The Kronecker-Duval Philosophy. This may be accessible by Google books. To find said section quickly simply search for "Schubert". See also Mignotte's interesting paper [2] on the history (abstract appended below).

ABSTRACT. The First General Method of Factorization of Polynomials.
On a Memoir of F.T. Schubert.

We analyse two little known papers of N. Bernoulli (1708) and F.T. Schubert (1794) on the factorization of integer polynomials as well as the work of L. Kronecker and B.A. Hausmann on the same topic. The factorization method of Bernoulli-Schubert uses the calculus and the interpolation of finite differences. It was rediscovered by Kronecker (1882), who used Lagrange interpolation. Both procedures allow the effective factorization of polynomials having small degrees and coefficients. An algorithm combining the results of Bernoulli-Schubert and Kronecker was obtained by B.A. Hausmann. His method is particularly useful for the factorization of stable polynomials. The three methods are briefly compared with modern factorization algorithms.

[1] Edwards, H. Kronecker's Algorithmic Mathematics
(Presented at "Computability in Europe 2008," Athens, June 19, 2008.)
http://www.math.nyu.edu/faculty/edwardsd/athens.pdf

[2] Maurice Mignotte; Doru Stefanescu
La première méthode générale de factorisation des polynômes.
Autour d'un mémoire de F.T. Schubert
Revue d'histoire des mathématiques 7, fascicule 1 (2001), 67-89
http://smf4.emath.fr/Publications/RevueHistoireMath/7/html/smf_rhm_7_67-89.html

$\endgroup$
0
$\begingroup$

The problem is multifold:

  • irreducibility, as the other answers showed, is a stumbling block at the best of times.
  • Polynomial factoring (by faster methods), isn't the only way we could factor an integer, but it's probably the most cost effective to implement.
  • We can use polynomial remainder theorem, it can work with things like $(x-(x-7))$ aka 7. But, that and other modular arithmetic tricks, is how we get to most divisibility tricks to begin with.

  • $(n-1)^2+1$ integers always have a subset with a sum divisible by n (via pigeonhole principle). But, does going through potentially all 10,295,472 combinations of 7 from a set of 37 digits, repeatedly until you are left with 30 non-zero digits ( not necessarily clumped together) in the entire number , sound appealing to find out if a large number is divisible by 7 ? Welcome to the subset sum problem, applied to multisets.

  • Most of the above facts seem useful ( plus a few more), until you consider implementing them. If you don't have enough digits, you can't implement them. Once you do, good luck going down lots of dead ends potentially.

example:

142859374923636582974652016665013284472978368643690531468097543

okay if I summed things right it's a multiple of 3 (bad choice of digits, casted out multiples of 3 using digit sum rule).

multiple of 5 test via the 4th point:

14285937492363658 has a subset of digits that's a multiple of 5, we can get rid of the whole thing it sums to a multiple of 5,

29746520166650132 Also sums to a multiple of 5 ...

84472978368643690 Also sums to a multiple of 5 ... ( what I get for not using a random number)

531468097543 Also sums to a multiple of 5 but isn't 17 digits.

Of course the digit sum trick plus pigeonhole principle aren't useful as the base being divisible by 5 is enough, just to check the last digit. in base's that have remainder 1 on division by 5 the number would have shrunk to 12 digits or less. It would change which digits mattered in different bases.

$\endgroup$

You must log in to answer this question.

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