Это официальный сайт Команды GIMPS.Russia

Мы сообща занимаемся вычислениями для проекта Mersenne.org и представляем в нем Россию!

§ ПОИСК ПРОСТЫХ ЧИСЕЛ МЕРСЕННА


Историческая справка

Числами Мерсенна принято называть ряд 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) - перепроверка уже проверенного ранее числа

P-1 (P-1 Factoring) - разложение на множители P-алгоритмом Полларда

ECM (Elliptic Curve Method) - разложение на множители методом эллиптических кривых

ECMF (ECM on Fermat numbers) - разложение на множители чисел Ферма методом ECM

Ознакомиться подробнее с описаниями данных расчетов можно на сайте GIMPS:
http://mersenne.org/various/math.php



Таблица рекордов


НомерЧислоРазмерностьДатаОткрывательАлгоритм и компьютер
122 -11 цифра~500 до н.э.Древнегреческие математики
223 -11~500 до н.э.Древнегреческие математики
325 -12~275 до н.э.Древнегреческие математики
427 -13~275 до н.э.Древнегреческие математики
5213 -141456НеизвестноПростое деление
6217 -161588Pietro CataldiПростое деление
7219 -161588Pietro CataldiПростое деление
8231 -1101772Leonhard EulerУлучшенное простое деление
9261 -1191883Иван Михеевич ПервушинПоследовательность Люка
10289 -1271911.06R.E.PowersПоследовательность Люка
112107 -1331914.06.11R.E.PowersПоследовательность Люка
122127 -1391876.01.10Edouard LucasПоследовательность Люка

Компьютерная Эра:

132521 -11571952.01.30Raphael M.RobinsonLL / SWAC
142607 -11831952.01.30Raphael M.RobinsonLL / SWAC
1521,279 -13861952.06.25Raphael M.RobinsonLL / SWAC
1622,203 -16641952.10.07Raphael M.RobinsonLL / SWAC
1722,281 -16871952.10.09Raphael M.RobinsonLL / SWAC
1823,217 -19691957.09.08Hans RieselLL / BESK
1924,253 -11,2811961.11.03Alexander HurwitzLL / IBM 7090
2024,423 -11,3321961.11.03Alexander HurwitzLL / IBM 7090
2129,689 -12,9171963.05.11Donald B.GilliesLL / ILLIAC II
2229,941 -12,9931963.05.16Donald B.GilliesLL / ILLIAC II
23211,213 -13,3761963.06.02Donald B.GilliesLL / ILLIAC II
24219,937 -16,0021971.03.04Bryant TuckermanLL / IBM 360/91
25221,701 -16,5331978.10.30Landon Curt Noll & Laura NickelLL / CDC Cyber 174
26223,209 -16,9871979.02.09Landon Curt NollLL / CDC Cyber 174
27244,497 -113,3951979.04.08Harry Lewis Nelson & David SlowinskiLL / Cray 1
28286,243 -125,9621982.09.25David SlowinskiLL / Cray 1
292110,503 -133,2651988.01.28Walter Colquitt & Luke WelshLL / NEC SX-2
302132,049 -139,7511983.09.19David SlowinskiLL / Cray X-MP
312216,091 -165,0501985.09.01David SlowinskiLL / Cray X-MP/24
322756,839 -1227,8321992.02.19David Slowinski & Paul GageLL / Maple - Harwell Lab Cray-2
332859,433 -1258,7161994.01.04David Slowinski & Paul GageLL / Cray C90
3421,257,787 -1378,6321996.09.03David Slowinski & Paul GageLL / Cray T94

Эра GIMPS:

3521,398,269 -1420,9211996.11.13GIMPS / Joel ArmengaudLL / Prime95 - 90 MHz Pentium PC
3622,976,221 -1895,9321997.08.24GIMPS / Gordon SpenceLL / Prime95 - 100 MHz Pentium PC
3723,021,377 -1909,5261998.01.27GIMPS / Roland ClarksonLL / Prime95 - 200 MHz Pentium PC
3826,972,593 -12,098,9601999.06.01GIMPS / Nayan HajratwalaLL / Prime95 - 350 MHz Pentium II IBM Aptiva
39213,466,917 -14,053,9462001.11.14GIMPS / Michael CameronLL / Prime95 - 800 MHz Athlon Thunderbird
40220,996,011 -16,320,4302003.11.17GIMPS / Michael ShaferLL / Prime95 - 2 GHz Dell Dimension
41224,036,583 -17,235,7332004.05.15GIMPS / Josh FindleyLL / Prime95 - 2.4 GHz Pentium 4 PC
42225,964,951 -17,816,2302005.02.18GIMPS / Martin NowakLL / Prime95 - 2.4 GHz Pentium 4 PC
43230,402,457 -19,152,0522005.12.15GIMPS / Curtis Cooper & Steven BooneLL / Prime95 - 2 GHz Pentium 4 PC
44232,582,657 -19,808,3582006.09.04GIMPS / Curtis Cooper & Steven BooneLL / Prime95 - 3 GHz Pentium 4 PC
45 ??237,156,667 -111,185,2722008.09.06GIMPS / Hans-Michael ElvenichLL / Prime95 - 2.83 GHz Core 2 Duo PC
46 ??242,643,801 -112,837,0642009.04.12GIMPS / Odd M. StrindmoLL / Prime95 - 3 GHz Core 2 PC
47 ??243,112,609 -112,978,1892008.08.23GIMPS / Edson SmithLL / Prime95 - Dell Optiplex 745
48 ??257,885,161 -117,425,1702013.01.25GIMPS / Curtis CooperLL / Prime95 - Intel Core2 Duo E8400 @ 3.00GHz
49 ??274,207,281 -122,338,6182016.01.07GIMPS / Curtis CooperLL / Prime95 - Intel i7-4790 @ 3.60GHz


