Отличный Интернет-поиск Mersenne Prime - Great Internet Mersenne Prime Search

Не путать с GIMP .
Большой поиск в Интернете Мерсенн Прайм (GIMPS)
GIMPS logo 2020.png
Логотип GIMPS
Веб-сайт Mersenne .org Edit this at Wikidata

The Great Internet Mersenne Prime Search ( GIMPS ) - это совместный проект добровольцев, которые используют бесплатное программное обеспечение для поиска простых чисел Мерсенна .

GIMPS был основан в 1996 году Джорджем Вольтманом , который также написал клиент Prime95 и его порт для Linux MPrime. Скотт Куровски написал внутренний сервер PrimeNet для демонстрации программного обеспечения для распределенных вычислений от Entropia, компании, которую он основал в 1997 году. GIMPS зарегистрирован как Mersenne Research, Inc., где Куровски является исполнительным вице-президентом и директором совета директоров. GIMPS считается одним из первых крупномасштабных проектов распределенных вычислений через Интернет для исследовательских целей.

По состоянию на сентябрь 2021 года в рамках проекта было обнаружено в общей сложности семнадцать простых чисел Мерсенна , пятнадцать из которых были наибольшими известными простыми числами на момент их открытия. Наибольшее известное простое число по состоянию на июнь 2021 года составляет 2 82,589,933  - 1 (или для краткости 82,589,933 M ) и было обнаружено 7 декабря 2018 года Патриком Ларошем. 4 декабря 2020 года проект прошел важную веху после того, как все экспоненты ниже 100 миллионов были проверены хотя бы один раз.

Проект основан в первую очередь на тесте простоты Лукаса – Лемера, поскольку это алгоритм, который одновременно специализируется на проверке простых чисел Мерсенна и особенно эффективен на двоичных компьютерных архитектурах . Существует также фаза пробного деления , используемая для быстрого исключения многих чисел Мерсенна с небольшими множителями. Алгоритм Полларда p - 1 также используется для поиска гладких факторов. В 2017 году GIMPS принял тест на простоту Ферма в качестве альтернативы для проверки на простоту. В сентябре 2020 года GIMPS начал использовать доказательства PRP, которые вместе с очень надежной проверкой ошибок, разработанной Робертом Гербичем, обеспечивают полную уверенность в правильности результата теста и, таким образом, устраняют необходимость в двойных проверках.

История

Проект начался в начале января 1996 года с программы, работающей на компьютерах i386 . Название проекта было придумано Люком Уэлшем, одним из его первых исследователей и одним из первооткрывателей 29-го простого числа Мерсенна. В течение нескольких месяцев к нам присоединилось несколько десятков человек, а к концу первого года - более тысячи. Жоэль Арменго, участник, обнаружил первичность M 1,398,269 13 ноября 1996 года.

Положение дел

По состоянию на июль 2021 года GIMPS имеет устойчивую среднюю совокупную пропускную способность примерно 1,21  петафлопс (или пфлопс) . В ноябре 2012 года GIMPS поддерживал 95 терафлопс, что теоретически принесло виртуальному компьютеру GIMPS 330 место в рейтинге TOP500 самых мощных известных компьютерных систем в мире. Предыдущее место заняла HP Cluster Platform 3000 BL460c G7 от Hewlett-Packard . По результатам июля 2021 года в рейтинге TOP500 текущие номера GIMPS больше не будут входить в список.

Ранее это составляло примерно 50 терафлопс в начале 2010 года, 30 терафлопс в середине 2008 года, 20 терафлопс в середине 2006 года и 14 терафлопс в начале 2004 года.

Лицензия на программное обеспечение

Хотя исходный код программного обеспечения GIMPS является общедоступным, технически это не бесплатное программное обеспечение , поскольку оно имеет ограничение, согласно которому пользователи должны соблюдать условия распространения проекта. В частности, если программное обеспечение используется для обнаружения простого числа, содержащего не менее 100000000 десятичных цифр, пользователь выиграет только 50 000 долларов из приза в 150 000 долларов, предлагаемого Electronic Frontier Foundation .

