GIMPS

GIMPS (Great Internet Mersenne Prime Search) — широкомасштабный проект добровольных вычислений по поиску простых чисел Мерсенна.

GIMPS
Prime95, запущенная в Wine.
Платформа	своя
Объём загружаемого ПО	4 МБ
Объём загружаемых данных задания	<1 КБ
Объём отправляемых данных задания	<1 КБ
Объём места на диске	27 МБ
Используемый объём памяти	2,5 МБ (TF), 45 МБ (PM1-1), >350 МБ (PM1-2), 60 МБ (LL)
Графический интерфейс	да (только в Windows и Mac OS X)
Среднее время расчёта задания	20 мин. — 1 день (TF), 5 дней (PM1), >2 мес. (LL)
Deadline	нет
Возможность использования GPU	да

Логотип GIMPS

Цели и методы проекта

Определение того, является ли данное число простым, в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, предложенный (и строго обоснованный теоретически) детерминированный алгоритм практически непригоден, в виду его большой, хотя и полиномиальной, сложности. Поэтому в криптографии с открытым ключом, где используются простые числа порядка $10^{300}$, простоту по-прежнему определяют с помощью эффективных вероятностных тестов, таких как тест Миллера — Рабина. Если практика довольствуется числами, являющимися простыми с вероятностью близкой к $1$, то теория такие числа не приемлет: если про число утверждается, что оно простое, это должно быть строго доказано. Эта разница подчёркивается в разделении алгоритмов на вероятностные и детерминированные.

Если задаться вопросом, какое же наибольшее простое число известно человечеству — то ответом будет какое-то простое число Мерсенна. Числа Мерсенна имеют вид $M_{p}=2^{p}-1$. Заметим, что простота числа $2^{p}-1$ влечёт простоту $p$; в противном случае $p=xy$ для $x,y>1$ и число $2^{p}-1=2^{xy}-1$ не будет простым в виду делимости на $2^{x}-1$ (как, впрочем, и на $2^{y}-1$).

Как следует из названия, целью проекта GIMPS является поиск новых простых чисел Мерсенна. Самое большое известное на данный момент простое число $M_{82589933}=2^{82589933}-1$ было найдено в рамках проекта GIMPS 7 декабря 2018 года и состоит из 24 862 048 десятичных цифр. Более того, 15 предыдущих рекордов также были установлены участниками GIMPS. Причина кроется в наличии эффективного (детерминированного) критерия их простоты, носящего имя Люка — Лемера. Для поиска простых чисел Мерсенна сервер GIMPS раздаёт клиентам простые «экспоненты» $p$ для проверки числа $M_{p}$ на простоту тестом Люка — Лемера.

На начало 2023 года известно 51 простое число Мерсенна, при этом достоверно известны порядковые номера первых 48 из них. Порядковые номера трех наибольших известных простых чисел Мерсенна пока достоверно не установлены (между ними могут оказаться другие, ещё не открытые простые числа Мерсенна).

Практическая значимость

Простые числа Мерсенна стабильно удерживают рекорд как самые большие известные простые числа.

