Raíces enteras de un polinomio

10

¿Qué algoritmo podemos usar para encontrar todas las raíces enteras de un polinomio con coeficientes enteros?f(x)

Observo que Sage puede encontrar las raíces en unos pocos segundos, incluso cuando todos los coeficientes de son muy grandes. ¿Cómo es capaz de hacer eso?f(x)

ds.algorithms na.numerical-analysis usuario12290
fuente
1
¿Está buscando un algoritmo para devolver una raíz entera de un polinomio dado? Si es así, eso es indecidible y la pregunta está fuera de tema aquí. Puede preguntarlo en Computer Science, que tiene un alcance más amplio.
Kaveh
77
Espere. ¿Por qué ser indecidible hace que la pregunta esté fuera de tema? Esta es una pregunta legítima a nivel de investigación.
Jeff el
2
Entonces, ¿cómo lo hace Sage? Ser indecidible, incluso ser conocido por ser indecidible, no hace que el problema sea teóricamente poco interesante. Los científicos informáticos teóricos resuelven problemas indecidibles todo el tiempo; ver, por ejemplo, toda la verificación asistida por computadora.
Jeffε
11
f(x)f(x)dd
1
@Pratik No necesita bases Gröbner en el caso univariante.
Yuval Filmus

Respuestas:

10

f

En cualquier caso, la documentación de Sage explica claramente cómo están haciendo la búsqueda raíz: "El siguiente método, que se usa si K es un dominio integral, es intentar factorizar el polinomio. Si esto tiene éxito, entonces para cada grado uno factor a * x + b, agregamos -b / a como raíz (siempre y cuando este cociente esté realmente en el anillo deseado) ". Ver http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html .

Entonces su pregunta es ¿Cómo factorizan eficientemente polinomios con coeficientes enteros? Aparentemente, Sage está llamando a NTL para hacer eso (consulte http://www.shoup.net/ntl/doc/ZZXFactoring.txt para obtener detalles sobre NTL).

Si desea un método asintóticamente eficiente, puede consultar el método de Lenstra, Lenstra y Lovasz ( https://openaccess.leidenuniv.nl/handle/1887/3810 ).

minar
fuente
1
Gracias por la sugerencia útil! Fascinante. ¿Podría estar dispuesto a editar su respuesta para explicar cómo convertir esto en un algoritmo y cuál es su tiempo de ejecución? ¿Es exponencial el tiempo de ejecución en el peor de los casos (porque puede tomar tiempo subexponencial para factorizar, y luego puede haber exponencialmente muchos divisores del coeficiente inicial y final)? Si es así, ¿hay mejores algoritmos o se trata de lo mejor que se puede hacer? Además, ¿este enfoque no encuentra solo las raíces racionales, pero no las raíces irracionales?
DW
Al releer la pregunta y ver que la interpretas de manera diferente, ya no estoy completamente seguro, pero a mí y a algunos comentaristas nos pareció claro que la pregunta se refiere a raíces enteras. ¿No lo lees así?
minar
@ Seminario, tienes razón. Ahora que releí la pregunta, parece ser así. Debo haber leído la pregunta demasiado rápido. (Inicialmente interpreté mal la pregunta como que implica que queremos todas las raíces de un polinomio con coeficientes enteros, pero al volver a leer la pregunta, parece una mala interpretación).
DW
2
Para un método asintóticamente y prácticamente eficiente, el algoritmo más conocido es el de Van Hoeij (ver aquí ). En realidad, NTL parece estar usándolo.
Bruno