§ ПОИСК ПРОСТЫХ ЧИСЕЛ МЕРСЕННА
Историческая справка
Числами Мерсенна принято называть ряд 2p -1, где p - натуральное число.
При этом простые числа в этом ряду получаются только при некоторых простых значениях p.
Благодаря открытию быстрого теста простоты Люка-Лемера (LL - Lucas-Lehmer Primality Testing) именно простые числа Мерсенна являются рекордсменами по размеру среди всех прочих видов простых чисел.
Electronic Frontier Foundation (EFF) учредила денежные призы за нахождение простых чисел-рекордсменов: награды за 1,000,000-значное и 10,000,000-значное уже были выплачены, а за 100,000,000-значное и 1,000,000,000-значное еще ждут своего часа!
http://ru.wikipedia.org/wiki/Мерсенн,_Марен
http://ru.wikipedia.org/wiki/Числа_Мерсенна
http://ru.wikipedia.org/wiki/Тест_Люка_—_Лемера
http://ru.wikipedia.org/wiki/Electronic_Frontier_Foundation
Эра GIMPS
К концу XX века стало понятно, что индивидуальный поиск зашел в тупик - слишком высока стала размерность чисел, слишком велики расстояния между соседними достижениями.
Тогда-то, в 1995 году, программисту Джорджу Уолтману (George Woltman) и пришла мысль создать проект распределенных вычислений GIMPS (Great Internet Mersenne Prime Search).
Теперь каждый участник (к концу первого года их насчитывалось уже более 1,000 человек) мог быть уверен, что проверяет никем еще не изученный диапазон значений, а следовательно плоды его усилий суммируются к прогрессу всего проекта без коллизий с другими искателями.
Результат не заставил себя ждать - все последующие рекорды были установлены именно в рамках GIMPS.
Призовой фонд, полученный от EFF, был несколько перераспределен: теперь каждый открыватель нового простого числа Мерсенна получает приз $3,000.
Но тот участник, кому посчастливится найти первое стомиллионзнаковое или миллиардзнаковое простое число (а скорее всего это будет именно число Мерсенна), получит несравненно больше!
Работа ведется одновременно по нескольким направлениям: поиск малых делителей, чтобы небольшими затратами прорежать список чисел-претендентов; поиск более крупных делителей с помощью различных алгоритмов разложения; проверка кандидатов с помощью теста простоты LL, и повторная перепроверка ради уверенности, что ни один из претендентов не оказался пропущен или протестирован с ошибкой.
TF (Trial Factoring) - разложение на множители числа-претендента путем простого перебора делителей вида 2pk +1
LL (Lucas-Lehmer) - первичная проверка на простоту числа-претендента
LL-D (Lucas-Lehmer Double-check) - перепроверка на простоту числа-претендента, уже проверенного ранее LL-тестом
PRP (PRobable Prime test) - первичная проверка на вероятную простоту числа-претендента + генерация сертификата теста (CERT)
PRP-DC (PRobable Prime test Double-Check) - перепроверка на вероятную простоту числа-претендента, уже проверенного ранее LL-тестом
CERT (Certificate test) - очень быстрая перепроверка на вероятную простоту числа-претендента, уже проверенного ранее PRP-тестом
PRP-CF (PRobable Prime test for CoFactor) - первичная проверка на вероятную простоту кофактора (числа-претендента, деленного на все его известные делители)
PRP-CF-DC (PRobable Prime test for CoFactor Double-Check) - перепроверка на вероятную простоту кофактора (числа-претендента, деленного на все его известные делители)
P-1 (P-1 Factoring) - разложение на множители P-алгоритмом Полларда
ECM (Elliptic Curve Method) - разложение на множители методом эллиптических кривых
ECMF (ECM on Fermat numbers) - разложение на множители чисел Ферма методом ECM
Ознакомиться подробнее с описаниями данных расчетов можно на сайте GIMPS:
http://mersenne.org/various/math.php
Таблица рекордов
| Номер | Число | Размерность | Дата | Открыватель | Алгоритм и компьютер |
|---|
| 1 | 22 -1 | 1 цифра | ~500 до н.э. | Древнегреческие математики | |
| 2 | 23 -1 | 1 | ~500 до н.э. | Древнегреческие математики | |
| 3 | 25 -1 | 2 | ~275 до н.э. | Древнегреческие математики | |
| 4 | 27 -1 | 3 | ~275 до н.э. | Древнегреческие математики | |
| 5 | 213 -1 | 4 | 1456 | Неизвестно | Простое деление |
| 6 | 217 -1 | 6 | 1588 | Pietro Cataldi | Простое деление |
| 7 | 219 -1 | 6 | 1588 | Pietro Cataldi | Простое деление |
| 8 | 231 -1 | 10 | 1772 | Leonhard Euler | Улучшенное простое деление |
| 9 | 261 -1 | 19 | 1883 | Иван Михеевич Первушин | Последовательность Люка |
| 10 | 289 -1 | 27 | 1911.06 | R.E.Powers | Последовательность Люка |
| 11 | 2107 -1 | 33 | 1914.06.11 | R.E.Powers | Последовательность Люка |
| 12 | 2127 -1 | 39 | 1876.01.10 | Edouard Lucas | Последовательность Люка |
Компьютерная Эра:
|
|---|
| 13 | 2521 -1 | 157 | 1952.01.30 | Raphael M.Robinson | LL / SWAC |
| 14 | 2607 -1 | 183 | 1952.01.30 | Raphael M.Robinson | LL / SWAC |
| 15 | 21,279 -1 | 386 | 1952.06.25 | Raphael M.Robinson | LL / SWAC |
| 16 | 22,203 -1 | 664 | 1952.10.07 | Raphael M.Robinson | LL / SWAC |
| 17 | 22,281 -1 | 687 | 1952.10.09 | Raphael M.Robinson | LL / SWAC |
| 18 | 23,217 -1 | 969 | 1957.09.08 | Hans Riesel | LL / BESK |
| 19 | 24,253 -1 | 1,281 | 1961.11.03 | Alexander Hurwitz | LL / IBM 7090 |
| 20 | 24,423 -1 | 1,332 | 1961.11.03 | Alexander Hurwitz | LL / IBM 7090 |
| 21 | 29,689 -1 | 2,917 | 1963.05.11 | Donald B.Gillies | LL / ILLIAC II |
| 22 | 29,941 -1 | 2,993 | 1963.05.16 | Donald B.Gillies | LL / ILLIAC II |
| 23 | 211,213 -1 | 3,376 | 1963.06.02 | Donald B.Gillies | LL / ILLIAC II |
| 24 | 219,937 -1 | 6,002 | 1971.03.04 | Bryant Tuckerman | LL / IBM 360/91 |
| 25 | 221,701 -1 | 6,533 | 1978.10.30 | Landon Curt Noll & Laura Nickel | LL / CDC Cyber 174 |
| 26 | 223,209 -1 | 6,987 | 1979.02.09 | Landon Curt Noll | LL / CDC Cyber 174 |
| 27 | 244,497 -1 | 13,395 | 1979.04.08 | Harry Lewis Nelson & David Slowinski | LL / Cray 1 |
| 28 | 286,243 -1 | 25,962 | 1982.09.25 | David Slowinski | LL / Cray 1 |
| 29 | 2110,503 -1 | 33,265 | 1988.01.28 | Walter Colquitt & Luke Welsh | LL / NEC SX-2 |
| 30 | 2132,049 -1 | 39,751 | 1983.09.19 | David Slowinski | LL / Cray X-MP |
| 31 | 2216,091 -1 | 65,050 | 1985.09.01 | David Slowinski | LL / Cray X-MP/24 |
| 32 | 2756,839 -1 | 227,832 | 1992.02.19 | David Slowinski & Paul Gage | LL / Maple - Harwell Lab Cray-2 |
| 33 | 2859,433 -1 | 258,716 | 1994.01.04 | David Slowinski & Paul Gage | LL / Cray C90 |
| 34 | 21,257,787 -1 | 378,632 | 1996.09.03 | David Slowinski & Paul Gage | LL / Cray T94 |
Эра GIMPS:
|
|---|
| 35 | 21,398,269 -1 | 420,921 | 1996.11.13 | GIMPS / Joel Armengaud | LL / Prime95 - 90 MHz Pentium PC |
| 36 | 22,976,221 -1 | 895,932 | 1997.08.24 | GIMPS / Gordon Spence | LL / Prime95 - 100 MHz Pentium PC |
| 37 | 23,021,377 -1 | 909,526 | 1998.01.27 | GIMPS / Roland Clarkson | LL / Prime95 - 200 MHz Pentium PC |
| 38 | 26,972,593 -1 | 2,098,960 | 1999.06.01 | GIMPS / Nayan Hajratwala | LL / Prime95 - 350 MHz Pentium II IBM Aptiva |
| 39 | 213,466,917 -1 | 4,053,946 | 2001.11.14 | GIMPS / Michael Cameron | LL / Prime95 - 800 MHz Athlon Thunderbird |
| 40 | 220,996,011 -1 | 6,320,430 | 2003.11.17 | GIMPS / Michael Shafer | LL / Prime95 - 2 GHz Dell Dimension |
| 41 | 224,036,583 -1 | 7,235,733 | 2004.05.15 | GIMPS / Josh Findley | LL / Prime95 - 2.4 GHz Pentium 4 PC |
| 42 | 225,964,951 -1 | 7,816,230 | 2005.02.18 | GIMPS / Martin Nowak | LL / Prime95 - 2.4 GHz Pentium 4 PC |
| 43 | 230,402,457 -1 | 9,152,052 | 2005.12.15 | GIMPS / Curtis Cooper & Steven Boone | LL / Prime95 - 2 GHz Pentium 4 PC |
| 44 | 232,582,657 -1 | 9,808,358 | 2006.09.04 | GIMPS / Curtis Cooper & Steven Boone | LL / Prime95 - 3 GHz Pentium 4 PC |
| 45 | 237,156,667 -1 | 11,185,272 | 2008.09.06 | GIMPS / Hans-Michael Elvenich | LL / Prime95 - 2.83 GHz Core 2 Duo PC |
| 46 | 242,643,801 -1 | 12,837,064 | 2009.04.12 | GIMPS / Odd M. Strindmo | LL / Prime95 - 3 GHz Core 2 PC |
| 47 | 243,112,609 -1 | 12,978,189 | 2008.08.23 | GIMPS / Edson Smith | LL / Prime95 - Dell Optiplex 745 |
| 48 | 257,885,161 -1 | 17,425,170 | 2013.01.25 | GIMPS / Curtis Cooper | LL / Prime95 - Intel Core2 Duo E8400 @ 3.00GHz |
| 49 ?? | 274,207,281 -1 | 22,338,618 | 2016.01.07 | GIMPS / Curtis Cooper | LL / Prime95 - Intel i7-4790 @ 3.60GHz |
| 50 ?? | 277,232,917 -1 | 23,249,425 | 2017.12.26 | GIMPS / Jonathan Pace | LL / Prime95 - Intel i5-6600 @ 3.30GHz |
| 51 ?? | 282,589,933 -1 | 24,862,048 | 2018.12.07 | GIMPS / Patrick Laroche | LL / Prime95 - Intel i5-6600 @ 3.30GHz |
Как водится во многих проектах, здесь также не обошлось без знаменательных достижений отдельных личностей.
Так, живой легендой последнего десятилетия является Кертис Купер (Curtis Cooper) - профессор Университета Центрального Миссури (UCM - The University of Central Missouri).
Его парк компьютерной техники, задействованной в проекте, насчитывает более 19,000 ПК!
Неудивительно, что он четырежды (!) становился номинантом награды.
В 2018 году к проекту присоединился участник - британский миллиардер Ben Delo, владелец биржи криптовалют BitMEX. Мощность GIMPS фактические удвоилась, и скорость первичной проверки экспонент обогнала все прогнозы! В связи с этим ждем новых результатов!
Но поиск очередного простого числа - не единственная задача проекта.
На другом его полюсе ведутся активные поиски делителей чисел Мерсенна, которые существенно сокращают список претендентов на полноценное тестирование LL.
Здесь особо отличается японец Тадаси Таура (Tadashi Taura) - имя в проекте TJAOI.
Он знаменит тем, что много лет собирает у себя дома различную вычислительную технику, и живет, по сути, внутри мэйнфрейма!
За четверть века он нашел более полутора десятков делителей чисел Ферма и несколько миллионов (!) делителей чисел Мерсенна!
Денежных выплат за делители в проектах не предусмотрено, поиск ведется исключительно на чистом энтузиазме!
Первоисточник: http://mersenne.org/primes/
Статус проекта на 2023.01.08
Проект охватывает диапазон экспонент до 999,999,999 (50,847,533 кандидата).
Тем не менее, статистика обнаруженных делителей ведется до 4,294,967,295 (203,280,220 кандидатов).
Проверены хотя бы однократно все экспоненты до 111.240.127.
Дважды перепроверены все экспоненты до 62.396.471.
До подтверждения номера 49-го простого числа Мерсенна осталось 178,954 тестов.
До подтверждения номера 50-го простого числа Мерсенна осталось 233,349 тестов.
До подтверждения номера 51-го простого числа Мерсенна осталось 331,852 тестов.
Узнать текущее положение дел можно на этой странице:
http://mersenne.org/report_milestones/
С чего начать новичку?
Самая большая проблема данного проекта - редкие успехи.
Практически в любой из существующих команд постоянные участники составляют скромный процент, в то время как большинство остальных забросили его.
Видимо, проект многим наскучил: кому через день, кому через неделю, кому через месяцы или даже годы.
Достичь фундаментального успеха довольно сложно: за 25 лет существования проекта было найдено всего 17 новых простых чисел Мерсенна.
Можно надеяться на Случай, ведь может быть следующему повезет именно вам!
Но в проекте также предусмотрены и более мелкие результаты - поиск делителей, отсев заведомо неподходящих составных кандидатов.
Каждый обнаруженный делитель будет подписан вашим именем. К тому же он сэкономит проекту несколько месяцев ненужного более теста простоты!
К настоящему моменту найдено уже более 43 миллионов делителей.
Непроверенными остаются еще чуть меньше 21 миллиона экспонент - так что на наш век хватит!
Поэтому рискну дать совет: опробуйте сперва свои силы на небольших заданиях.
Вы получите первые баллы GHz-Days, увидите, как начнет расти ваш рейтинг, а если повезет - то и получите свой именной делитель!
Наибольшая вероятность успеха наблюдается в режиме Trial factoring to low limits - примерно 1 успех на 75 заданий (для примера: свой 1-й делитель в 2015 году я нашел лишь через 19 дней работы CPU, а потом стал находить их по 5-20 шт. в день на GPU, сейчас, конечно, значительно реже).
Настройте несколько Worker-ов на поиск новых делителей на быстрых TF, ECM или P-1.
Помните: на многоядерных процессорах можно настроить несколько параллельно работающих Worker-ов, что может дать прирост производительности по TF до 3,5 раз!
Если спустя какое-то время вы почувствуете, что готовы остаться здесь надолго, можно взять задания и посерьезнее:
Загрузите Worker #1 долгим тестом простоты, а все остальные Worker-ы пустите на его поддержку/ускорение.
Как именно это настраивается, читайте в Инструкции на Форуме >>>
World record sized numbers to test - LL-тест экспоненты, большей чем текущий рекорд
First time tests - от недели до пары месяцев
Double-check tests - от нескольких дней до пары месяцев
PRP - примерно аналогичен LL-тесту
PRP-DC - примерно аналогичен LL-D-тесту
CERT - около 1 часа
PRP-CF - от нескольких часов
PRP-CF-DC - от нескольких часов
Trial factoring - от нескольких минут (желательно выполнять только на GPU)
P-1 factoring - около 14 часов
Trial factoring to low limits - от нескольких минут (желательно выполнять только на GPU)
ECM on small Mersenne numbers - около 1 часа
ECM on Fermat numbers - от нескольких часов (нужно много памяти)
100,000,000 digit numbers to test - от нескольких месяцев до года и более
Посмотреть, как часто вообще везет участникам проекта, можно на этой странице:
http://mersenne.org/report_recent_results/
Вы хотите присоединиться к нам?
Так получилось, что сейчас в Команде России всего несколько десятков активных участников,
компьютеры которых регулярно выполняют какие-либо расчеты для проекта GIMPS.
Это довольно мало. Будем очень рады, если Вы присоединитесь к нам и поможете увеличивать рейтинг нашей Родины!
Шаг 1: Зарегистрируйтесь в проекте ⇒ Mersenne.org
Шаг 2: Присоединитесь к нашей Команде ⇒ GIMPS.Russia
Шаг 3: Скачайте ПО и получите первые задания ⇒ ПО «Prime95»
Шаг 4: Наблюдайте за нашими последними достижениями ⇒ Team Results
Шаг 5: Пишите, если нужна помощь или появятся новые идеи ⇒ Team Contacts
|