Factorización en Primos
Todo número entero mayor que 1 puede escribirse como producto de números primos, y esa descomposición es única, salvo por el orden de los factores.
Ese resultado tiene nombre: teorema fundamental de la aritmética. Garantiza que 60 es siempre 2 × 2 × 3 × 5, y nunca otra combinación de primos.
La herramienta devuelve los factores, indica si el número es primo y lista todos los divisores, que son las combinaciones posibles de los factores encontrados.
El método es la división sucesiva: se divide entre 2 mientras se pueda, y luego se prueban los impares a partir de 3.
La prueba se detiene cuando el divisor supera la raíz cuadrada de lo que queda. Funciona porque si un número tiene un factor mayor que su raíz, el factor complementario es necesariamente menor y ya se habría encontrado.
Lo que sobra al final, si es mayor que 1, es primo y entra como último factor.
Esa parada en la raíz cuadrada es lo que hace viable el método: comprobar si 1.000.003 es primo requiere unas mil divisiones, no un millón.
Multiplicar dos primos grandes es instantáneo. Recuperar los dos factores a partir del producto es caro computacionalmente, y no se conoce ningún método rápido para el caso general.
Esa asimetría sostiene la criptografía RSA: la clave pública es el producto, y la seguridad reside en que nadie consiga factorizarlo en un tiempo razonable.
Los números de algunas decenas de dígitos se factorizan rápido aquí. Las claves criptográficas reales tienen cientos de dígitos, y por eso quedan fuera de alcance.
Preguntas frecuentes
Porque rompería la unicidad de la factorización. Si el 1 fuera primo, 6 podría ser 2 × 3, o 1 × 2 × 3, o 1 × 1 × 2 × 3, y la descomposición dejaría de ser única.
El cálculo usa enteros de precisión arbitraria, pero el tiempo crece con el tamaño. Los números de algunas decenas de dígitos son rápidos; mucho más allá la espera se vuelve impracticable.
Son todas las combinaciones posibles de los factores primos. Para 12, que es 2 × 2 × 3, los divisores son 1, 2, 3, 4, 6 y 12.
Porque si un número tiene un factor mayor que su raíz, el factor complementario es menor y ya se habría encontrado antes. Probar más allá de la raíz sería repetir trabajo.