GIMPS

GIMPS (Great Internet Mersenne Prime Search, «Великий интернет-поиск простых чисел Мерсенна») — это проект распределённых вычислений, целью которого является поиск простых чисел Мерсенна. Проект был основан в 1996 году программистом Джорджем Вольтманом и с тех пор координируется им совместно с математиком Скоттом Куровски. GIMPS использует добровольные вычислительные ресурсы тысяч участников по всему миру для выполнения математических расчётов, что позволяет находить крупнейшие известные простые числа.

История проекта

Идея использования распределённых вычислений для поиска простых чисел Мерсенна возникла в середине 1990-х годов, когда развитие персональных компьютеров и интернета сделало возможным объединение их мощностей. Джордж Вольтман, американский программист и математик, разработал программу Prime95, которая стала основой проекта. Первая версия программы была выпущена в 1996 году, и в том же году GIMPS начал свою работу.

Первое простое число Мерсенна, найденное в рамках проекта, — M\(_{1398269}\) (2\(^{1398269}\) — 1) — было обнаружено 13 ноября 1996 года. С тех пор GIMPS стал основным источником открытий новых простых чисел Мерсенна. На 2025 год проект нашёл 18 из 51 известных простых чисел Мерсенна, включая все числа, начиная с M\(_{6972593}\) (открытого в 1999 году). Последнее на данный момент открытие — M\(_{82589933}\) (2\(^{82589933}\) — 1) — было совершено 7 декабря 2018 года.

Принцип работы

GIMPS функционирует как проект распределённых вычислений. Участники (добровольцы) загружают и устанавливают на свои компьютеры клиентское программное обеспечение, обычно Prime95 для Windows или MPrime для Linux и macOS. Программа автоматически получает от сервера GIMPS задания — диапазоны чисел для проверки на простоту по критерию Люка — Лемера. После завершения вычислений результат отправляется на сервер, где он проверяется и, в случае успеха, включается в базу данных.

Процесс поиска включает несколько этапов:

1. Предварительное просеивание — отсеивание чисел, заведомо не являющихся простыми, с помощью малых делителей.
2. Тест Люка — Лемера — основной алгоритм проверки числа Мерсенна на простоту. Он эффективен для больших чисел, так как требует только \(O(p^2)\) операций, где \(p\) — показатель степени.
3. Верификация — найденное простое число проверяется независимо на другом компьютере для исключения ошибок.

Программное обеспечение

Основной программой проекта является Prime95, разработанная Джорджем Вольтманом. Она доступна для операционных систем Windows, Linux и macOS. Prime95 оптимизирована для работы с большими целыми числами и использует алгоритмы быстрого преобразования Фурье (FFT) для ускорения умножения. Программа может работать в фоновом режиме, используя неиспользуемые ресурсы процессора, что не мешает повседневной работе пользователя.

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

Математическая основа

GIMPS специализируется на поиске чисел Мерсенна — чисел вида \(M_p = 2^p — 1\), где \(p\) — простое число. Простые числа Мерсенна — это числа Мерсенна, которые сами являются простыми. Они названы в честь французского математика Марена Мерсенна (1588—1648), который изучал их свойства.

Для проверки простоты чисел Мерсенна используется тест Люка — Лемера, который является детерминированным и эффективным для этого класса чисел. Тест заключается в построении последовательности \(S_n\) по рекуррентной формуле: \[ S_1 = 4, \quad S_{k+1} = S_k^2 — 2 \mod M_p \] Число \(M_p\) является простым тогда и только тогда, когда \(S_{p-1} \equiv 0 \pmod{M_p}\).

Участники и сообщество

Проект GIMPS объединяет тысячи добровольцев из разных стран. Участники могут регистрироваться на официальном сайте, где ведётся статистика вклада каждого пользователя. За найденные простые числа Мерсенна присуждаются денежные премии, учреждённые Electronic Frontier Foundation (EFF). Например, за нахождение простого числа с более чем 10 миллионами десятичных цифр была выплачена премия в 100 000 долларов США (число M\(_{43112609}\), найденное в 2008 году). За число с более чем 100 миллионами цифр (M\(_{82589933}\)) премия составила 150 000 долларов США.

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

Результаты и достижения

На 2025 год GIMPS является автором 18 открытий простых чисел Мерсенна. Среди наиболее значимых:

• M\(_{6972593}\) (2 098 960 цифр) — найдено 1 июня 1999 года, первое простое число с более чем 2 миллионами цифр.
• M\(_{43112609}\) (12 978 189 цифр) — найдено 23 августа 2008 года, премия EFF в 100 000 долларов.
• M\(_{57885161}\) (17 425 170 цифр) — найдено 25 января 2013 года.
• M\(_{74207281}\) (22 338 618 цифр) — найдено 7 января 2016 года.
• M\(_{77232917}\) (23 249 425 цифр) — найдено 26 декабря 2017 года.
• M\(_{82589933}\) (24 862 048 цифр) — найдено 7 декабря 2018 года, последнее на данный момент открытие.

Все эти числа являются крупнейшими известными простыми числами на момент их открытия.

Критика и ограничения

Несмотря на успехи, GIMPS имеет ряд ограничений. Во-первых, проект ориентирован исключительно на числа Мерсенна, что сужает область поиска. Во-вторых, с ростом показателя степени \(p\) вычислительная сложность теста Люка — Лемера растёт квадратично, что делает поиск всё более трудоёмким. В-третьих, проект зависит от добровольных ресурсов, что ограничивает скорость вычислений. Некоторые критики отмечают, что GIMPS не вносит существенного вклада в теоретическую математику, так как простые числа Мерсенна не имеют прямого практического применения, однако они важны для тестирования алгоритмов и вычислительных систем.

Значение и влияние

GIMPS сыграл важную роль в популяризации распределённых вычислений. Проект продемонстрировал, что объединение ресурсов обычных пользователей может решать сложные научные задачи, конкурирующие с суперкомпьютерами. Кроме того, GIMPS способствовал развитию алгоритмов целочисленной арифметики и оптимизации программного обеспечения для многопроцессорных систем. Найденные простые числа Мерсенна используются в криптографии (например, в генераторах псевдослучайных чисел) и в тестах производительности вычислительной техники.

Источники

• Официальный сайт проекта GIMPS: mersenne.org
• Джордж Вольтман, «The Great Internet Mersenne Prime Search», 1996.
• Скотт Куровски, «Mersenne Prime Search: A Distributed Computing Project», 1997.
• Electronic Frontier Foundation, «Cooperative Computing Awards», 2008.
• Статья «Mersenne prime» в энциклопедии Wolfram MathWorld.
• Отчёты о находках простых чисел Мерсенна на сайте PrimeCurios.