Поиск простых чисел Мерсенна: Коллективный проект GIMPS

Введение

Добровольческий проект с использованием программного обеспечения для поиска простых чисел Мерсенна

Большой интернет-поиск простых чисел Мерсенна (GIMPS) — это совместный проект добровольцев, использующих свободно доступное программное обеспечение для поиска простых чисел Мерсенна. GIMPS был основан в 1996 году Джорджем Уолтманом, который также написал клиент Prime95 и его порт для Linux — MPrime. Скотт Куровски разработал сервер PrimeNet для демонстрации программного обеспечения для добровольных вычислений компании Entropia, основанной им в 1997 году. GIMPS зарегистрирован как Mersenne Research, Inc., с Куровски в качестве исполнительного вице-президента и члена совета директоров. GIMPS считается одним из первых крупномасштабных проектов добровольных вычислений в интернете для исследовательских целей. По состоянию на 2022 год проект обнаружил в общей сложности семнадцать простых чисел Мерсенна, пятнадцать из которых являлись крупнейшими известными простыми числами на момент их открытия. Самое большое известное простое число по состоянию на 2022 год — 2⁸²⁵⁸⁹⁹³³ − 1 (или M82⁵⁸⁹⁹³³ для краткости) и было обнаружено 7 декабря 2018 года Патриком Ларошем. 4 декабря 2020 года проект достиг важной вехи, когда все показатели степени ниже 100 миллионов были проверены как минимум один раз. С момента основания и до 2018 года проект в основном опирался на тест простоты Лукаса — Лемера, поскольку это алгоритм, специализирующийся на проверке чисел Мерсенна и особенно эффективный на двоичных компьютерных архитектурах. Перед применением к данному числу Мерсенна выполнялась фаза пробного деления, используемая для быстрого исключения многих чисел Мерсенна с малыми делителями. Также используется алгоритм p − 1 Полларда для поиска гладких множителей. В 2018 году GIMPS принял тест простоты Ферма в качестве альтернативного варианта проверки простоты, сохраняя при этом тест Лукаса — Лемера в качестве дополнительной проверки для чисел Мерсенна, которые тест Ферма определил как вероятные простые числа. (Хотя тест Лукаса — Лемера является детерминированным, а тест Ферма — только вероятностным, вероятность того, что тест Ферма обнаружит псевдопростое число Ферма, которое не является простым, значительно ниже, чем частота ошибок теста Лукаса — Лемера из-за ошибок компьютерного оборудования.) В сентябре 2020 года GIMPS начал поддерживать доказательства простоты, основанные на проверяемых функциях задержки. Файлы доказательств генерируются в процессе выполнения теста простоты Ферма. Эти доказательства, вместе с алгоритмом проверки ошибок, разработанным Робертом Гербицем, обеспечивают полную уверенность в правильности результата теста и устраняют необходимость в двойных проверках. Первичные тесты Лукаса — Лемера были прекращены в апреле 2021 года. GIMPS также имеет подпроекты по факторизации известных составных чисел Мерсенна и Ферма.

The Great Internet Mersenne Prime Search (GIMPS) is a collaborative project of volunteers who use freely available software to search for Mersenne prime numbers. GIMPS was founded in 1996 by George Woltman, who also wrote the Prime95 client and its Linux port MPrime. Scott Kurowski wrote the back end PrimeNet server to demonstrate volunteer computing software by Entropia, a company he founded in 1997. GIMPS is registered as Mersenne Research, Inc. with Kurowski as Executive Vice President and board director. GIMPS is said to be one of the first large scale volunteer computing projects over the Internet for research purposes. as of 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 2022 is 282,589,933 − 1 (or M82,589,933 for short) and was discovered on December 7, 2018, by Patrick Laroche. On December 4, 2020, the project passed a major milestone after all exponents below 100 million were checked at least once. From its inception until 2018, the project relied primarily on the Lucas–Lehmer primality test as it is an algorithm that is both specialized for testing Mersenne primes and particularly efficient on binary computer architectures. Before applying it to a given Mersenne number, there was a trial division phase, used to rapidly eliminate many Mersenne numbers with small factors. Pollard's p − 1 algorithm is also used to search for smooth factors. In 2018, GIMPS adopted a Fermat primality test as an alternative option for primality testing, while keeping the Lucas Lehmer test as a double check for Mersenne numbers detected as probable primes by the Fermat test. (While the Lucas Lehmer test is deterministic and the Fermat test is only probabilistic, the probability of the Fermat test finding a Fermat pseudoprime that is not prime is vastly lower than the error rate of the Lucas Lehmer test due to computer hardware errors.) In September 2020, GIMPS began to support primality proofs based on verifiable delay functions. The proof files are generated while the Fermat primality test is in progress. These proofs, together with an error checking algorithm devised by Robert Gerbicz, provide a complete confidence in the correctness of the test result and eliminate the need for double checks. First time Lucas Lehmer tests were deprecated in April 2021. GIMPS also has sub projects to factor known composite Mersenne and Fermat numbers.

