Отличный интернет-поиск простых чисел Мерсенна

Не путать с GIMP .
Отличный интернет-поиск простых чисел Мерсенна (GIMPS)
Логотип
Веб-сайт Мерсенн .org Отредактируйте это в Викиданных

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

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

По состоянию на октябрь 2022 г. , 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 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 г. 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 г. , 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]

См. также [ править ]

Ссылки [ править ]

  1. ^ «Волонтёрские вычисления» . БОИНК. Архивировано из оригинала 18 декабря 2021 года . Проверено 25 декабря 2021 г.
  2. ^ «Проект GIMPS обнаружил самое большое известное простое число: 2». 82,589,933 -1» . Mersenne Research, Inc. 21 декабря 2018 г. Дата обращения 21 декабря 2018 г.
  3. ^ «Отчет об основных этапах работы GIMPS» . Мерсенн.орг . Мерсенн Рисерч, Инк . Проверено 5 декабря 2020 г.
  4. ^ Что такое простые числа Мерсенна? Чем они полезны? - Домашняя страница GIMPS
  5. ^ «GIMPS — Математика — PrimeNet» .
  6. ^ «mersenneforum.org — Посмотреть отдельное сообщение — Получение надежного LL на ненадежном оборудовании» . mersenneforum.org . Проверено 5 октября 2022 г.
  7. ^ «mersenneforum.org — Посмотреть отдельное сообщение — Получение надежного LL на ненадежном оборудовании» . mersenneforum.org . Проверено 5 октября 2022 г.
  8. ^ «Объявления» . GIMPS, великий интернет-поиск простых чисел Мерсенна. Архивировано из оригинала 14 августа 2021 г. Проверено 1 сентября 2021 г.
  9. ^ "Что нового" . Проверено 1 сентября 2021 г.
  10. ^ «Прайм95 v30.3» . Проверено 1 сентября 2021 г.
  11. ^ Уолтман, Джордж (16 июня 2020 г.). «Следующее большое развитие GIMPS» . Форум ГИМПС . Проверено 20 мая 2022 г.
  12. ^ Уолтман, Джордж (08 апреля 2021 г.). «Первого раза ЛЛ больше нет» . Проверено 19 мая 2022 г.
  13. ^ «Прогресс PrimeNet ECM» . Проверено 20 мая 2022 г.
  14. ^ Информационный бюллетень Мерсенна, выпуск № 9. Проверено 2 октября 2011 г. Архивировано 6 февраля 2012 г. в Wayback Machine.
  15. ^ "mersenneforum.org - Посмотреть отдельное сообщение - Вечеринка началась! GIMPS исполняется 10 лет!!!" . www.mersenneforum.org . Проверено 22 декабря 2018 г.
  16. ^ Уолтман, Джордж (24 февраля 1996 г.). «Информационный бюллетень Мерсенна, выпуск № 1» (txt) . Отличный интернет-поиск простых чисел Мерсенна (GIMPS) . Проверено 16 июня 2009 г.
  17. ↑ Перейти обратно: Перейти обратно: а б Уолтман, Джордж (15 января 1997 г.). «Информационный бюллетень Мерсенна, выпуск № 9» (txt) . ГИМПЫ . Проверено 16 июня 2009 г.
  18. ^ Информационный бюллетень Мерсенна, выпуск № 9 . Проверено 25 августа 2009 г.
  19. ^ Уолтман, Джордж (12 апреля 1996 г.). «Информационный бюллетень Мерсенна, выпуск № 3» (txt) . ГИМПЫ . Проверено 16 июня 2009 г.
  20. ^ Уолтман, Джордж (23 ноября 1996 г.). «Информационный бюллетень Мерсенна, выпуск № 8» (txt) . ГИМПЫ . Проверено 16 июня 2009 г.
  21. ^ Сводка активности PrimeNet , GIMPS , получено 19 июля 2022 г.
  22. ^ Сводка активности PrimeNet , GIMPS , получено 5 апреля 2012 г.
  23. ^ «ТОП500 — ноябрь 2012» . Проверено 22 ноября 2012 г.
  24. ^ ТОП500 за ноябрь 2012 г.; HP BL460c с производительностью 95,1 терафлопс/с (R макс.). «ТОП500 – 329 место» . Проверено 22 ноября 2012 г.
  25. ^ «Исходный код программного обеспечения» . Мерсенн Рисерч, Инк . Проверено 16 марта 2013 г.
  26. ^ Награды EFF Cooperative Computing Awards , Electronic Frontier Foundation, 29 февраля 2008 г. , получено 19 сентября 2011 г.
  27. ^ «Млукас README» .
  28. ^ «Без названия» .
  29. ^ «Список GIMPS известных простых чисел Мерсенна» . Мерсенн Рисерч, Инк . Проверено 3 января 2018 г.
  30. ^ «Вехи GIMPS» . Мерсенн Рисерч, Инк . Проверено 30 ноября 2020 г.
  31. ^ «М40, что пошло не так? - Страница 11 - mersenneforum.org» . mersenneforum.org . Проверено 22 декабря 2018 г.
  32. ^ «Проект GIMPS обнаружил самое большое известное простое число» . 19 января 2016 г.

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Great_Internet_Mersenne_Prime_Search&oldid=1215958422"