Es factorizar polinomios más fácil que la factorización de números enteros?

Question

Estaba leyendo el libro de Álgebra: Capítulo 0 , por Paolo Aluffi, y llegó a través de la siguiente afirmación, en la página 290, Ejercicio 5.9:

De hecho, es mucho más difícil factor de enteros de los números enteros polinomios.

Lo que quiero saber es:

1. ¿Qué es exactamente el significado de más fácil.
2. ¿Por qué es eso así? Porque parece muy poco intuitivo para mí que encontrar la factorización de un alto grado del polinomio (con un montón de grandes entero coeficientes) debería ser más fácil que el factoring el grado del polinomio en sí.

Answer 1

El significado preciso es que hay más rápido algoritmos para factorizar un polinomio con $n$ los coeficientes de cada uno de los con $m$ bits de un número entero con $n\cdot m$ bits. Por supuesto que es más fácil para el factor de número de $n$ sí, pero esto no es correcta la comparación, debido a que el número de bits necesarios para expresar $n$ es mucho menor que el número de bits necesarios para expresar el polinomio.

Para polinomios, hay algoritmos que se pueden factorizar el polinomio en una cantidad de tiempo polinomial en $n\cdot m$. La estrategia es esencialmente de forma recursiva factor del polinomio sobre $\mathbb F_{p^n}$ más grande y más grande $n$ y diferentes valores de $p$, y el uso de esta pieza juntos una factorización sobre los enteros. Una discusión más detallada se puede encontrar en esta página de la Wikipedia.

Para los números enteros, ningún algoritmo es conocido que tiene tiempo de ejecución polinomial en $n\cdot m$. El mejor algoritmo conocido es el horriblemente complicado General del Campo de Número de Tamiz.

Una razón de esto podría parecer sorprendente, es que es mucho más fácil escribir una correcta entero algoritmo de factorización de una correcta polinomio factorización de algoritmo. Resulta que si se reemplaza "correcta" con "rápido", lo contrario es cierto.