Кроме того, простые числа Мерсенна играют важную роль в некоторых проблемах теории чисел. Например, Евклид обнаружил, что если число $M_{p}=2^{p}-1$ простое, то число $M_{p}(M_{p}+1)/2=2^{p-1}(2^{p}-1)$ совершенно, то есть равно сумме своих собственных делителей (примеры таких чисел: 6=1+2+3, 28=1+2+4+7+14, 496=1+2+4+8+16+31+62+124+248, а Эйлер впоследствии доказал, что все чётные совершенные числа имеют указанный вид (вопрос о существовании нечётного совершенного числа открыт до сих пор).

Остаётся открытым вопрос о бесконечности количества простых чисел Мерсенна и об их асимптотике. Найденные простые числа Мерсенна могут служить отправной точкой для выдвижения и проверки гипотез о поведении простых чисел Мерсенна.

На практике простые числа Мерсенна применяются для построения генераторов псевдо-случайных чисел с большими периодами (см. Вихрь Мерсенна).

Денежные призы

GIMPS выиграла денежный приз в 100 000 долларов США за нахождение простого числа из более чем 10 миллионов десятичных цифр и намеревается выиграть аналогичные призы в 150 000 и 250 000 долларов США, обещанные Electronic Frontier Foundation за нахождение простых чисел соответственно из более чем 100 миллионов и 1 миллиарда десятичных цифр. Из суммы этого приза планируется сделать выплаты всем «открывателям» предыдущих простых чисел Мерсенна, авторам программного обеспечения и авторам новых, более эффективных алгоритмов поиска (если такие алгоритмы будут найдены).

Найденное в августе 2008 года число $M_{43112609}=2^{43112609}-1$ содержит 12 978 189 десятичных цифр это позволило GIMPS получить премию в 100 000 долларов США. Однако, чтобы получить следующую премию в 150 000 долларов США, придётся проверять на простоту числа из более чем 100 миллионов десятичных цифр, каждое из которых при текущем развитии вычислительной и алгоритмической техники потребует более трёх лет.

Соревновательный эффект

Ежедневно проект GIMPS получает результаты вычислений сотен участников. По каждому из них проект ведёт статистику, публикует и регулярно обновляет рейтинги производительности и результативности. Для усиления соревновательного эффекта в проекте реализована возможность объединения участников в команды. В этом случае результаты участника идут в зачёт не только ему, но и его команде. Как и для отдельных участников, проект ведёт и обновляет рейтинги команд.

Команды обычно формируются по местоположению участников (страна или город), по принадлежности к какой-либо организации (учебное заведение или компания) или просто из желания поддержать то или иное интернет-сообщество.

Всего в проекте участвует более 1000 команд. Абсолютное большинство из них небольшие, состоящие из одного или нескольких участников, многие давно перестали быть активными. Наиболее крупные команды включают в себя десятки/сотни участников, причём нередко обладателей больших вычислительных мощностей: от нескольких личных компьютеров до целого парка компьютерной техники «подшефной» компании или университета.

Нередко за каждую строчку в командных рейтингах разыгрывается нешуточная борьба. Некоторые команды целенаправленно координируют действия своих участников, чтобы совершить прорыв в намеченном виде вычислений и максимально быстро подняться на более высокие позиции. В целом же командный ТОП-10 рейтинга относительно стабилен, сюрпризы преподносят в основном новые участники, неожиданно вступающие в игру за ту или иную команду. Именно поэтому команды всегда рады новоприбывающим участникам, а старожилы стараются по возможности помогать им с настройками оборудования и ПО, консультировать по выбору наиболее интересных видов вычислений.

Вероятность успеха

Эвристические оценки показывают, что «экспоненты» $p$ каждого последующего простого числа Мерсенна $M_{p}=2^{p}-1$ "в среднем" в 1,47576 раза больше предыдущего, таким образом существуют ещё три неизвестных простых числа Мерсенна, которые состоят менее чем из 100 миллионов десятичных цифр, а ближайшее из них может состоять примерно из 36 миллионов десятичных цифр. Подробную информацию об возможном распределении простых числа Мерсенна, а также об ожидаемых трудозатратах на их нахождение можно получить на странице статистики проекта.

Тестирование аппаратного обеспечения

Клиентская программа GIMPS проводит интенсивные вычисления, постоянно следя за их точностью. Поэтому многие рассматривают её как прекрасный инструмент для тестирования стабильности работы аппаратной части компьютера. Пиковые нагрузки и жёсткий контроль позволяют легко выявлять проблемы с памятью, кэшем, шиной данных, разгоном и перегревом процессора и т. п. Для облегчения процедуры тестирования клиент GIMPS предоставляет возможность работы в режиме «stress testing», когда вычисления проводятся для известных простых чисел Мерсенна и результаты вычислений сверяются с ожидаемыми.

Поддерживаемые операционные системы

Клиентская часть ПО проекта GIMPS доступна для следующих операционных систем:

• Microsoft Windows 7/Vista/XP/2008/2003/2000/NT/Me/98/95. Также есть версия для 64-битных вариантов Windows 7/Vista/XP/2008.
• Mac OS X
• GNU/Linux (64-битная и 32-битная версии)
• FreeBSD (64-битная и 32-битная версии)

Ссылки

• Официальный сайт GIMPS (англ.)
• Рейтинг участников в проекте GIMPS (англ.)
• Рейтинг команд в проекте GIMPS (англ.)
• Официальный форум GIMPS (англ.)
• Инструменты и расширенная статистика GIMPS (англ.)