Calculadora de factorización en números primos

¿Qué es la factorización en primos?

Todo número entero mayor que uno es primo —divisible solo por sí mismo y por uno— o bien un producto de primos, y ese producto es único salvo por el orden en que lo escribas. Eso es el teorema fundamental de la aritmética, y factorizar es encontrarlo: 360 es 2 × 2 × 2 × 3 × 3 × 5, que se escribe 2³ × 3² × 5, y ninguna otra combinación de primos da 360.

Es la operación que hay debajo de buena parte de la aritmética corriente. Simplificar una fracción es cancelar factores primos comunes. Un mínimo común denominador se construye con los primos de cada denominador, tomando la mayor potencia de cada uno. Y el número de divisores sale directo de la factorización: multiplica cada exponente más uno, así que 360 = 2³ × 3² × 5¹ tiene 4 × 3 × 2 = 24 divisores, y la herramienta los lista todos.

Esta calculadora trabaja con aritmética entera exacta y no con coma flotante, así que no hay ningún tamaño a partir del cual las respuestas se vuelvan aproximadas en silencio. Pega un número de cuarenta cifras y cada factor que devuelva será exactamente correcto.

Cómo usarla

1. Escribe o pega un número entero. Las comas, los espacios y los guiones bajos se ignoran, así que un número copiado de una hoja de cálculo funciona tal cual. Los decimales, el signo menos y la notación exponencial se rechazan en vez de reinterpretarse en silencio.
2. Lee la factorización y los divisores. Los números compuestos aparecen en forma exponencial con todos sus factores primos, además del número de divisores y, cuando la lista es de longitud razonable, todos los divisores. Un número primo simplemente se informa como primo.
3. Si dice que no terminó, créetelo. Los números difíciles alcanzan un límite de trabajo y la herramienta te lo dice, enseñando lo que sí encontró y lo que queda. El botón ofrece una búsqueda más larga; si esa también falla, el número está de verdad fuera del alcance de un navegador en un tiempo razonable.

Por qué algunos números la detienen, y por qué ese es el asunto

Factorizar es enormemente más fácil para unos números que para otros, y la diferencia no está en el tamaño. Ir sacando primos pequeños resuelve la mayoría al instante, porque la mayoría de los números tienen un factor pequeño: sobre cuarenta números aleatorios de cuarenta cifras, el del medio se factoriza en torno a un sexto de segundo. Lo difícil es un número sin ningún factor pequeño: un semiprimo, el producto de dos primos grandes y nada más.

El método ingenuo lo deja clarísimo. La división por tentativa prueba todos los candidatos hasta la raíz cuadrada, así que su coste se duplica cada dos cifras más o menos: en la máquina donde se construyó esta página, un semiprimo de dos primos de diez cifras tardó tres segundos, y uno de dos primos de once cifras tardó tres minutos y medio. Esta herramienta usa en su lugar la rho de Pollard, que llevó ese mismo caso de once cifras de 212 segundos a 68 milisegundos: tres órdenes de magnitud, con un algoritmo que cabe en veinte líneas.

Pero la rho solo mueve el muro, no lo quita. Un semiprimo de dos primos de trece cifras sigue estando fuera del alcance de una pestaña del navegador, y eso no es un defecto por el que disculparse. Es la base misma de la criptografía de clave pública: las claves RSA son semiprimos elegidos precisamente porque multiplicar dos primos grandes es trivial y deshacerlo no lo es. Los números que protegen tu banco tienen la misma forma que aquel con el que esta página se rinde, solo que muchísimo mayores.

Por eso el límite aquí es un presupuesto de trabajo y no un tope de cifras. Un tope de cifras se equivocaría en las dos direcciones: rechazaría el número de cuarenta cifras que se factoriza en un milisegundo y aceptaría el de veinticinco que tarda segundos. Contar el esfuerzo significa que la herramienta para cuando el trabajo se vuelve irrazonable, tenga el número el aspecto que tenga, y que informe con honestidad en vez de congelar la pestaña.

Límites honestos

Cuando la búsqueda se detiene antes de tiempo, todo lo que se muestra sigue siendo cierto. Los factores encontrados son de verdad factores primos de tu número; lo que queda simplemente no se ha descompuesto. Multiplica los factores mostrados por el resto y recuperas tu número exactamente: esa propiedad se cumple con cualquier presupuesto, y es lo que las pruebas comprueban con más insistencia, porque una respuesta parcial que se hace pasar por completa es mucho peor que una que admite haber parado.

La primalidad se decide con el test de Miller-Rabin usando un conjunto fijo de doce testigos. Esa combinación está demostrada como correcta para todo número por debajo de unos 3,3 × 10²⁴, que cubre cuanto esta herramienta va a recibir en la práctica; por encima pasa a ser un test probabilístico en vez de una demostración, y la probabilidad de error es minúscula pero no nula. Casi ninguna calculadora dice de qué lado de esa línea está.

El cero y el uno tienen respuestas propias en vez de un resultado vacío. El cero no tiene factorización, porque todos los números lo dividen. El uno no es ni primo ni compuesto —no tiene ningún factor primo—, lo cual es un hecho sobre la definición y no un descuido, y la razón de que el teorema fundamental empiece en el dos.

La lista de divisores está limitada en pantalla, porque un número muy compuesto puede tener miles y mostrarlos todos no ayuda a nadie. El recuento que aparece encima es siempre el total real, calculado a partir de los exponentes y no contando lo que se ve.

¿Por qué es gratis?

Porque no cuesta nada mantenerla. Toda la aritmética ocurre en tu navegador con su soporte nativo de enteros grandes: no se sube nada, ningún servidor ve tus números y no hay cuenta ni límite de cuántos compruebas.

El motor se contrasta con un factorizador escrito de forma independiente en otro lenguaje, y con algo más fuerte que cualquier implementación de referencia: una factorización se verifica multiplicándola de vuelta, y las pruebas lo hacen con todos los presupuestos de trabajo hasta cero. Dos de los fallos que esa comprobación cazó eran justo de los peligrosos: una respuesta parcial presentada como completa, y un resto declarado primo.