RSA-232 factorization has been selected as a symbol of the Year of Science and Technology in Russia, as stated in the report on the most significant achievements of Russian scientists in 2020 that President of the Russian Academy of Sciences Alexander Sergeev presented to the RAS General Meeting.
This impressive achievement has been made by Nikolai Zamarashkin and Dmitry Zheltkov from the Moscow Center for Fundamental and Applied Mathematics at Marchuk Institute of Numerical Mathematics of RAS (INM RAS) and their colleague, Sergey Matveev, a research scientist at Skoltech (now an associate professor at Lomonosov Moscow State University). To achieve this result, the team used MSU’s Lomonosov supercomputer and Skoltech’s Zhores supercomputer.
RSA is the first public-key cryptographic system used for encryption and digital signature. The list of huge RSA numbers was published in 1991, and about half of them have not yet been factorized. Factorization is used to decode information. As the numbers become bigger, their factorization involves an increasingly larger number of operations and a unique calculation for each number.
For example, the first 100-digit RSA number was factorized in 1991 using a single computer that coped with the task in a matter of days, while RSA-129 factorization required upwards of 1,500 computers in 1994. RSA numbers and problems of their factorization are under non-decreasing interest for researchers from France, the United States, and many other countries.
“There has not been a result of such impact in Russia for nearly a decade, and we are very proud that our achievement gets the full attention of the professional community, particularly in the Year of Science and Technology in Russia. This achievement would not have been possible without the close collaboration of INM RAS, Skoltech, and MSU. Thanks to a quota on Zhores, we solved a super-large system of linear equations (numbers 0 and 1), the key element of factorization that required about a month of continuous computations using almost the entire CPU segment of the supercomputer,” Sergey Matveev says.
“RSA-232 has 232 decimal digits and two divisors of about the same size as the root of the number itself, i.e., about 116 digits. If we search for divisors in the range from 2 up to the root, the number of variants to sort through will be about 10 to 20 times greater than the number of atoms in the universe. Smartly selecting divisor candidates and then picking out the only correct pair from the pool of candidates is a formidable technological challenge,” Sergey adds.
The key to success was Zhores, one of the most advanced supercomputers in Russia installed at the Skoltech Center for Computational and Data-Intensive Science and Engineering (CDISE).
+7 (495) 280 14 81