История

Проект начался в начале января 1996 года с программы, работавшей на компьютерах i386. Название проекта придумал Люк Уэлш, один из первых участников и соавтор открытия 29-го числа Мерсенна. В течение нескольких месяцев к проекту присоединились несколько десятков человек, а к концу первого года – более тысячи. Участник проекта Джоэль Арменго 13 ноября 1996 года доказал простоту числа M1,398,269. С тех пор GIMPS в среднем открывает новое число Мерсенна каждые 1–2 года. Однако с 2018 года новые числа Мерсенна не находились, что является самым длительным периодом без новых открытий с момента начала проекта (более 5 лет по состоянию на 2024 год).

Статус

по состоянию на 2022 год, GIMPS демонстрирует устойчивую среднюю совокупную производительность около 4,71 Петафлопс (или PFLOPS). В ноябре 2012 года GIMPS достигал 95 Тфлопс, что теоретически позволило бы виртуальному компьютеру GIMPS занять 330-е место в рейтинге TOP500 самых мощных известных компьютерных систем в мире. Предыдущее место в рейтинге занимал кластер "HP Cluster Platform 3000 BL460c G7" компании Hewlett Packard. Согласно результатам TOP500 на июль 2021 года, текущие показатели GIMPS уже не позволяют ему войти в этот список. Ранее, в начале 2010 года, производительность составляла около 50 Тфлопс, в середине 2008 года – 30 Тфлопс, в середине 2006 года – 20 Тфлопс, а в начале 2004 года – 14 Тфлопс.

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

Хотя исходный код программного обеспечения GIMPS общедоступен, технически это не свободное программное обеспечение, поскольку оно имеет ограничение, которое пользователи должны соблюдать в соответствии с условиями распространения проекта. В частности, если программное обеспечение используется для обнаружения простого числа с не менее 100 000 000 десятичных цифр, пользователь выиграет только 50 000 долларов из приза в 150 000 долларов, предлагаемого Фондом электронных границ. С другой стороны, они выиграют 3 000 долларов, когда обнаружат меньшее простое число, не имеющее права на приз. Программы третьих сторон для тестирования чисел Мерсена, такие как Mlucas и Glucas (для не-x86 систем), не имеют этого ограничения. GIMPS также "зарезервирует за собой право изменять данное лицензионное соглашение без предварительного уведомления и с разумной обратной силой". GIMPS обнаружил все известные простые числа Мерсена, начиная с 35-го.

Although the GIMPS software's source code is publicly available, technically it is not free software, since it has a restriction that users must abide by the project's distribution terms. Specifically, if the software is used to discover a prime number with at least 100,000,000 decimal digits, the user will only win $50,000 of the $150,000 prize offered by the Electronic Frontier Foundation. On the other hand, they will win $3,000 when discovering a smaller prime not qualifying for the prize. Third party programs for testing Mersenne numbers, such as Mlucas and Glucas (for non x86 systems), do not have this restriction. GIMPS also "reserves the right to change this EULA without notice and with reasonable retroactive effect." GIMPS has found all known Mersenne primes beginning with the 35th. # Discovery date Prime Mp Digits count Processor 35 November 13, 1996 M1398269 420,921 Pentium (90 MHz) 36 August 24, 1997 M2976221 895,932 Pentium (100 MHz) 37 January 27, 1998 M3021377 909,526 Pentium (200 MHz) 38 June 1, 1999 M6972593 2,098,960 Pentium (350 MHz) 39 November 14, 2001 M13466917 4,053,946 AMD T Bird (800 MHz) 40 November 17, 2003 M20996011 6,320,430 Pentium (2 GHz) 41 May 15, 2004 M24036583 7,235,733 Pentium 4 (2.4 GHz) 42 February 18, 2005 M25964951 7,816,230 Pentium 4 (2.4 GHz) 43 December 15, 2005 M30402457 9,152,052 Pentium 4 (2 GHz overclocked to 3 GHz) 44 September 4, 2006 M32582657 9,808,358 Pentium 4 (3 GHz) 45 September 6, 2008 M37156667 11,185,272 Intel Core 2 Duo (2.83 GHz) 46 June 4, 2009 M42643801 12,837,064 Intel Core 2 Duo (3 GHz) 47 August 23, 2008 M43112609 12,978,189 Intel Core 2 Duo E6600 CPU (2.4 GHz) 48 January 25, 2013 M57885161 17,425,170 Intel Core 2 Duo E8400 @ 3.00 GHz 49 January 7, 2016 M74207281 22,338,618 Intel Core i7 4790 50 December 26, 2017 M77232917 23,249,425 Intel Core i5 6600 51 December 7, 2018 M82589933 24,862,048 Intel Core i5 4590T

