Dos ejemplos: factorización y MCD

Las computadoras clásicas que existen hoy en día son increíblemente rápidas, y su velocidad parece ir en aumento constante. Por eso, algunos podrían pensar que las computadoras son tan rápidas que ningún problema computacional está fuera de su alcance.

Esta creencia es falsa. Algunos problemas computacionales son tan intrínsecamente complejos que, aunque existan algoritmos para resolverlos, ninguna computadora en el planeta Tierra hoy es lo suficientemente rápida como para ejecutar esos algoritmos hasta su conclusión, ni siquiera con entradas de tamaño moderado, dentro del tiempo de vida de un ser humano, ni siquiera dentro del tiempo de vida de la Tierra misma.

Para explicarlo mejor, introduzcamos el problema de la factorización de enteros.

Factorización de enteros

Entrada: un entero $N\geq 2$
Salida: la factorización prima de $N$

Por factorización prima de $N$ nos referimos a una lista de los factores primos de $N$ y las potencias a las que deben elevarse para obtener $N$ mediante multiplicación. Por ejemplo, los factores primos de $12$ son $2$ y $3,$ y para obtener $12$ debemos tomar el producto de $2$ elevado a la potencia $2$ y $3$ elevado a la potencia $1.$

$$12 = 2^2 \cdot 3$$

Salvo por el orden de los factores primos, existe una única factorización prima para cada entero positivo $N\geq 2,$ hecho conocido como el teorema fundamental de la aritmética.

Algunas demostraciones sencillas de código en Python serán útiles para explicar mejor la factorización de enteros y otros conceptos relacionados con esta discusión. Las siguientes importaciones son necesarias para estas demostraciones.

# Added by doQumentation — required packages for this notebook
!pip install -q sympy

import math
from sympy.ntheory import factorint

La función factorint del paquete de matemáticas simbólicas SymPy para Python resuelve el problema de factorización de enteros para cualquier entrada $N$ que elijamos. Por ejemplo, podemos obtener la factorización prima de 12, que naturalmente coincide con la factorización mostrada arriba.

N = 12
print(factorint(N))

{2: 2, 3: 1}

Factorizar números pequeños como $12$ es sencillo, pero cuando el número $N$ a factorizar se hace más grande, el problema se vuelve más difícil. Por ejemplo, ejecutar factorint sobre un número considerablemente más grande provoca una pausa breve pero notable en una computadora personal típica.

N = 3402823669209384634633740743176823109843098343
print(factorint(N))

{3: 2, 74519450661011221: 1, 5073729280707932631243580787: 1}

Para valores aún más grandes de $N,$ las cosas se vuelven imposiblemente difíciles, al menos hasta donde sabemos. Por ejemplo, el RSA Factoring Challenge, llevado a cabo por RSA Laboratories entre 1991 y 2007, ofrecía un premio en efectivo de $100,000 dólares por factorizar el siguiente número, que tiene 309 dígitos decimales (o 1024 bits en representación binaria). El premio por este número nunca fue reclamado y sus factores primos permanecen desconocidos.

RSA1024 = 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563
print(RSA1024)

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

No vale la pena intentar ejecutar factorint sobre RSA1024; no terminaría en el tiempo de vida de ninguno de nosotros.

El algoritmo más rápido conocido para factorizar enteros grandes se conoce como la criba del cuerpo de números. Como ejemplo de su uso, el número del desafío RSA RSA250, que tiene 250 dígitos decimales (o 829 bits en representación binaria), fue factorizado utilizando la criba del cuerpo de números en 2020. El cálculo requirió miles de años-núcleo de CPU, distribuidos entre decenas de miles de máquinas alrededor del mundo. Aquí podemos apreciar ese esfuerzo verificando la solución.

RSA250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711

print(RSA250 == p * q)

True

La seguridad del criptosistema de clave pública RSA se basa en la dificultad computacional de la factorización de enteros, en el sentido de que un algoritmo eficiente para factorizar enteros lo rompería.

A continuación, consideremos un problema relacionado pero muy diferente: el cálculo del máximo común divisor (o MCD) de dos enteros.

Máximo común divisor (MCD)

Entrada: enteros no negativos $N$ y $M,$ al menos uno de los cuales es positivo
Salida: el máximo común divisor de $N$ y $M$

El máximo común divisor de dos números es el entero más grande que divide exactamente a ambos.

Este problema es fácil de resolver con una computadora — tiene aproximadamente el mismo costo computacional que multiplicar los dos números de entrada. La función gcd del módulo math de Python calcula el máximo común divisor de números considerablemente más grandes que RSA1024 en un abrir y cerrar de ojos. (De hecho, RSA1024 es el MCD de los dos números en este ejemplo.)

N = 4636759690183918349682239573236686632636353319755818421393667064929987310592347460711767784882455889983961546491666129915628431549982893638464243493812487979530329460863532041588297885958272943021122033997933550246447236884738870576045537199814804920281890355275625050796526864093092006894744790739778376848205654332434378295899591539239698896074
M = 5056714874804877864225164843977749374751021379176083540426461360945653967249306494545888621353613218518084414930846655066495767441010526886803458300440345782982127522212209489410315422285463057656809702949608368597012967321172325810519806487247195259818074918082416290513738155834341957254558278151385588990304622183174568167973121179585331770773

print(math.gcd(N, M))

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

Esto es posible porque contamos con algoritmos muy eficientes para calcular el MCD, el más conocido de los cuales es el algoritmo de Euclides, descubierto hace más de 2,000 años.

¿Podría existir un algoritmo rápido para la factorización de enteros que aún no hayamos descubierto, que permita factorizar números grandes como RSA1024 en un abrir y cerrar de ojos? La respuesta es sí. Aunque podríamos esperar que un algoritmo eficiente para factorizar, tan simple y elegante como el algoritmo de Euclides para calcular el MCD, ya habría sido descubierto, nada descarta la existencia de un algoritmo clásico muy rápido para la factorización de enteros, más allá del hecho de que hasta ahora no hemos logrado encontrar uno. Podría descubrirse mañana, pero no contengas la respiración. Generaciones de matemáticos e informáticos han buscado, y factorizar números como RSA1024 sigue estando fuera de nuestro alcance.