¿Recordais cuando estabais en el colegio y os ponian de deberes hacer minimos común multiplos y máximos común divisores a manta? Los que no veais mucho la tele y/o no os hayais golpeado mucho en la cabeza recordareis que un paso previo para hacerlos era factorizar los números, ya sabeis, 2*2*2*3*5 = 120 y esos rollos.

Pues ahora teneis la oportunidad de recuperar todo aquel precioso tiempo de niñez absolutamente perdido, gracias al reto RSA.

Los Laboratorios RSA pertenecen a RSA Security, una empresa que vende "soluciones" (ya sabeis como me parto con estas palabrerias) de seguridad a nivel de mensaje en internet, lo que en la práctica imagino que quiere decir que venden software de criptografí­a, ssh propietario, firma digital y cosas por el estilo. Lo que no sé si sabeis es que el modelo actual de comunicaciones secretas está fuertemente basado en los números primos, o más exactamente, en la dificultad para determinar si un número es primo o no.

Evidentemente, no hablo de números como el 120 que ponia de ejemplo, sino númerazos de cientos y cientos de cifras, que son tan dificiles de factorizar que entra en juego la economia. Por ejemplo, yo mando un mensaje a mi banco con un cheque en blanco de 1000 euros. El mensaje va cifrado, y un jaker 31337 lo intercepta, se dispone a romperlo... y se encuentra con que leerlo en claro le cuesta 2000 euros, en ordenadores lo suficientemente potentes, electricidad o lo que sea... está claro que el negocio no le iria muy bien.

Por ello, y aquí­ es donde entran vuestros fantabulosos conocimientos factoriles, la empresa que comentaba antes paga a quien rompa una clave que ellos dan, lo que en realidad no es más que determinar si un numero bastante grande es primo o no, para comprobar por donde anda el estado del arte en cuanto a poder de computación y saber a partir de cuantos bits las claves son economicamente seguras. Y paga bastante bien, $30.000 dolares, unos 25.200€ por el que menos ahora mismo.

Así­ que ya lo sabeis, si teneis una tarde libre y quereis ganar algo de pasta, os cogeis una libreta y un boligráfo, y a factorizar.

Una simple advertencia: esto que os escribo es una rendición por mi parte.

Cuando lo leí­, pensé, pues se puede intentar. Me hice un cliente distribuido en Pascal básico, para poder repartir el trabajo entre varios ordenadores y sistemas operativos sin necesidad de runtimes de decenas de megas y aprovechar la velocidad del código ejecutado sobre el interpretado. Decidí­ que cada paquete a distribuir podria ser de mil millones de números, es decir, que cada paquete fuera comprobar si en un rango de mil millones estaban los factores, y cuando empecé a trabajar en el servidor eche cuentas y, ouch, resultó que incluso con esos paquetones, salian 2 elevado a 214 paquetes a comprobar.

Si, exactamente, para optar a los 4 millones y pico de pesetas hay que hacer mil millones multiplicado por 2 elevado a 214 divisiones, optimizaciones aparte, por lo que os advierto que podria ser una tarde muuuy larga.

Mejor seguir echando euromillones.

ACTUALIZACIí“N 20051211: Ojo que no eran 2²¹⁴ sino 10 elevado a 214, es decir, un uno seguido de doscientos catorce ceros.