Devin разложил RSA-260 на GPU за $400 тыс., в 10 раз дешевле рекорда

Исследователь Cognition с помощью агентов Devin разложил на простые множители число RSA-260 из 260 десятичных знаков. Это новый рекорд среди публично решённых задач RSA Factoring Challenge: предыдущий, RSA-250, был поставлен в феврале 2020 года. Вычисления заняли около 4 900 GPU-дней (13,5 GPU-года) и обошлись примерно в $400 тыс. по рыночным ценам. По оценке автора, это в 10 раз дешевле прежнего публичного уровня.

Автор подчёркивает, что алгоритмических прорывов нет. Использовано общее решето числового поля (GNFS), самый эффективный известный метод для чисел крупнее примерно 100 знаков. База — сильно переработанный CADO-NFS. Выигрыш дала, по его словам, «старая добрая инженерия производительности» под устройство памяти GPU. Квантового компьютера тоже нет, и угадывать 130-значные простые числа вручную никто не пытался.

Откуда взялись вычисления

Кластеры Cognition для обучения и инференса LLM состоят из стоек NVL72, в каждой номинально по 18 компьютеров с быстрым NVLink. Планировщик упаковывает задачи в стойки, и где-то остаётся свободный узел: резерв на случай отказа, нечётное число машин при чётной задаче, 17 узлов вместо 18. В сумме это однозначный процент всей мощности.

Исследователь настроил планировщик так, чтобы заполнять эти дыры однонодовыми задачами с нижайшим приоритетом. Не хватало источника задач, которые можно прервать в любой момент. Решето по решёткам подошло идеально: оно параллелится на миллиарды мелких единиц работы и безопасно для мгновенного вытеснения. Все прежние публичные рекорды GNFS считали эту стадию только на CPU, потому что на GPU мешали ветвления и хаотичный доступ к памяти.

Как работал Devin

Промпт ушёл 13 августа в 0:11:58 по тихоокеанскому времени. Задача: сделать drop-in замену CPU-решету las из CADO-NFS, быстрее оригинала. Через два часа автор добавил требование тянуть параметры RSA-250 и лёг спать. К утру, после ещё семи часов итераций, Devin справился.

Дальше агенты оптимизировали остальной конвейер. За три недели в среднем работало 3 параллельные сессии, максимум 18. Автор заглядывал в цикл раз в пару часов. Devin сам ставил эксперименты, подбирал параметры решета и линейной алгебры, отлаживал код и запускал расчёты на кластере. Автор признаётся, что глубоко математику не понимает, а свою роль описывает как постановку приоритетов, бенчмарки и вовремя замеченные ошибки в направлении работы.

Переписаны почти все части: GPU-версия первой стадии выбора полинома, GPU-решето glas, ускоренные dup/purge и merge/replay, новая GPU-реализация блочного алгоритма Видемана, GPU-sqrt. Нетронутыми остались только cado-nfs.py, polyselect_ropt, makefb и dup1.

Цифры проекта

• Всего около 4 900 GPU-дней, примерно $400 тыс.
• Выбор полинома: 643 GPU-дня (аномально много из-за ошибок оператора).
• Решето: 3 813 GPU-дней.
• Линейная алгебра: 467 GPU-дней, около 7% потеряно на сбои и вытеснение более важными задачами.
• Получено 8,3 млрд линейных соотношений над GF(2).
• Расчёт шёл на единицах процентов мощности кластера, без предельной стоимости.

Что с реальными ключами

RSA-1024 по стандартному масштабированию GNFS требует лишь в 78 раз больше вычислений, чем RSA-260. Автор оценивает стоимость примерно в $30 млн за число и допускает ещё двукратное снижение после доработок. Гиперскейлеры и крупные AI-лаборатории теоретически способны на такое. Но 1024-битный RSA признан устаревшим ещё в 2013 году, а подозрения о возможностях спецслужб звучали с середины 2000-х.

RSA-2048, нынешний стандарт, остаётся примерно в миллиард раз сложнее RSA-1024 и работой не затронут. Изменились три вещи: цена, число потенциальных исполнителей (нужны GPU, а не специализированное железо) и то, что в оптимизации факторизации теперь могут участвовать не криптографы.

Что делать командам

Безопасникам стоит проверить, не осталось ли в инфраструктуре 1024-битных ключей и сертификатов, включая встраиваемые устройства и старые внутренние сервисы. Для них миграция давно просрочена. С 2048-битными ключами срочности нет, но этот результат полезно учитывать в моделях угроз для долгоживущих данных.

Для инженерных и научных групп вывод шире. Однонодовые вытесняемые задачи могут утилизировать фрагментированные остатки кластера. Автономные кодинг-агенты способны взять на себя сочетание узкой теории и GPU-оптимизации, на которое раньше требовалась команда узких специалистов на месяцы.