Great Internet Mersenne Prime Search ( GIMPS ) — это совместный проект добровольцев, которые используют свободно распространяемое программное обеспечение для поиска простых чисел Мерсенна .
GIMPS был основан в 1996 году Джорджем Вольтманом , который также написал клиент Prime95 и его порт для Linux MPrime. Скотт Куровски написал серверную часть PrimeNet для демонстрации программного обеспечения для добровольных вычислений от Entropia, компании, которую он основал в 1997 году. GIMPS зарегистрирован как Mersenne Research, Inc., а Куровски является исполнительным вице-президентом и членом совета директоров. GIMPS считается одним из первых крупномасштабных проектов по добровольным вычислениям через Интернет в исследовательских целях. [1]
По состоянию на октябрь 2022 года [обновлять]проект обнаружил в общей сложности семнадцать простых чисел Мерсенна, пятнадцать из которых были крупнейшими известными простыми числами на момент их открытия. Наибольшее известное простое число по состоянию на сентябрь 2022 года [ссылка]составляет 2 82 589 933 − 1 (или M 82 589 933 для краткости) и было обнаружено 7 декабря 2018 года Патриком Ларошем. [2] 4 декабря 2020 года проект преодолел важный рубеж, после того как все показатели степени ниже 100 миллионов были проверены хотя бы один раз. [3]
С момента своего создания и до 2018 года проект в основном полагался на тест простоты Лукаса-Лемера [4], поскольку это алгоритм , который одновременно специализирован для проверки простых чисел Мерсенна и особенно эффективен на двоичных компьютерных архитектурах . Перед применением его к заданному числу Мерсенна была фаза пробного деления , используемая для быстрого исключения многих чисел Мерсенна с малыми множителями. Алгоритм Полларда p − 1 также используется для поиска гладких множителей.
В 2018 году GIMPS принял тест Ферма на простоту с базисом a=3 [5] [6] в качестве альтернативного варианта для проверки простоты, [7] сохранив тест Люка-Лемера в качестве двойной проверки чисел Мерсенна, определенных как вероятные простые числа тестом Ферма. [8] (Хотя тест Люка-Лемера является детерминированным, а тест Ферма — только вероятностным, вероятность того, что тест Ферма обнаружит псевдопростое число Ферма , которое не является простым, значительно ниже, чем частота ошибок теста Люка-Лемера из-за ошибок компьютерного оборудования . [9] )
В сентябре 2020 года [10] [11] [12] GIMPS начал поддерживать доказательства простоты , основанные на проверяемых функциях задержки. [13] Файлы доказательств генерируются во время выполнения теста Ферма на простоту. Эти доказательства вместе с алгоритмом проверки ошибок, разработанным Робертом Гербицем, обеспечивают полную уверенность в правильности результата теста и устраняют необходимость в двойных проверках. Первые тесты Лукаса-Лемера были объявлены устаревшими в апреле 2021 года. [14]
GIMPS также имеет подпроекты по факторизации известных составных чисел Мерсенна и Ферма . [15]
Проект начался в начале января 1996 года [16] [17] с программы, работавшей на компьютерах i386 . [18] [19] Название проекта было придумано Люком Уэлшем, одним из его ранних исследователей и соавтором открытия 29-го простого числа Мерсенна. [20] В течение нескольких месяцев к проекту присоединилось несколько десятков человек, а к концу первого года их число превысило тысячу. [19] [21] Джоэл Арменго, участник, открыл простоту числа M 1 398 269 13 ноября 1996 года. [22] С тех пор GIMPS в среднем открывал новое простое число Мерсенна каждые 1–2 года. Однако с 2018 года не было обнаружено ни одного нового простого числа Мерсенна, что составляет самый длительный период без новых открытий с начала проекта (более 5 лет по состоянию на 2024 год).
По состоянию на июль 2022 года [обновлять]GIMPS имеет устойчивую среднюю совокупную пропускную способность приблизительно 4,71 петафлопс (или PFLOPS) . [23] В ноябре 2012 года GIMPS поддерживал 95 TFLOPS, [24] теоретически зарабатывая виртуальному компьютеру GIMPS 330-е место среди TOP500 самых мощных известных компьютерных систем в мире. [25] Предыдущее место тогда занимала «HP Cluster Platform 3000 BL460c G7» компании Hewlett-Packard . [26] По результатам TOP500 июля 2021 года текущие показатели GIMPS больше не будут попадать в список.
Ранее этот показатель составлял приблизительно 50 TFLOPS в начале 2010 года, 30 TFLOPS в середине 2008 года, 20 TFLOPS в середине 2006 года и 14 TFLOPS в начале 2004 года.
Хотя исходный код программного обеспечения GIMPS находится в открытом доступе, [27] технически это не свободное программное обеспечение , поскольку у него есть ограничение, согласно которому пользователи должны соблюдать условия распространения проекта. [28] В частности, если программное обеспечение используется для обнаружения простого числа с не менее чем 100 000 000 десятичных цифр, пользователь выиграет только 50 000 долларов из приза в 150 000 долларов, предлагаемого Electronic Frontier Foundation . С другой стороны, он выиграет 3 000 долларов, если обнаружит меньшее простое число, не подпадающее под приз. [28] [29]
Сторонние программы для проверки чисел Мерсенна, такие как Mlucas [30] и Glucas [31] (для систем, отличных от x86), не имеют этого ограничения.
GIMPS также «оставляет за собой право изменять настоящее лицензионное соглашение без предварительного уведомления и с разумным ретроспективным эффектом » . [28]
Все простые числа Мерсенна имеют вид M p = 2 p − 1 , где p — само простое число. Наименьшее простое число Мерсенна в этой таблице — 2 1398269 − 1.
Первый столбец — это ранг простого числа Мерсенна в (упорядоченной) последовательности всех простых чисел Мерсенна; [32] GIMPS нашел все известные простые числа Мерсенна, начиная с 35-го.
^ † По состоянию на 14 ноября 2023 года [обновлять]65 723 341 является наибольшим показателем, ниже которого все остальные простые показатели были проверены дважды, поэтому не проверено, существуют ли какие-либо неоткрытые простые числа Мерсенна между 48-м (M 57885161 ) и 51-м (M 82589933 ) на этой диаграмме; поэтому рейтинг является предварительным. Кроме того, 114 055 847 является наибольшим показателем, ниже которого все остальные простые показатели были проверены по крайней мере один раз, поэтому все числа Мерсенна ниже 51-го (M 82589933 ) были проверены. [33]
^ ‡ Число M 82589933 имеет 24 862 048 десятичных цифр. Чтобы помочь визуализировать размер этого числа, если бы оно было сохранено на диске, полученный текстовый файл был бы длиной около 25 мегабайт (большинство книг в формате обычного текста имеют размер менее двух мегабайт). Стандартный макет текстового процессора (50 строк на странице, 75 цифр в строке) потребовал бы 6629 страниц для его отображения. Если бы кто-то распечатал его на стандартной бумаге для принтера, с одной стороны, потребовалось бы примерно 14 пачек (14 × 500 = 7000 листов) бумаги.
Всякий раз, когда возможное простое число сообщается на сервер, оно сначала проверяется (одним или несколькими независимыми тестами на разных машинах) перед тем, как быть объявленным. Важность этого была проиллюстрирована в 2003 году, когда на сервер было сообщено ложное положительное число как простое число Мерсенна, но проверка не удалась. [34]
Официальная «дата открытия» простого числа — это дата, когда человек впервые заметил результат для простого числа, которая может отличаться от даты, когда результат был впервые сообщен серверу. Например, M 74207281 был сообщен серверу 17 сентября 2015 года, но сообщение было проигнорировано до 7 января 2016 года. [35]