INVESTIGADORES
CHARA Maria De Los Angeles
congresos y reuniones científicas
Título:
Detectando potencias enteras en tiempo esencialmente polinomial
Autor/es:
MARÍA DE LOS ANGELES CHARA
Lugar:
Universidade Estadual de Campinas
Reunión:
Jornada; XIV Jornadas de Jovens Pesquisadores da AUGM; 2006
Institución organizadora:
Asociación de Universidades Grupo Montevideo (AUGM)
Resumen:
En este trabajo presentamos un método para determinar en tiempo polinomial si dado un entero positivo n existen enteros m y k tales que n=m^k. Para ello analizamos las raíces de la función f(x)=x^k-n utilizando variantes discretas de los conocidos métodos de la bisección y de Newton. La resolución eficiente de este problema es de interés cuando se desea factorizar números enteros. Demostramos que el número de pasos es del orden de log_2 n log log_2 n. También damos estimaciones del error cuando se utiliza el método de Newton.
