Великий Интернет Поиск простого числа Мерсенна
Волонтерский проект по использованию программного обеспечения для поиска простых чисел Мерсенна
Отличный интернет-поиск простых чисел Мерсенна (GIMPS)
Логотип
Веб-сайтmersenne.org

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

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

По состоянию на октябрь 2024 года [обновлять]проект обнаружил в общей сложности восемнадцать простых чисел Мерсенна, шестнадцать из которых были крупнейшими известными простыми числами на момент их открытия. Наибольшее известное простое число по состоянию на октябрь 2024 года [ссылка]составляет 2 136 279 841  − 1 (или M 136 279 841 для краткости) и было обнаружено 12 октября 2024 года Люком Дюрантом. [2] [3] 4 декабря 2020 года проект преодолел важный рубеж, после того как все показатели степени ниже 100 миллионов были проверены хотя бы один раз. [4]

С момента своего создания и до 2018 года проект в основном полагался на тест простоты Лукаса-Лемера [5], поскольку это алгоритм , который одновременно специализирован для проверки простых чисел Мерсенна и особенно эффективен на двоичных компьютерных архитектурах . Перед применением его к заданному числу Мерсенна была фаза пробного деления , используемая для быстрого исключения многих чисел Мерсенна с малыми множителями. Алгоритм Полларда p − 1 также используется для поиска гладких множителей.

В 2018 году GIMPS принял тест Ферма на простоту с базисом a=3 [6] [7] в качестве альтернативного варианта для проверки простоты, [8] сохранив тест Люка-Лемера в качестве двойной проверки чисел Мерсенна, определенных как вероятные простые числа тестом Ферма. [9] (Хотя тест Люка-Лемера является детерминированным, а тест Ферма — только вероятностным, вероятность того, что тест Ферма обнаружит псевдопростое число Ферма , которое не является простым, значительно ниже, чем частота ошибок теста Люка-Лемера из-за ошибок компьютерного оборудования . [10] )

В сентябре 2020 года [11] [12] [13] GIMPS начал поддерживать доказательства простоты , основанные на проверяемых функциях задержки. [14] Файлы доказательств генерируются во время выполнения теста Ферма на простоту. Эти доказательства вместе с алгоритмом проверки ошибок, разработанным Робертом Гербицем, обеспечивают полную уверенность в правильности результата теста и устраняют необходимость в двойных проверках. Первые тесты Лукаса-Лемера были объявлены устаревшими в апреле 2021 года. [15]

GIMPS также имеет подпроекты по факторизации известных составных чисел Мерсенна и Ферма . [16]

История

Проект начался в начале января 1996 года [17] [18] с программы, работавшей на компьютерах i386 . [19] [20] Название проекта было придумано Люком Уэлшем, одним из его ранних исследователей и соавтором открытия 29-го простого числа Мерсенна. [21] В течение нескольких месяцев к проекту присоединилось несколько десятков человек, а к концу первого года их число превысило тысячу. [20] [22] Джоэл Арменго, участник, открыл простоту числа M 1 398 269 13 ноября 1996 года. [23] С тех пор GIMPS обнаруживает новое простое число Мерсенна в среднем каждые 1-2 года. Однако на поиск последнего наибольшего простого числа, найденного в октябре 2024 года, ушло почти шесть лет.

Статус

По состоянию на июль 2022 года [обновлять]GIMPS имеет устойчивую среднюю совокупную пропускную способность приблизительно 4,71  петафлопс (или PFLOPS) . [24] В ноябре 2012 года GIMPS поддерживал 95 TFLOPS, [25] теоретически зарабатывая виртуальному компьютеру GIMPS 330-е место среди TOP500 самых мощных известных компьютерных систем в мире. [26] Предыдущее место тогда занимала «HP Cluster Platform 3000 BL460c G7» компании Hewlett-Packard . [27] По результатам TOP500 июля 2021 года текущие показатели GIMPS больше не будут попадать в список.

Ранее этот показатель составлял приблизительно 50 TFLOPS в начале 2010 года, 30 TFLOPS в середине 2008 года, 20 TFLOPS в середине 2006 года и 14 TFLOPS в начале 2004 года.

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

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

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

