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

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

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

Если задаться вопросом, какое же наибольшее простое число^[1] известно человечеству — то ответом будет какое-то простое число Мерсенна. Числа Мерсенна имеют вид . Заметим, что простота числа влечёт простоту ; в противном случае для и число не будет простым в виду делимости на (как, впрочем, и на ).

Как следует из названия, целью проекта GIMPS является поиск новых простых чисел Мерсенна. Самое большое известное на данный момент простое число было найдено в рамках проекта GIMPS в августе 2008 года. Более того, одиннадцать предыдущих рекордов также были установлены участниками GIMPS. Причина кроется в наличии эффективного (детерминированного) критерия их простоты, носящего имя Люка-Лемера. Для поиска простых чисел Мерсенна сервер GIMPS раздаёт клиентам простые «экспоненты» для проверки числа на простоту тестом Люка-Лемера.

На сегодняшний день достоверно известны только первые 40 простых чисел Мерсенна. Также найдено семь больших простых числа Мерсенна, порядковые номера которых пока не установлены.^[2]

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

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

Кроме того, простые числа Мерсенна играют важную роль в некоторых проблемах теории чисел. Например, Евклид обнаружил, что если число простое, то число совершенно, т. е. равно сумме своих собственных делителей (примеры таких чисел: , , ), а Эйлер впоследствии доказал, что все чётные совершенные числа имеют указанный вид (вопрос о существовании нечётного совершенного числа открыт до сих пор).

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

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

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

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

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

Кроме денежного вознаграждения, имя открывателя навсегда будет записано в анналы математики.

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

Эвристические оценки показывают, что в интервале для p от 10 000 000 до 80 000 000 ждут своего открытия ещё два неизвестных простых числа Мерсенна. Подробную информацию об их возможном распределении, а также об ожидаемых трудозатратах на их нахождение можно получить на странице статистики проекта.^[5]

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

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

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

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

• Microsoft Windows 3.1/9x/NT/2000/XP; Vista поддерживается, но с оговорками. Также есть версия для 64-битных вариантов XP/Vista.
• Mac OS X 64-х и 32-х битные версии
• GNU/Linux (Существуют 32-битная и 64-битная версии.)
• FreeBSD
• OS/2

Примечания