155-ЗНАЧНОЕ ЧИСЛО РАЗЛОЖЕНО НА ВИДЕОКАРТАХ

Разложить большое число на простые множители трудно, и эта трудность важна для криптографии — поэтому статья тщательно оговаривает, чему её результат не угрожает. Публичные числа «RSA challenge» служат эталонами для методов факторизации. RSA-155 — одно из них: 155 цифр, или 512 бит.

Два решета — по рекорду у каждого

Доминируют два семейства алгоритмов. Решето числового поля (number field sieve) — чемпион для очень больших чисел: оно разложило RSA-155 ещё в 1999 году, и, согласно статье, общий рекорд сейчас — 270-значное число RSA-896 в 2026 году. Более старое квадратичное решето асимптотически медленнее и, по собственным словам авторов, «не тот инструмент» для общих рекордов. Однако у него есть свой список рекордов: самым большим разложенным им числом было RSA-150 в июне 2025 года, на что ушло 11 664 ядро-часа CPU.

Квадратичное решето ищет множество небольших чисел, которые полностью раскладываются по набору малых простых, а затем с помощью линейной алгебры комбинирует их в два квадрата x² и y², равные по модулю N. Наибольший общий делитель затем выявляет множитель. На компьютере это кошмар для графических процессоров (GPU): обращения к памяти разбросаны далеко за пределы любого кэша, проверки полны ветвлений, а итоговая алгебра работает в двоичной арифметике, которую не поддерживает ни одна библиотека производителей. Прежние попытки на GPU ускоряли лишь отдельные шаги.

Всё на видеокарте

Фабиан Янушевский и Кристоф Хайнрихс из математического института Падерборнского университета в Германии создали CUDA-MPQS — квадратичное решето с открытым исходным кодом, в котором каждый этап — подготовка многочленов, просеивание, проверка кандидатов, сопоставление частичных результатов, построение матрицы, её решение и извлечение итогового квадратного корня — выполняется на GPU. Обычный процессор лишь управляет, выполняет настройку и занимается вводом-выводом; авторы явно перечисляют немногие шаги, оставшиеся на стороне хоста. В тесте со 100-значным числом GPU был занят 99,9% времени просеивания, без пауз на ожидание процессора.

Масштабирование выявило тонкую ошибку. При размере RSA-155 8-битный счётчик, используемый при просеивании, переполнялся как раз на самых ценных кандидатах, молча отбрасывая от 98 до 99,5% из них. Команда заменила его насыщающимся счётчиком, который, как они доказывают, даёт идентичные результаты.

RSA-155 примерно за сутки

14 июля 2026 года конвейер разложил RSA-155 на два простых числа по 78 цифр, проверенных и на GPU, и на хосте:

• Просеивание: 64 GPU NVIDIA H100 на 16 узлах, 10,8 часа, собрано около 17,3 миллиона соотношений.
• Линейная алгебра: одна H100 в течение 10,9 часа, матрица из 16,7 миллиона строк с 684 миллионами ненулевых элементов.
• Итого: 700,6 GPU-часа и 242 киловатт-часа, примерно 24 часа от старта до множителей. На просеивание пришлось 98,4% затрат.

Насколько известно авторам, это самое большое целое число, когда-либо разложенное квадратичным решетом, на пять цифр больше прежнего рекорда, — причём достигнуто простейшим вариантом метода, который хранит лишь одно «большое простое» на соотношение, тогда как недавние рекорды использовали три.

Быстрее лучших процессоров

На 100-значном числе одна H100 справляется за 29,2 секунды, а потребительская RTX 5070 Ti — за 51 секунду. В контролируемом сравнении на том же числе, с измерением энергопотребления с обеих сторон, одна H100 оказалась в 3,6–4,2 раза быстрее самого быстрого квадратичного решета на CPU, работающего на 96 ядрах процессора AMD EPYC, и примерно в девять-десять раз быстрее другого стандартного пакета. Они также заново разложили RSA-150 за 302,9 GPU-часа против 11 664 ядро-часов прежнего рекорда — авторы подчёркивают, что это соотношение не является ускорением при равных условиях.

Никакой угрозы шифрованию

Авторы говорят прямо: RSA-155 уже было разложено, это не общий рекорд факторизации, и «ничто здесь не сужает запас надёжности». Код к тому же намеренно ограничен примерно 155 цифрами. Их интерес в другом: показать, что нерегулярный алгоритм с обилием ветвлений может целиком жить на GPU. Естественной следующей целью они называют GPU-реализацию решётчатого просеивания (lattice siever), лежащего в основе решета числового поля, — работу, которую, как они отмечают, другие уже начали, разложив RSA-260 и RSA-896 с помощью GPU-версий существующего пакета, причём вторая сделана с Claude.

Конфликт интересов. Авторы сообщают, что использовали генеративный ИИ и агентные инструменты программирования: модели Claude от Anthropic (через Claude Code) наряду с моделями GPT от OpenAI и Gemini от Google для разработки программ, а также модели Claude для подготовки данных и рукописи. Они утверждают, что весь вывод ИИ был вручную просмотрен и проверен. Эту статью также написал Claude.