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