GIMPS также «оставляет за собой право изменять настоящее лицензионное соглашение без предварительного уведомления и с разумным ретроспективным эффектом » . [29]

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

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

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

#Дата открытияПростое число M pКоличество цифрПроцессор
3513 ноября 1996 г.М 1398269420,921Pentium (90 МГц )
3624 августа 1997 г.М 2976221895,932Пентиум (100 МГц)
3727 января 1998 г.М 3021377909,526Пентиум (200 МГц)
381 июня 1999 г.М 69725932,098,960Пентиум (350 МГц)
3914 ноября 2001 г.М 134669174,053,946AMD T-Bird (800 МГц)
4017 ноября 2003 г.М 209960116,320,430Пентиум (2 ГГц)
4115 мая 2004 г.М 240365837,235,733Пентиум 4 (2,4 ГГц)
4218 февраля 2005 г.М 259649517,816,230Пентиум 4 (2,4 ГГц)
4315 декабря 2005 г.М 304024579,152,052Pentium 4 (2 ГГц, разогнан до 3 ГГц)
444 сентября 2006 г.М 325826579,808,358Пентиум 4 (3 ГГц)
456 сентября 2008 г.М 3715666711,185,272Intel Core 2 Duo (2,83 ГГц)
464 июня 2009 г.М 4264380112,837,064Intel Core 2 Duo (3 ГГц)
4723 августа 2008 г.М 4311260912,978,189Процессор Intel Core 2 Duo E6600 (2,4 ГГц)
4825 января 2013 г.М 5788516117,425,170Intel Core 2 Duo E8400 @ 3.00 ГГц
49 [†]7 января 2016 г.М 7420728122,338,618Intel Core i7-4790
50 [†]26 декабря 2017 г.М 7723291723,249,425Intel Core i5-6600
51 [†]7 декабря 2018 г.М 8258993324,862,048Intel Core i5-4590T
52 [†]21 октября 2024 г.М 136279841 [‡]41,024,320Nvidia A100

^ † По состоянию на 14 ноября 2023 года [обновлять]65 723 341 является наибольшим показателем, ниже которого все остальные простые показатели были проверены дважды, поэтому не проверено, существуют ли какие-либо неоткрытые простые числа Мерсенна между 48-м (M 57885161 ) и 51-м (M 82589933 ) на этой диаграмме; поэтому рейтинг является предварительным. Кроме того, 114 055 847 является наибольшим показателем, ниже которого все остальные простые показатели были проверены по крайней мере один раз, поэтому все числа Мерсенна ниже 51-го (M 82589933 ) были проверены. [34]

^ ‡ Число M 136279841 имеет 41 024 320 десятичных цифр. Чтобы помочь визуализировать размер этого числа, если бы оно было сохранено на диске, полученный текстовый файл был бы длиной около 42 мегабайт (большинство книг в формате обычного текста имеют размер менее двух мегабайт). Стандартный макет текстового процессора (50 строк на странице, 75 цифр в строке) потребовал бы 10 940 страниц для его отображения. Если бы кто-то распечатал его на стандартной бумаге для принтера, с одной стороны, потребовалось бы примерно 22 стопки (22 × 500 = 11 000 листов) бумаги.

Всякий раз, когда возможное простое число сообщается на сервер, оно сначала проверяется (одним или несколькими независимыми тестами на разных машинах) перед тем, как быть объявленным. Важность этого была проиллюстрирована в 2003 году, когда ложное срабатывание было сообщено на сервер как простое число Мерсенна, но проверка не удалась. [35]

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

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