Как водится во многих проектах, здесь также не обошлось без знаменательных достижений отдельных личностей. Так, живой легендой последнего десятилетия является Кертис Купер (Curtis Cooper) - профессор Университета Центрального Миссури (UCM - The University of Central Missouri). Его парк компьютерной техники, задействованной в проекте, насчитывает более 19,000 ПК! Неудивительно, что он четырежды (!) становился номинантом награды.

Но поиск очередного простого числа - не единственная задача проекта. Но другом его полюсе ведутся активные поиски делителей чисел Мерсенна, которые существенно сокращают список претендентов на полноценное тестирование LL. Здесь особо отличается японец Тадаси Таура (Tadashi Taura) - имя в проекте TJAOI. Он знаменит тем, что много лет собирает у себя дома различную вычислительную технику, и живет, по сути, внутри мэйнфрейма! За четверть века он нашел более полутора десятков делителей чисел Ферма и несколько миллионов (!) делителей чисел Мерсенна! Денежных выплат за делители в проектах не предусмотрено, поиск ведется исключительно на чистом энтузиазме!

Первоисточник: http://mersenne.org/primes/



Статус проекта на 2016.08.01

Проект охватывает диапазон экспонент до 999,999,999 (50,847,533 кандидата).
Тем не менее, статистика обнаруженных делителей ведется до 4,294,967,295 (203,280,220 кандидатов).

Проверены хотя бы однократно все экспоненты до 67,587,407.

Дважды перепроверены все экспоненты до 36,076,661.

До подтверждения номера 45-го простого числа Мерсенна осталось 647 тестов.

До подтверждения номера 46-го простого числа Мерсенна осталось 57,745 тестов.

До подтверждения номера 47-го простого числа Мерсенна осталось 64,469 тестов.

До подтверждения номера 48-го простого числа Мерсенна осталось 341,658 тестов.

До подтверждения номера 49-го простого числа Мерсенна осталось 657,538 тестов.

Узнать текущее положение дел можно на этой странице:
http://mersenne.org/report_milestones/



С чего начать новичку?

Самая большая проблема данного проекта - редкие успехи. Практически в любой из существующих команд постоянные участники составляют скромный процент, в то время как большинство остальных забросили его. Видимо, проект многим наскучил: кому через день, кому через неделю, кому через месяцы или даже годы. Достичь фундаментального успеха довольно сложно: за 20 лет существования проекта было найдено всего 15 новых простых чисел Мерсенна. Можно надеяться на Случай, ведь может быть следующему повезет именно вам!

Но в проекте также предусмотрены и более мелкие результаты - поиск делителей, отсев заведомо неподходящих составных кандидатов. Каждый обнаруженный делитель будет подписан вашим именем. К тому же он сэкономит проекту несколько месяцев ненужного более теста простоты! К настоящему моменту найдено уже более 33 миллионов делителей. Непроверенными остаются еще чуть меньше 23 миллионов экспонент - так что на наш век хватит!

Поэтому рискну дать совет: опробуйте сперва свои силы на небольших заданиях. Вы получите первые баллы GHz-Days, увидите, как начнет расти ваш рейтинг, а если повезет - то и получите свой именной делитель! Наибольшая вероятность успеха наблюдается в режиме Trial factoring to low limits - примерно 1 успех на 67 заданий (для примера: свой 1-й делитель я нашел лишь через 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 - 2-3 месяца интенсивно

Double-check tests - пару месяцев

Trial factoring - около суток

P-1 factoring - около 14 часов

Trial factoring to low limits - чуть больше часа

ECM on small Mersenne numbers - примерно 25 минут

ECM on Fermat numbers - около 15 часов (но бывает и месяц)

100,000,000 digit numbers to test - 2 года и более

Посмотреть, как часто вообще везет участникам проекта, можно на этой странице:
http://mersenne.org/report_recent_results/





Вы хотите присоединиться к нам?

Так получилось, что сейчас в Команде России всего несколько десятков активных участников, компьютеры которых регулярно выполняют какие-либо расчеты для проекта GIMPS. Это довольно мало. Будем очень рады, если Вы присоединитесь к нам и поможете увеличивать рейтинг нашей Родины!

Шаг 1: Зарегистрируйтесь в проекте ⇒ Mersenne.org

Шаг 2: Присоединитесь к нашей Команде ⇒ GIMPS.Russia

Шаг 3: Скачайте ПО и получите первые задания ⇒ ПО «Prime95»

Шаг 4: Наблюдайте за нашими последними достижениями ⇒ Team Results

Шаг 5: Пишите, если нужна помощь или появятся новые идеи ⇒ Team Contacts


© Copyright 2015 - Today