Отличный интернет-поиск простых чисел Мерсенна
 Логотип | |
| Веб-сайт | Мерсенн |
|---|---|
Великий Интернет-поиск простых чисел Мерсенна ( GIMPS ) — это совместный проект добровольцев, которые используют бесплатно доступное программное обеспечение для поиска простых чисел Мерсенна .
GIMPS была основана в 1996 году Джорджем Вольтманом , который также написал клиент Prime95 и его порт MPrime для Linux. Скотт Куровски написал внутренний сервер PrimeNet для демонстрации добровольного компьютерного программного обеспечения для Entropia, компании, которую он основал в 1997 году. GIMPS зарегистрирована как Mersenne Research, Inc., а Куровски является исполнительным вице-президентом и директором совета директоров. GIMPS считается одним из первых крупномасштабных добровольных компьютерных проектов через Интернет для исследовательских целей. [1]
По состоянию на октябрь 2022 г. [update], the project has found a total of seventeen Mersenne primes, fifteen of which were the largest known prime number at their respective times of discovery. The largest known prime as of September 2022[ref] 2 82,589,933 M 82 589 933 ) и был обнаружен 7 декабря 2018 года Патриком Ларошем. − 1 (или сокращенно [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 г. [update]GIMPS имеет устойчивую среднюю совокупную пропускную способность примерно 4,71 петафлопс (или PFLOPS) . [21] В ноябре 2012 года GIMPS поддерживал производительность 95 терафлопс. [22] GIMPS теоретически заработав виртуальному компьютеру 330-е место среди ТОП-500 самых мощных известных компьютерных систем в мире. [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] и Глюкас [29] (для систем, отличных от x86), это ограничение отсутствует.
GIMPS также «оставляет за собой право изменять настоящее Лицензионное соглашение без предварительного уведомления и с разумной обратной силой . » [26]
Простые числа найдены
[ редактировать ]Все простые числа Мерсенна имеют вид M p = 2 п − 1 , где p само является простым числом. Наименьшее простое число Мерсенна в этой таблице равно 2. 1398269 − 1.
Первый столбец представляет собой ранг простого числа Мерсенна в (упорядоченной) последовательности всех простых чисел Мерсенна; [30] GIMPS нашел все известные простые числа Мерсенна, начиная с 35-го.
| # | Дата открытия | Прайм М п | Количество цифр | Процессор |
|---|---|---|---|---|
| 35 | 13 ноября 1996 г. | М 1398269 | 420,921 | Пентиум (90 МГц ) |
| 36 | 24 августа 1997 г. | М 2976221 | 895,932 | Пентиум (100 МГц) |
| 37 | 27 января 1998 г. | М 3021377 | 909,526 | Пентиум (200 МГц) |
| 38 | 1 июня 1999 г. | М 6972593 | 2,098,960 | Пентиум (350 МГц) |
| 39 | 14 ноября 2001 г. | М 13466917 | 4,053,946 | AMD T-Bird (800 МГц) |
| 40 | 17 ноября 2003 г. | М 20996011 | 6,320,430 | Пентиум (2 ГГц) |
| 41 | 15 мая 2004 г. | М 24036583 | 7,235,733 | Пентиум 4 (2,4 ГГц) |
| 42 | 18 февраля 2005 г. | М 25964951 | 7,816,230 | Пентиум 4 (2,4 ГГц) |
| 43 | 15 декабря 2005 г. | М 30402457 | 9,152,052 | Pentium 4 (2 ГГц с разгоном до 3 ГГц) |
| 44 | 4 сентября 2006 г. | М 32582657 | 9,808,358 | Пентиум 4 (3 ГГц) |
| 45 | 6 сентября 2008 г. | М 37156667 | 11,185,272 | Intel Core 2 Duo (2,83 ГГц) |
| 46 | 4 июня 2009 г. | М 42643801 | 12,837,064 | Intel Core 2 Duo (3 ГГц) |
| 47 | 23 августа 2008 г. | М 43112609 | 12,978,189 | Процессор Intel Core 2 Duo E6600 (2,4 ГГц) |
| 48 | 25 января 2013 г. | М 57885161 | 17,425,170 | Intel Core 2 Duo E8400 @ 3,00 ГГц |
| 49 [†] | 7 января 2016 г. | М 74207281 | 22,338,618 | Intel Core i7-4790 |
| 50 [†] | 26 декабря 2017 г. | М 77232917 | 23,249,425 | Intel Core i5-6600 |
| 51 [†] | 7 декабря 2018 г. | М 82589933 [‡] | 24,862,048 | Intel Core i5-4590T |
^ † По состоянию на 14 ноября 2023 г. [update], 65 723 341 — это наибольший показатель степени, ниже которого все остальные показатели простых чисел проверялись дважды, поэтому не проверяется, существуют ли какие-либо неоткрытые простые числа Мерсенна между 48-м (M 57885161 ) и 51-м (M 82589933 ) на этой диаграмме; поэтому рейтинг является предварительным. Кроме того, 114 055 847 — это наибольший показатель степени, ниже которого все остальные простые показатели проверялись хотя бы один раз, поэтому все числа Мерсенна ниже 51-го (M 82589933 ). были проверены [31]
^ ‡ Число М 82589933 имеет 24 862 048 десятичных цифр. Чтобы представить себе размер этого числа, если его сохранить на диск, полученный текстовый файл будет иметь длину почти 25 мегабайт (большинство книг в текстовом формате имеют размер менее двух мегабайт). Стандартный макет текстового процессора (50 строк на странице, 75 цифр в строке) потребует для его отображения 6629 страниц. Если бы его распечатали на стандартной односторонней бумаге для принтера, потребовалось бы примерно 14 стопок (14 × 500 = 7000 листов) бумаги.
Всякий раз, когда на сервер сообщается о возможном простом числе, перед объявлением оно сначала проверяется (путем одного или нескольких независимых тестов на разных машинах). Важность этого была продемонстрирована в 2003 году, когда на сервер было отправлено сообщение о ложном положительном результате как простое число Мерсенна, но проверка не удалась. [32]
Официальной «датой открытия» простого числа является дата, когда человек впервые заметил результат для простого числа, которая может отличаться от даты, когда результат был впервые сообщен на сервер. Например, сообщение о M 74207281 было отправлено на сервер 17 сентября 2015 г., но сообщение просматривалось до 7 января 2016 г. [33]
См. также
[ редактировать ]- Открытая инфраструктура Беркли для сетевых вычислений
- Список волонтерских компьютерных проектов
- ПраймГрид
Ссылки
[ редактировать ]- ^ «Волонтёрские вычисления» . БОИНК. Архивировано из оригинала 18 декабря 2021 года . Проверено 25 декабря 2021 г.
- ^ «Проект GIMPS обнаружил самое большое известное простое число: 2». 82,589,933 -1» . Mersenne Research, Inc. 21 декабря 2018 г. Дата обращения 21 декабря 2018 г.
- ^ «Отчет об основных этапах работы GIMPS» . Мерсенн.орг . Мерсенн Рисерч, Инк . Проверено 5 декабря 2020 г.
- ^ Что такое простые числа Мерсенна? Чем они полезны? - Домашняя страница GIMPS
- ^ «GIMPS — Математика — PrimeNet» .
- ^ «mersenneforum.org — Посмотреть отдельное сообщение — Получение надежного LL на ненадежном оборудовании» . mersenneforum.org . Проверено 5 октября 2022 г.
- ^ «mersenneforum.org — Посмотреть отдельное сообщение — Получение надежного LL на ненадежном оборудовании» . mersenneforum.org . Проверено 5 октября 2022 г.
- ^ «Объявления» . GIMPS, великий интернет-поиск простых чисел Мерсенна. Архивировано из оригинала 14 августа 2021 г. Проверено 1 сентября 2021 г.
- ^ "Что нового" . Проверено 1 сентября 2021 г.
- ^ «Прайм95 v30.3» . Проверено 1 сентября 2021 г.
- ^ Уолтман, Джордж (16 июня 2020 г.). «Следующее большое развитие GIMPS» . Форум ГИМПС . Проверено 20 мая 2022 г.
- ^ Уолтман, Джордж (08 апреля 2021 г.). «Первого раза ЛЛ больше нет» . Проверено 19 мая 2022 г.
- ^ «Прогресс PrimeNet ECM» . Проверено 20 мая 2022 г.
- ^ Информационный бюллетень Мерсенна, выпуск № 9. Проверено 2 октября 2011 г. Архивировано 6 февраля 2012 г. в Wayback Machine.
- ^ "mersenneforum.org - Посмотреть отдельное сообщение - Вечеринка началась! GIMPS исполняется 10 лет!!!" . www.mersenneforum.org . Проверено 22 декабря 2018 г.
- ^ Уолтман, Джордж (24 февраля 1996 г.). «Информационный бюллетень Мерсенна, выпуск № 1» (txt) . Отличный интернет-поиск простых чисел Мерсенна (GIMPS) . Проверено 16 июня 2009 г.
- ↑ Перейти обратно: Перейти обратно: а б Уолтман, Джордж (15 января 1997 г.). «Информационный бюллетень Мерсенна, выпуск № 9» (txt) . ГИМПЫ . Проверено 16 июня 2009 г.
- ^ Информационный бюллетень Мерсенна, выпуск № 9 . Проверено 25 августа 2009 г.
- ^ Уолтман, Джордж (12 апреля 1996 г.). «Информационный бюллетень Мерсенна, выпуск № 3» (txt) . ГИМПЫ . Проверено 16 июня 2009 г.
- ^ Уолтман, Джордж (23 ноября 1996 г.). «Информационный бюллетень Мерсенна, выпуск № 8» (txt) . ГИМПЫ . Проверено 16 июня 2009 г.
- ^ Сводка деятельности PrimeNet , GIMPS , получено 19 июля 2022 г.
- ^ Сводка активности PrimeNet , GIMPS , получено 5 апреля 2012 г.
- ^ «ТОП500 — ноябрь 2012» . Архивировано из оригинала 5 октября 2018 года . Проверено 22 ноября 2012 г.
- ^ ТОП500 за ноябрь 2012 г.; HP BL460c с производительностью 95,1 терафлопс/с (R макс.). «ТОП500 – 329 место» . Проверено 22 ноября 2012 г.
- ^ «Исходный код программного обеспечения» . Мерсенн Рисерч, Инк . Проверено 16 марта 2013 г.
- ↑ Перейти обратно: Перейти обратно: а б с GIMPS Legalese , GIMPS , получено 19 сентября 2011 г.
- ^ Награды EFF Cooperative Computing Awards , Electronic Frontier Foundation, 29 февраля 2008 г. , получено 19 сентября 2011 г.
- ^ «Млукас README» .
- ^ «Без названия» .
- ^ «Список GIMPS известных простых чисел Мерсенна» . Мерсенн Рисерч, Инк . Проверено 3 января 2018 г.
- ^ «Вехи GIMPS» . Мерсенн Рисерч, Инк . Проверено 30 ноября 2020 г.
- ^ «М40, что пошло не так? - Страница 11 - mersenneforum.org» . mersenneforum.org . Проверено 22 декабря 2018 г.
- ^ «Проект GIMPS обнаружил самое большое известное простое число» . 19 января 2016 г.