¿Es Factorizando polinomios tan duros como la factorización de números enteros?

Question

Parece haber un consenso de que la factorización de números enteros es duro (en algunos precisa computacional sentido). Se sabe si el polinomio factorización es computacionalmente fácil o difícil?

Una cosa que yo inicialmente pensaba que si podríamos factor de polinomios fácilmente, entonces podríamos factor $$ n por la búsqueda de un polinomio $p(x)$ con $p(m)=n$ $m$, entonces "fácilmente factorización" $p$ obtener $p(x)=q(x)\cdot r(x)$. Entonces $p(m)\cdot r(m)$ sería una factorización de $n$. Pero no tendríamos ninguna información acerca de si uno de estos pasó a ser 1.

¿Alguien tiene una solución o una referencia para este problema? (He buscado en internet, pero todo lo que podía encontrar era cómo hacer la factorización como en alto los problemas de la escuela.)

Answer 1

No es un polinomio de tiempo del algoritmo para factorizar polinomios con coeficientes racionales (la liga de la leche algoritmo de Lenstra, Lenstra, y Lovasz), para factorizar polinomios sobre los racionales es conocida por ser "fácil" (polinomio, se considera que para hacer que el problema computacionalmente fácil", incluso si en la práctica no funcionan bien). De los métodos conocidos para el factoring general enteros, por otro lado, el mejor es el General de campo de número de tamiz, que se cree para ser super-polinomio y sub-exponencial (la complejidad del algoritmo se calcula de forma heurística), que es peor.

En general, este tipo de problema tiende a ser más fácil para los polinomios de que para los enteros, gracias a la existencia de la derivada. Por lo tanto, es relativamente fácil la prueba de "FLT para polinomios" (acerca de una página de largo); es trivial para detectar si un polinomio es squarefree (y no tan fácil algoritmo es conocido por enteros), y así sucesivamente.

Su idea para la factorización de enteros con polinomios es muy natural, pero desafortunadamente no en ambas direcciones: no todos los de la factorización de $n$ se detecta por una factorización de $p(x)$, y no todos los de la factorización de $p(x)$ daría una factorización de $n$. Por ejemplo, $p(x) = x^2+x+1$ es irreductible más de $\mathbb{Q}$ (incluso más de $\mathbb{R}$), pero $p(10) = 111 = 3\times 37$, por lo que esta factorización no puede ser "detectado" por factorización $p(x)$. Por otro lado, $q(x) = x^4 - 1 = (x-1)(x^3+x^2+x+1)$ no podría detectar factores de $p(2)=15$. Si usted tiene que comenzar a hurgar por polinomios, probar varios para ver si puede detectar un trivial de la factorización, incluso si finalmente "hit" en la que da la respuesta a la facilidad de factorizar el polinomio puede ser eclipsado por la dificultad de encontrar un "buen" polinomio en primer lugar, por lo que toda la cosa puede ser un lavado.

Answer 2

Como se ha mencionado, hay (teórico) el polinomio de tiempo de los algoritmos de factorización de polinomios tales como la liga de la leche. Sin embargo, no se desempeñan bien en la práctica, así que varios otros algoritmos son típicamente empleados (por ejemplo, de Berlekamp, Zippel escasa modular, etc). Para algunas referencias, véase mi respuesta a la pregunta anterior aquí sobre las mejores formas de factor de polinomios.

El método que propones parece estar relacionado con un antiguo método debido a los Bernoulli, de Schubert, de Kronecker, Hausmann et al. Usted puede encontrar una buena presentación de este algoritmo con los ejemplos desarrollados en 16 Segundos.1 p 347ff en: Mora. La solución de ecuación polinómica de sistemas, I. La Kronecker-Duval Filosofía. Esto puede ser accesible por la búsqueda de libros de Google. Para encontrar dicha sección rápido, simplemente la búsqueda para "Schubert". Véase también Mignotte interesante artículo [2] en la historia (resumen adjunta a continuación).

RESUMEN. El Primer Método General de la Factorización de Polinomios.
En un libro de Memorias de la F. T. de Schubert.

Analizamos dos pequeños trabajos de N. Bernoulli (1708) y F. T. Schubert (1794) en la factorización de enteros polinomios así como la obra de L. Kronecker y B. R. Hausmann sobre el mismo tema. El método de factorización de Bernoulli-Schubert utiliza el cálculo y la interpolación de diferencias finitas. Fue redescubierto por Kronecker (1882), que utiliza la interpolación de Lagrange. Ambos procedimientos permiten el efectivo de la factorización de polinomios de tener pequeños grados y los coeficientes. Un algoritmo que combina los resultados de Bernoulli-Schubert y de Kronecker fue obtenida por B. R. Hausmann. Su método es particularmente útil para la factorización de la estabilidad de polinomios. Los tres métodos son brevemente en comparación con los modernos algoritmos de factorización.

[1] Edwards, H. Kronecker de la Matemática Algorítmica
(Presentado en "la Computabilidad en Europa 2008," Atenas, 19 de junio de 2008).
http://www.math.nyu.edu/faculty/edwardsd/athens.pdf

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