Los límites de la computación: los números primos

Hoy hablaremos de matemáticas, pero no será hablar por hablar: son conceptos relevantes para la computación y justifican por qué hay tanto interés en la computación cuántica. Venga, vamos a «hacer el primo».

Un número primo es un número natural que tiene exactamente dos divisores: 1 y él mismo. Es decir, 1 no es un número primo, pero 2, 3, 5 y 7 sí lo serían, por ejemplo. Hay muchas propiedades conocidas sobre los números primos, como que «hay un número infinito de números primos» (gracias, señor Euclides) o que «cualquier número natural puede descomponerse de forma única como producto de sus factores primos» (Teorema fundamental de la aritmética). Sin embargo, hay otras propiedades que se intuyen pero que no todavía no han sido probadas. La más famosa es la conjetura de Goldbach, planteada en 1742 y aún por demostrar, que se enuncia en una de sus versiones como «todo número par mayor que 2 puede expresarse como la suma de dos números primos«. Si os pica la curiosidad sobre esta última conjetura, os recomiendo una novela que la tiene como protagonista.

Desde el punto de vista computacional, hay dos problemas destacados en el ámbito de los números primos. El primero consiste en decidir, dado un número, si éste es primo o no (test de primalidad). El segundo consiste en calcular la lista de factores primos de un número proporcionado como entrada (factorización). ¿Y por qué estos problemas son relevantes? La causa no está en la belleza de las matemáticas, sino en las ventajas materiales que aporta su resolución. Y la culpa de todo la tiene la criptografía.

Los criptosistemas de clave pública basan su funcionamiento en un par de claves, una de las cuáles se difunde de forma abierta (clave pública) mientras que sólo es conocida por el propietario (clave privada). La clave pública permite cifrar un mensaje de forma que sólo pueda abrirse con la clave privada. Por contra, la clave privada permite firmar un mensaje, de forma que cualquier persona puede verificar que el emisor es quién afirma ser mediante su clave pública. Es decir, el sistema permite asegurar tanto la privacidad como la autenticidad de las comunicaciones… si todo se hace como Dios manda.

Uno de los criptosistemas de clave pública más populares, RSA, utiliza dos números primos (p, q) en su proceso de construcción de las claves pública y privada. Los números primos p y q forman parte de la clave privada, mientras que la parte pública incluye el valor n = p * q. Ser capaz de factorizar el número n revelaría información sobre la clave privada que debería ser secreta. ¿Os imagináis lo que sería leer los mensajes de un tercero o suplantarle? El potencial para hacer maldades es ilimitado.

La «defensa» de RSA ante los intentos de factorización es doble. Por un lado se utilizan claves con muchos bits, es decir, números primos muy grandes, con muchos dígitos. Y por otro lado, los mejores algoritmos conocidos para factorizar números (sin recurrir a casos especiales) no son muy rápidos: dado un número x con b bits, ningún algoritmo conocido puede factorizarlo en caso general usando un tiempo proporcional a b^k (es decir, no hay algoritmos de tiempo polinómico). Pensemos un algoritmo de fuerza bruta muy poco inteligente que comprobara cada valor entre 2 y x para ver si es un divisor. Semejante algoritmo realizaría un número de divisiones proporcional a x, un valor que es exponencial respecto al número de bits b de la entrada. Mira por donde, en este caso el coste exponencial es algo bueno que nos salva de la gente malintencionada que querría romper nuestras claves.

Aquí es donde entra a escena la computación cuántica. Existe un algoritmo para ordenadores cuánticos, el algoritmo de Shor, que permite calcular los factores primos de un número de b bits en tiempo b^3 usando espacio b. Semejante algoritmo permitiría factorizar números enteros en un ordenador cuántico que dispusiera de suficientes qubits (el equivalente a la unidad de información en la computación cuántica) para representar a dicho número.

El algoritmo de Shor funciona de verdad y ya se ha probado en computadores cuánticos factorizando los números 15 y 21. Sin embargo, existe un problema de escalabilidad a nivel de hardware: los ordenadores cuánticos actuales no pueden manipular un número elevado de qubits simultáneamente, aunque se van dando pequeños pasos en esa dirección. Hasta el momento, nadie ha construido un ordenador cuántico lo suficientemente potente para romper claves RSA, aunque los delicuentes y las agencias de inteligencia tienen este tema en su agenda desde hace tiempo. Quién sabe, quizás ya lo han hecho: es un tema que da para muchas teorías conspiranoicas y algunas películas sobre el tema.