Ссылки

  1. ^ "Volunteer computing". BOINC. Архивировано из оригинала 18 декабря 2021 г. Получено 25 декабря 2021 г.
  2. ^ "GIMPS обнаруживает самое большое известное простое число: 2136,279,841 − 1". Mersenne Research, Inc. 21 октября 2024 г. Получено 21 октября 2024 г.
  3. ^ "Проект GIMPS обнаружил самое большое известное простое число: 282,589,933-1". Mersenne Research, Inc. 21 декабря 2018 г. Получено 21 декабря 2018 г.
  4. ^ "GIMPS Milestones Report". Mersenne.org . Mersenne Research, Inc . Получено 5 декабря 2020 г. .
  5. ^ Что такое простые числа Мерсенна? Чем они полезны? - Домашняя страница GIMPS
  6. ^ a=2 не сработает, поскольку все числа Мерсенна являются 2-псевдопростыми.
  7. ^ https://www.mersenneforum.org/node/22795.
  8. ^ "GIMPS - Математика - PrimeNet".
  9. ^ "mersenneforum.org - Просмотреть отдельную запись - Получение надежного LL из ненадежного оборудования". mersenneforum.org . Получено 2022-10-05 .
  10. ^ "mersenneforum.org - Просмотреть отдельную запись - Получение надежного LL из ненадежного оборудования". mersenneforum.org . Получено 2022-10-05 .
  11. ^ "Объявления". GIMPS, Великий интернет-поиск простых чисел Мерсенна. Архивировано из оригинала 2021-08-14 . Получено 1 сентября 2021 г.
  12. ^ "Что нового" . Получено 1 сентября 2021 г. .
  13. ^ "Prime95 v30.3" . Получено 1 сентября 2021 г.
  14. ^ Woltman, George (2020-06-16). "The Next Big Development for GIMPS". Форум GIMPS . Получено 20 мая 2022 г.
  15. ^ Вольтман, Джордж (2021-04-08). "First time LL is no more" . Получено 19 мая 2022 г. .
  16. ^ "PrimeNet ECM Progress" . Получено 20 мая 2022 г.
  17. ^ The Mersenne Newsletter, выпуск № 9. Получено 2011-10-02. Архивировано 2012-02-06 на Wayback Machine
  18. ^ "mersenneforum.org - Просмотреть отдельную запись - Вечеринка началась! GIMPS исполняется 10 лет!!!". www.mersenneforum.org . Получено 22 декабря 2018 г. .
  19. ^ Woltman, George (24 февраля 1996 г.). "The Mersenne Newsletter, issue #1" (txt) . Great Internet Mersenne Prime Search (GIMPS) . Получено 16.06.2009 .
  20. ^ ab Woltman, George (15 января 1997 г.). "The Mersenne Newsletter, issue #9" (txt) . GIMPS . Получено 16 июня 2009 г.
  21. ↑ The Mersenne Newsletter, выпуск № 9. Получено 25 августа 2009 г.
  22. ^ Уолтман, Джордж (12 апреля 1996 г.). "The Mersenne Newsletter, issue #3" (txt) . GIMPS . Получено 16 июня 2009 г.
  23. ^ Уолтман, Джордж (23 ноября 1996 г.). "The Mersenne Newsletter, issue #8" (txt) . GIMPS . Получено 16 июня 2009 г.
  24. ^ Сводка активности PrimeNet, GIMPS , получено 19 июля 2022 г.
  25. ^ Сводка активности PrimeNet, GIMPS , получено 2012-04-05
  26. ^ "TOP500 - Ноябрь 2012". Архивировано из оригинала 5 октября 2018 года . Получено 22 ноября 2012 года .
  27. ^ TOP500 на ноябрь 2012 г.; HP BL460c с 95,1 TFLOP/s (R max). "TOP500 - Rank 329" . Получено 22 ноября 2012 г.
  28. ^ "Исходный код программного обеспечения". Mersenne Research, Inc. Получено 16 марта 2013 г.
  29. ^ Премия EFF Cooperative Computing Awards, Electronic Frontier Foundation, 29 февраля 2008 г. , получено 19 сентября 2011 г.
  30. ^ "Mlucas README".
  31. ^ «Без названия».
  32. ^ "Список известных простых чисел Мерсенна GIMPS". Mersenne Research, Inc. Получено 03.01.2018 .
  33. ^ "Вехи GIMPS". Mersenne Research, Inc. Получено 30.11.2020 .
  34. ^ "M40, что пошло не так? - Страница 11 - mersenneforum.org". mersenneforum.org . Получено 22 декабря 2018 г. .
  35. ^ «Проект GIMPS обнаружил самое большое известное простое число». 19 января 2016 г.
  • Официальный сайт
Взято с "https://en.wikipedia.org/w/index.php?title=Great_Internet_Mersenne_Prime_Search&oldid=1257087325"