Факторизация числа RSA-232: решения и нерешенные вопросы в задачах отображения алгоритмов на реальные вычислительные системы

Пусть $n = pq$ с большими простыми $p$ и $q,$ а $x < n$ целое число, битовое представление которого является сообщением. Выберем число $e \in \mathbb{Z}^*_{(p-1)(q-1)}.$ Число $y \in \mathbb{Z}_n,$ получаемое по формуле,
\begin{equation} \label{eq:1} y = x^d \mod n, \end{equation}
рассматривают как зашифрованное сообщение. Дешифровка (восстановление $x$) не вызывает трудностей, если известен обратный к $e$ элемент $d \in \mathbb{Z}^*_{(p-1)(q-1)}.$ В этом случае
\begin{equation} \label{eq:2} x = y^d \mod n. \end{equation}
В системе шифрования RSA параметры $n$ и $e$ считаются общедоступными. Определить $d$ не сложно, зная $p$ и $q,$ но именно информация о делителях $n$ является закрытой, а нахождение $p$ и $q$ относится к сложным задачам.
Между научными группами ведется соревнование по разложению больших RSA-чисел. За последние 15 лет все рекорды получены с помощью общего метода решета числового поля (Generalized Number Field Sieve, GNFS). В основе GNFS лежит следующая последовательность шагов:

• а) выбирается число $m$ и неприводимый полином $f(x) \in \mathbb{Z}[x]$ такой, что $f(m) = 0 \mod n;$
• б) в кольце $\mathbb{Z}[\theta]$ ($\theta$ – корень $f$) выбирается база делителей из простых идеалов первого порядка, а в кольце $\mathbb{Z}_n$ выбирается база делителей из простых чисел;
• в) набирается большое число пар $(a,b) \in \mathbb{Z}^2$ таких, что $a+b\theta$ расскладывается по базе простых идеалов, а $a + bm$ по базе простых чисел;
• г) из полученных соотношений составляется сверх-большая однородная система линейных уравнений над полем из двух элементов, любое решение которой определяет два числа $u$ и $v$ в $\mathbb{Z}_n,$ удовлетворяющие соотношению
  \begin{equation} \label{eq:3} u^2 = v^2 \mod n. \end{equation}
  
• д) С вероятнотью большей $\frac12$ либо $u+v,$ либо $u-v$ являются делителями $n.$

Сложность алгоритма GNFS экспоненциально растет с $n$ и определяется шагами в) и г). Шаг в) называется просеиванием, имеет высокую алгоритмическую сложность, но идеально масштабируется с точки зрения параллельных вычислений. На шаге г) составляется и решается сверх-большая однородная линейная система над полем из двух элементов. С ростом числа бит в представлении RSA-чисел именно эффективная реализация шага г) на современных массивно-параллельных вычислительных системах представляет наибольшие трудности и является критической для всего алгоpитма.
В ИВМ РАН создание программной реализации шага г) осуществлялось более 10 лет. Существующий программный код уникален. Парадоксальный выбор в пользу формально последовательного алгоритма Ланцоша-Монтгомери решения линейных систем над полем из двух элементов был компенсирован детальным изучением внутреннего параллелизма метода. Реализация ИВМ РАН использует практически все известные параллельные технологии (многопоточность, распределенные вычисления, специализированные ускорители), масштабируется на вычислительные системы с десятками тысяч ядер. Структуры данных и методы вычислений оптимизированы под эффективное использование современных вычислительных систем и современной оперативной памяти. Отказ от применения любой из вышеназванных технологий приводит к многократным потерям в производительности.
Таким образом, программный код ИВМ РАН является одновременно высоко технологичным продуктом и решением математической задачи эффективного отображения алгоритмов на реальные вычислительные системы.
17 февраля 2020 года в ИВМ РАН была закончена факторизация числа RSA-232 (число с $232$ десятичными знаками). На момент получения этот результат делил второе место в мире. Рекордным было число RSA-240 (результат опубликован 9 декабря 2019 года).