Calculadora de Factorización en Primos

Acerca de Calculadora de Factorización en Primos

Esta herramienta factoriza enteros desde 2 hasta 2¹²⁸ − 1, unos 3,4 × 10³⁸ o 39 cifras. Trabaja en tres fases. La división por tanteo con los primos pequeños hasta 2²⁰ (alrededor de un millón) elimina los factores pequeños; un test de Miller–Rabin comprueba si lo que queda es primo; y si es compuesto, la variante de Brent del algoritmo rho de Pollard encuentra un factor, tras lo cual cada trozo se factoriza a su vez.

El límite de 39 cifras se debe a que la aritmética de enteros de 128 bits está escrita directamente en WebAssembly. Los números normales de JavaScript dejan de representar enteros con exactitud por encima de 2⁵³, unos 9 × 10¹⁵. El tiempo que tarda depende menos del tamaño del número que del tamaño de su segundo factor primo más grande, así que dos entradas de 39 cifras pueden terminar en un milisegundo o en horas.

Por qué la división por tanteo se atasca con números grandes

El método evidente es dividir entre 2, 3, 5, 7 y así sucesivamente. Un compuesto n siempre tiene un factor no mayor que √n, así que basta con llegar hasta ahí. El problema es que √n es enorme: para un número de 20 cifras es un número de 10 cifras, y en el peor caso harían falta cerca de diez mil millones de divisiones; con 39 cifras, más de 10¹⁹.

Por eso esta herramienta solo usa la división por tanteo hasta 2²⁰. La mayoría de los enteros tienen varios factores pequeños y quedan casi descompuestos en esa fase. Lo que sobrevive es un primo grande o el producto de dos o tres primos grandes, y ahí entra el algoritmo más ingenioso.

Rho de Pollard: encontrar un factor p en unos √p pasos

El algoritmo que John Pollard publicó en 1975 itera una sucesión pseudoaleatoria como x → x² + c (mod n). Reducida módulo un factor primo desconocido p, la sucesión acaba repitiéndose y, por el mismo razonamiento que la paradoja del cumpleaños, suele hacerlo en unos √p pasos. Cuando ocurre, el máximo común divisor entre la diferencia de dos términos y n revela p. Richard Brent aceleró la detección del ciclo en 1980, y ese mismo año el método descompuso el número de Fermat F₈, de 78 cifras.

Lo esencial es que el tiempo depende de p, el menor factor primo, y no de n. El peor caso es un semiprimo equilibrado, dos primos de tamaño parecido, donde p ≈ √n y el número de pasos ronda n^(1/4). La estimación que la herramienta muestra antes de un cálculo largo supone ese peor caso, así que un número con un solo factor pequeño termina mucho antes de lo previsto.

Medido en un ordenador de sobremesa, el producto de dos primos de 10 cifras (20 cifras) tardó unos 0,05 segundos y el de dos primos de 13 cifras (25 cifras), unos 1,5 segundos. Cada 16 bits más, unas cinco cifras, multiplican el tiempo por 16, de modo que un semiprimo de 39 cifras formado por dos primos de 20 cifras puede tardar horas. En cambio, un primo de 39 cifras como 2¹²⁷ − 1 solo necesita el test de primalidad y responde en unos 0,01 segundos.

Comprobar si un número es primo es mucho más fácil que factorizarlo

Decidir si un número es primo y encontrar sus factores son problemas de dificultad muy distinta. El test de Miller–Rabin desenmascara a los compuestos con unas pocas exponenciaciones modulares, sin necesidad de hallar ningún factor. Por debajo de 2⁶⁴ esta herramienta usa como bases los primos del 2 al 37, lo que hace la respuesta determinista; por encima usa 18 bases hasta 61, un test probabilístico para el que no se conoce ningún contraejemplo en este rango.

Un simple test de Fermat se deja engañar por los números de Carmichael, como 561 = 3 × 11 × 17, que lo superan para toda base coprima con ellos. Miller–Rabin no cae en la trampa: al introducir 561 aparece al instante 3 × 11 × 17.

Cómo depende RSA de que factorizar sea difícil

Una clave pública RSA publica n = p × q, con dos primos grandes secretos. Cualquiera puede cifrar con n, pero para construir la clave privada hacen falta p y q. Multiplicar es instantáneo y deshacerlo no lo es; esa asimetría es la base de todo el sistema. RSA-129, un número de 129 cifras propuesto en la columna de Martin Gardner en Scientific American en 1977, no se factorizó hasta 1994, gracias a un proyecto que reunió ordenadores de voluntarios de todo el mundo.

Las claves RSA que se usan hoy suelen tener 2048 bits, unas 617 cifras: dieciséis veces la longitud en bits que admite esta herramienta. Para números así se usa la criba del cuerpo de números, no rho de Pollard, y aun así los récords públicos de factorización quedan muy por debajo de 2048 bits. Factorizar aquí un semiprimo de 64 bits y luego uno de 80 es una forma rápida de notar lo deprisa que crece el coste con cada bit.

Ejemplos

Cómo se usa

1. Introduce un entero mayor o igual que 2; se ignoran comas y espacios.
2. Con números grandes aparece primero el tiempo estimado para el peor caso, y puedes detener el cálculo cuando quieras.
3. Los factores repetidos se agrupan con exponentes; toca una entrada del historial para copiar la igualdad.

Preguntas frecuentes