GIMPS

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

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

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

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

Если задаться вопросом, какое же наибольшее простое число^[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_{43112609} = 2^{43112609} - 1$ было найдено в рамках проекта GIMPS в августе 2008 года. Более того, одиннадцать предыдущих рекордов также были установлены участниками GIMPS. Причина кроется в наличии эффективного (детерминированного) критерия их простоты, носящего имя Люка-Лемера. Для поиска простых чисел Мерсенна сервер GIMPS раздаёт клиентам простые «экспоненты» $p$ для проверки числа $M_p$ на простоту тестом Люка-Лемера.

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

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

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

Кроме того, простые числа Мерсенна играют важную роль в некоторых проблемах теории чисел. Например, Евклид обнаружил, что если число $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 выиграла^[3] денежный приз в 100 000 долларов США за нахождение простого числа из более чем 10 миллионов десятичных цифр и намеревается выиграть аналогичные призы в 150 000 и 250 000 долларов США, обещанные^[4] Electronic Frontier Foundation за нахождение простых чисел соответственно из более чем 100 и 1000 миллионов десятичных цифр. Из суммы этого приза планируется сделать выплаты всем «открывателям» предыдущих простых чисел Мерсенна, авторам программного обеспечения и авторам новых, более эффективных алгоритмов поиска (если такие алгоритмы будут найдены).

Найденный в августе 2008 года рекордсмен $M_{43112609} = 2^{43112609} - 1$ содержит 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

Примечания

1. ↑ The Largest Known Primes (англ.)
2. ↑ Table of Known Mersenne Primes (англ.)
3. ↑ Record 12-Million-Digit Prime Number Nets $100,000 Prize (англ.)
4. ↑ EFF Cooperative Computing Awards (англ.)
5. ↑ PrimeNet Activity Summary (англ.)
6. ↑ Download GIMPS client (англ.)

Ссылки

• Официальный сайт проекта GIMPS
• Сайт о распределенных вычислениях в интернете
• Сайт команды, представляющей на проекте Украину