Сторонние программы для тестирования чисел Мерсенна, такие как Mlucas и Glucas (для систем, отличных от x86), не имеют этого ограничения.

GIMPS также «оставляет за собой право вносить изменения в EULA без уведомления и с разумным ретроактивным . »

Найдены простые числа

Все простые числа Мерсенна имеют вид M p = 2 p - 1 , где p - само простое число. Наименьшее простое число Мерсенна в этой таблице - 2 1398269 - 1.

Первый столбец - это ранг простого числа Мерсенна в (упорядоченной) последовательности всех простых чисел Мерсенна; GIMPS нашел все известные простые числа Мерсенна, начиная с 35-го.

# Дата открытия Prime M p Количество цифр Процессор
35 год 13 ноября 1996 г. M 1398269 420 921 Pentium (90 МГц )
36 24 августа 1997 г. M 2976221 895 932 Pentium (100 МГц)
37 27 января 1998 г. M 3021377 909 526 Pentium (200 МГц)
38 1 июня 1999 г. M 6972593 2,098,960 Pentium (350 МГц)
39 14 ноября 2001 г. M 13466917 4 053 946 AMD T-Bird (800 МГц)
40 17 ноября 2003 г. M 20996011 6 320 430 Pentium (2 ГГц)
41 год 15 мая 2004 г. M 24036583 7 235 733 Pentium 4 (2,4 ГГц)
42 18 февраля 2005 г. M 25964951 7 816 230 Pentium 4 (2,4 ГГц)
43 год 15 декабря 2005 г. M 30402457 9 152 052 Pentium 4 (2 ГГц разогнан до 3 ГГц)
44 год 4 сентября 2006 г. M 32582657 9 808 358 Pentium 4 (3 ГГц)
45 6 сентября 2008 г. M 37156667 11 185 272 Intel Core 2 Duo (2,83 ГГц)
46 4 июня 2009 г. M 42643801 12 837 064 Intel Core 2 Duo (3 ГГц)
47 23 августа 2008 г. M 43112609 12 978 189 Процессор Intel Core 2 Duo E6600 (2,4 ГГц)
48 25 января 2013 г. M 57885161 17 425 170 Intel Core 2 Duo E8400 @ 3,00 ГГц
49 7 января 2016 г. M 74207281 22 338 618 Intel Core i7-4790
50 26 декабря 2017 г. M 77232917 23 249 425 Intel Core i5-6600
51 7 декабря 2018 г. M 82589933 24 862 048 Intel Core i5-4590T

^ † По состоянию на 3 октября 2021 г. 57 747 433 является наибольшим показателем, ниже которого все другие простые показатели были проверены дважды, поэтому не проверяется, существуют ли какие-либо неоткрытые простые числа Мерсенна между 47-м (M43112609) и 51-м (M82589933). на этом графике; поэтому рейтинг является предварительным. Кроме того, 104 815 069 является наибольшим показателем, ниже которого все остальные простые показатели были протестированы хотя бы один раз, поэтому были протестированы все числа Мерсенна ниже 51-го (M82589933).

^ ‡ Число M82589933состоит из 24862048 десятичных цифр. Чтобы наглядно представить размер этого числа, если бы его нужно было сохранить на диск, результирующий текстовый файл был бы длиной почти 25 мегабайт (большинство книг в текстовом формате занимают менее двух мегабайт). Стандартныймакеттекстового процессора(50 строк на страницу, 75 цифр в строке) потребует 6629 страниц для его отображения. Если распечатать его на стандартной односторонней бумаге для принтера, потребуется примерно 14пачекбумаги.

Всякий раз, когда серверу сообщается возможное простое число, оно сначала проверяется перед объявлением. Важность этого была проиллюстрирована в 2003 году, когда сообщалось, что ложное срабатывание могло быть 40-м простым числом Мерсенна, но проверка не удалась.

Официальная «дата открытия» простого числа - это дата, когда человек впервые заметил результат для простого числа, который может отличаться от даты, когда результат был впервые передан на сервер. Например, сообщение M 74207281 было отправлено на сервер 17 сентября 2015 г., но отчет не просматривался до 7 января 2016 г.

Смотрите также

использованная литература

внешние ссылки