Proponga un algoritmo para factorizar un número entero tal que cada uno de sus factores sea sin plaza .
Gracias,
Respuesta
¿Demasiados anuncios?
Es trivial dada la factorización completa en primos. Actualmente no conocemos ninguna otra forma de calcular las partes libres de cuadrados y se sospecha ampliamente que no se puede calcular de ninguna forma más sencilla.
Este problema es importante porque una de las principales tareas de la teoría algebraica computacional de números se reduce a él (en tiempo polinómico determinista). En concreto, el problema de calcular el anillo de enteros de un campo numérico algebraico depende de la descomposición libre de cuadrados del discriminante del polinomio al calcular una base integral.
Contrasta esta dificultad con la trivial descomposición libre de cuadrados de los polinomios mediante gcd con su derivada. La disponibilidad de las derivadas para los polinomios abre una poderosa caja de herramientas que no está disponible para los enteros. Por ejemplo, una vez que las derivadas están disponibles, también lo están los Wronskians, que proporcionan poderosas medidas de dependencia en la teoría de la trascendencia y la aproximación diofantina. Un ejemplo sencillo, pero impresionante, es la demostración elemental del caso polinómico del teorema ABC de Mason, que da lugar a una demostración de nivel escolar de la FLT para polinomios.
Para las referencias, véase mi posta aquí.
