GIMPS: нам нужны твои процессор и видеокарта

Приветствую всех любителей математики и больших простых чисел, а особенно — интересующихся, но ещё не погрузившихся в эту тему.

Пару недель назад было найдено очередное простое число Мерсенна — и я, пользуясь тем, что это событие подогрело интерес к проектам распределённым вычислений, хочу рассказать вам подробнее, что из себя представляет Great Internet Mersenne Prime Search. И, конечно же, по возможности, убедить присоединиться.

Итак, Великий Интернет-поиск Простых Чисел Мерсенна.

Это некоммерческий проект, запущенный аж в 1996 году Джорджем Уолтманом, математиком и программистом. Основной его целью является поиск простых чисел Мерсенна (их было найдено 18), хоть со временем и образовались несколько побочных активностей, связанных, например, с числами Ферма (2^{2^n}+1), Прота (k*2ⁿ + 1), Вагстаффа ((2ⁿ + 1) / 3) и так далее.

С технической точки зрения GIMPS представляет собой базу данных с информацией об экспонентах чисел Мерсенна и HTTP API, дающее возможность получить задание на определённую операцию с одной из этих экспонент — а затем, после его выполнения, вернуть результат.

Есть определённая последовательность действий, которой обычно придерживаются при проверке каждой экспоненты:

1. Trial Factoring (TF) — перебор делителей, то есть обычная проверка, не делится ли кандидат на все подряд простые числа до определённого размера в битах (каждый следующий бит, понятное дело, требует вдвое больше работы). Находит только очень небольшие делители, но отлично параллелится и поэтому на GPU показывает производительность на один-два порядка выше, чем CPU (посмотрите на адские цифры гигагерце-дней в бенчмарках).

2. Факторизация методом Полларда (P-1). В отличие от перебора, иногда находит здоровенные делители, но не даёт аналогичного выигрыша на GPU, и, кроме того, требует значительного объёма оперативной памяти.

3. Если после первых двух шагов предварительной факторизации не было найдено делителей, наступает время тяжёлой артиллерии — вероятностного теста простоты Миллера-Рабина (PRP). Это уже полноценная проверка на простоту. Она с абсолютной точностью определяет составные числа, и с очень высокой — простые. Иначе говоря, положительный результат PRP требует повторной проверки другими методами, а отрицательный (коих подавляющее большинство) — нет.

4. Сертификация PRP (CERT) с помощью Verifiable Delay Function — проверка результата теста на простоту, требующая менее 1% вычислений, чем сам PRP. Подтверждает, что присланный результат корректен и действительно вычислен, а не выдуман. Требует некоторого объёма дискового пространства на время проверки (от 3 до 12 ГБ) и предварительного скачивания proof-файла объёмом ~150 МБ (подробнее).

(Этот список неполон, но я решил не углубляться настолько. Просто знайте, что есть ещё другие, менее распространённые варианты — ECM, P+1, PRP Cofactor… в конце статьи я дам ссылку на огромный тред гимпсовского форума с максимально подробными описаниями.)

Пройдя все эти этапы, экспонента считается обработанной и проверенной. Разумеется, никто не запрещает сделать с ней ещё что-то — или даже с ещё не проверенной. Этот процесс называется «Manual assignment» и обычно используется энтузиастами, профиль работ которых не вписывается в основной фронт GIMPS — например, факторизация «далёких» или наоборот, небольших экспонент, перепроверка древних результатов, и так далее.

Думаю, пришло время перейти от сухой теории к гораздо более сочной практике. Чем в рамках активностей GIMPS можете заняться лично вы? Много чем, благо, выбор достаточно велик!

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

В зависимости от того, какое оборудование вы решите использовать, и на какой ОС — вам понадобится разное программное обеспечение:

• Prime95/Mprime — флагман GIMPS, основная рабочая лошадка, пригодная для всех видов тестов. Использует CPU, работает, кажется, на любой x86 ОС. Хорошо документирована, легко настраивается в качестве сервиса.

• GpuOwL/PRPLL — PRP и P-1 на GPU. Наиболее производительное ПО для проверки на простоту на видеокартах (вот, кстати, результаты бенчмарков). Часто обновляется. Требует отдельной интеграции с API GIMPS для автоматического получения заданий и отправки результатов, впрочем, это вопрос решаемый.

• Mfaktc (для NVIDIA GPU) и Mfakto (для AMD) — числодробилки для перебора делителей на GPU. Также требуют некоторых танцев для интеграции, но AutoPrimeNet из прошлого пункта помогает и здесь.

Существует возможность запустить всё вышеперечисленное не только локально, но и, например, в облаке — в том числе на Google Colab с их мощными Tesla T4, A100 и другими (правда, с недавних пор, к сожалению, только в платной версии — но если и другие облака!)

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

На этом закругляюсь и, поскольку в прошлый раз забыл, даю ссылку, по которой можно присоединиться к нашей GIMPS-команде, если вы ещё не.