Se ha factorizado uno de los grandes número RSA: los avances en computación van permitiendo lo que parecía imposible

Hay concursos y... Concursos. Por fortuna algunos muy imaginativos y que instan a que exprimamos nuestras neuronas para lograr batir récords tan curiosos como puede ser el de sacar decimales al número pi o el RSA Factoring Challenge, y este año hemos tenemos un ganador para el RSA 230, aunque estrictamente no entra el concurso.

¿Para el qué? Para uno de los números semiprimos que forman parte de este concurso creado en 1991 por los Laboratorios RSA para incentivar la investigación en la teoría computacional de números y la factorización de números enteros grandes. Un concurso que, aunque terminó en 2007 (y con ello la remuneración por cada premio), sigue vivo de alguna manera y ahora se ha conseguido un nuevo récord factorizando.

Pero, ¿qué es factorizar?

Factorizar una expresión matemática consiste en descomponerla, de modo que el producto de los factores obtenidos da dicha expresión inicial. Es algo que se practica en la asignatura de matemáticas durante la enseñanza secundaria, y quizás estemos familiarizados con Ruffini y otros métodos como el factor común.

Cuando hablamos de números enteros, o de números primos como en este caso, lo que se hace es descomponer un numero, lo cual es un problema cuando se trata de números muy grandes. Y ahí es donde entran los números RSA, siendo RSA-200 un número de 200 dígitos (que ya se factorizó), para los cuales no se conoce aún ningún algoritmo que resuelva su factorización de manera eficiente, tardando meses en realizar los cálculos.

El RSA Challenge se canceló, como decíamos, en 2007, antes de que la totalidad de los números se factorizasen. No obstante, hay quien ha seguido investigando y este año ha sido Samuel Gross quien ha logrado factorizar el RSA 230, según anuncia EFF.

Congrats to Samuel Gross on factoring 17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199929221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689! #rsa230
— EFF (@EFF) 13 de septiembre de 2018

Fue el propio Gross quien publicó el logro, si bien aún no ha dado los detalles de cómo lo consiguió (solamente que fue en la empresa Noblis). EFF compartía el número, pero aquí os mostramos la factorización de RSA 230:

RSA230 = 179694915979410667329161284495732461563675618080126000708889188355317264603414

9093349337224786865075523085586419992922181443668472287405206525793749569434838926

3171152522525654410980819170611742509702440718010364831638288518852689

= 452845035801049202661243973912016675891124604749370004007395

6759261590397250033699357694507193523000343088601688589

* 3968132623150957588532394439049887341769533966621957829426966

084093049516953598120833228447171744337427374763106901

Todo tiene una aplicación práctica en matemáticas

Las matemáticas pueden parecer abstractas cuando son muy complejas, pero siempre hay una aplicación práctica. En este caso la factorización de números complejos está relacionada con ciencias de la computación, computación cuántica o el desarrollo de algoritmos criptográficos, como lo es el propio RSA.

De hecho, la finalidad última del RSA Challenge era comprobar la fortaleza de este algoritmo criptográfico en cuanto a seguridad, de modo que si se lograse un algoritmo para la factorización de enteros que fuese rápido significaría que el RSA es inseguro. Para lograrlo se requieren equipos complejos, como la combinación de 80 CPUs Opteron AMD que se usaron para el RSA-640 (de 193 cifras).

Aún quedan muchos números RSA por factorizar, siendo el RSA-768 el número más grande que se ha logrado descomponer (232 cifras). Así que si os animáis tenéis para elegir, una lástima que ya no optéis a los 200.000 dólares que iban a entregar a quien lograsee factorizar el RSA-2018 (617 cifras).