El cálculo del máximo común divisor de polinomios sobre cuerpos de números

Abstract

RESUMEN: Al aplicar el algoritmo de Euclides tal y como hemos visto en el grado en el caso de polinomios con coeficientes racionales ocurre el fenómeno llamado explosión de coeficientes. El tamaño de los coeficientes de los polinomios intermedios hace que este algoritmo no sea eficiente en la práctica para polinomios de grado moderado. En esta memoria trabajaremos con polinomios con coeficientes en un cuerpo de números. Presentamos y analizamos un algoritmo alternativo propuesto por Langemyr y McCallum, basado en una algoritmo similar propuesto por Brown en el caso de polinomios con coeficientes racionales, que realiza el cálculo del máximo común divisor sobre varios anillos finitos para luego reconstruir el máximo común divisor original usando el Teorema Chino de los Restos.

ABSTRACT: When applying Euclid’s algorithm to the case of polynomials with rational coefficients, the phenomenon known as coefficient explosion arises. The size of the coefficients of the intermediate polynomials makes this algorithm unfeasible in practice for polynomials of moderate degree. In this report, we study the case of polynomials with coefficients in a number field. We present and analyze an alternative algorithm proposed by Langemyr and McCallum, based on an algorithm proposed by Brown for the case of rational coefficients, that computes greatest common divisor over several finite rings and then reconstructs the original greatest common divisor using the Chinese Remainder Theorem.