as of 2023, 65,723,341 is the largest exponent below which all other prime exponents have been checked twice, so it is not verified whether any undiscovered Mersenne primes exist between the 48th (M57885161) and the 51st (M82589933) on this chart; the ranking is therefore provisional. Furthermore, 114,055,847 is the largest exponent below which all other prime exponents have been tested at least once, so all Mersenne numbers below the 51st (M82589933) have been tested. The number M82589933 has 24,862,048 decimal digits. To help visualize the size of this number, if it were to be saved to disk, the resulting text file would be nearly 25 megabytes long (most books in plain text format clock in under two megabytes). A standard word processor layout (50 lines per page, 75 digits per line) would require 6,629 pages to display it. If one were to print it out using standard printer paper, single sided, it would require approximately 14 reams (14 × 500 = 7000 sheets) of paper. Whenever a possible prime is reported to the server, it is verified first (by one or more independent tests on different machines) before being announced. The importance of this was illustrated in 2003, when a false positive was reported to the server as being a Mersenne prime but verification failed. The official "discovery date" of a prime is the date that a human first noticed the result for the prime, which may differ from the date that the result was first reported to the server. For example, M74207281 was reported to the server on September 17, 2015, but the report was overlooked until January 7, 2016.

# Дата открытия Prime Mp Количество цифр Процессор
35 13 ноября 1996 M1398269 420 921 Pentium (90 МГц)
36 24 августа 1997 M2976221 895 932 Pentium (100 МГц)
37 27 января 1998 M3021377 909 526 Pentium (200 МГц)
38 1 июня 1999 M6972593 2 098 960 Pentium (350 МГц)
39 14 ноября 2001 M13466917 4 053 946 AMD T Bird (800 МГц)
40 17 ноября 2003 M20996011 6 320 430 Pentium (2 ГГц)
41 15 мая 2004 M24036583 7 235 733 Pentium 4 (2,4 ГГц)
42 18 февраля 2005 M25964951 7 816 230 Pentium 4 (2,4 ГГц)
43 15 декабря 2005 M30402457 9 152 052 Pentium 4 (2 ГГц, разогнан до 3 ГГц)
44 4 сентября 2006 M32582657 9 808 358 Pentium 4 (3 ГГц)
45 6 сентября 2008 M37156667 11 185 272 Intel Core 2 Duo (2,83 ГГц)
46 4 июня 2009 M42643801 12 837 064 Intel Core 2 Duo (3 ГГц)
47 23 августа 2008 M43112609 12 978 189 Intel Core 2 Duo E6600 CPU (2,4 ГГц)
48 25 января 2013 M57885161 17 425 170 Intel Core 2 Duo E8400 @ 3,00 ГГц
49 7 января 2016 M74207281 22 338 618 Intel Core i7 4790
50 26 декабря 2017 M77232917 23 249 425 Intel Core i5 6600
51 7 декабря 2018 M82589933 24 862 048 Intel Core i5 4590T

По состоянию на 2023 год, 65 723 341 является наибольшим показателем степени, ниже которого все остальные простые показатели были проверены дважды, поэтому не установлено, существуют ли необнаруженные простые числа Мерсена между 48-м (M57885161) и 51-м (M82589933) в этой таблице; поэтому рейтинг является предварительным. Кроме того, 114 055 847 является наибольшим показателем степени, ниже которого все остальные простые показатели были протестированы хотя бы один раз, поэтому все числа Мерсена ниже 51-го (M82589933) были проверены. Число M82589933 имеет 24 862 048 десятичных цифр. Чтобы лучше представить размер этого числа, если бы оно было сохранено на диске, то в результате получившийся текстовый файл был бы почти 25 мегабайт (большинство книг в формате обычного текста занимают менее двух мегабайт). Для стандартной компоновки текстового процессора (50 строк на странице, 75 цифр на строку) потребуется 6629 страниц для его отображения. Если бы его распечатали на стандартной односторонней бумаге, то для этого потребовалось бы примерно 14 пачек (14 × 500 = 7000 листов) бумаги. Всякий раз, когда сервер получает сообщение о возможном простом числе, оно сначала проверяется (одним или несколькими независимыми тестами на разных машинах), прежде чем объявляется. Важность этого была проиллюстрирована в 2003 году, когда ложноположительный результат был сообщен серверу как простое число Мерсена, но проверка не удалась. Официальная "дата открытия" простого числа - это дата, когда человек впервые заметил результат для простого числа, которая может отличаться от даты, когда результат был впервые сообщен серверу. Например, M74207281 было сообщено на сервер 17 сентября 2015 года, но отчет был проигнорирован до 7 января 2016 года.