Dado un número con algunas centenas de cifras decimales, es posible comprobar si es un número primo y si hay factores pequeños y si hay factores cercanos a la raíz cuadrada. ¿Pero qué más? ¿Existen otras informaciones, relevantes para la factorización, que puedan obtenerse con un ordenador personal?
Respuesta
¿Demasiados anuncios?
Faiz
Puntos
1660
Si el número no es demasiado grande, el mejor algoritmo conocido actualmente es la criba cuadrática. Los números hasta aproximadamente $120$ dígitos pueden ser factorizados de esta manera (Con un poco más de esfuerzo hasta cerca de $150$ dígitos).
Para encontrar factores hasta cerca de $30-40$ dígitos, el método de la curva elíptica (ECM) es el mejor y no depende del tamaño del número.
En raras ocasiones, el $p-1$ -Método da grandes factores.
La comprobación de la primalidad puede hacerse de forma mucho más eficiente. Algunas pruebas muy buenas son la de Miller-Rabin y la de BPSW. Si queremos demostrar la primalidad, esto también es rutinario hasta aproximadamente $1\ 000$ dígitos.
