GIMPS
[[Файл: |220x80px]] | |
[[Файл: |250x350px]] Prime95, запущенная в Wine. | |
| Платформа |
своя |
|---|---|
| Объём загружаемого ПО |
4 МБ |
| Объём загружаемых данных задания |
<1 КБ |
| Объём отправляемых данных задания |
<1 КБ |
| Объём места на диске |
27 МБ |
| Используемый объём памяти |
2,5 МБ (TF), |
| Графический интерфейс | |
| Среднее время расчёта задания |
20 мин. — 1 день (TF), |
| Deadline |
нет |
| Возможность использования GPU |
нет |
GIMPS (Great Internet Mersenne Prime Search) — широкомасштабный проект добровольных вычислений по поиску простых чисел Мерсенна.
Содержание
Цели и методы проекта
Определение того, является ли данное число простым, в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, предложенный (и строго обоснованный теоретически) детерминированный алгоритм практически непригоден, в виду его большой, хотя и полиномиальной, сложности. Поэтому в криптографии с открытым ключом, где используются простые числа порядка <math>10^{300}</math>, простоту по-прежнему определяют с помощью эффективных вероятностных тестов, таких как тест Миллера — Рабина. Важно отметить, что если практика довольствуется числами, являющимися простыми с вероятностью близкой к <math>1</math>, то теория такие числа не приемлет: если про число утверждается, что оно простое, это должно быть строго доказано. Эта разница подчёркивается в разделении алгоритмов на вероятностные и детерминированные.
Если задаться вопросом, какое же наибольшее простое число[1] известно человечеству — то ответом будет какое-то простое число Мерсенна. Числа Мерсенна имеют вид <math>M_p = 2^p - 1</math>. Заметим, что простота числа <math>2^p - 1</math> влечёт простоту <math>p</math>; в противном случае <math>p=xy</math> для <math>x,y>1</math> и число <math>2^p - 1 = 2^{xy} - 1</math> не будет простым в виду делимости на <math>2^x - 1</math> (как, впрочем, и на <math>2^y - 1</math>).
Как следует из названия, целью проекта GIMPS является поиск новых простых чисел Мерсенна. Самое большое известное на данный момент простое число <math>M_{74207281} = 2^{74207281} - 1</math> было найдено в рамках проекта GIMPS 7 января 2016 года и состоит из 22 338 618 десятичных цифр. Более того, тринадцать предыдущих рекордов также были установлены участниками GIMPS. Причина кроется в наличии эффективного (детерминированного) критерия их простоты, носящего имя Люка — Лемера. Для поиска простых чисел Мерсенна сервер GIMPS раздаёт клиентам простые «экспоненты» <math>p</math> для проверки числа <math>M_p</math> на простоту тестом Люка — Лемера.
На сегодняшний день известны 49 простых чисел Мерсенна, при этом достоверно известны порядковые номера первых 44 из них. Порядковые номера четырех наибольших известных простых чисел Мерсенна пока достоверно не установлены (между ними могут оказаться другие, ещё не открытые простые числа Мерсенна).[2]
Практическая значимость
Простые числа Мерсенна интересны уже тем, что они стабильно удерживают рекорд как самые большие известные простые числа.
Кроме того, простые числа Мерсенна играют важную роль в некоторых проблемах теории чисел. Например, Евклид обнаружил, что если число <math>M_p = 2^p - 1</math> простое, то число <math>M_p (M_p + 1)/2 = 2^{p-1}(2^p - 1)</math> совершенно, т. е. равно сумме своих собственных делителей (примеры таких чисел: 6=1+2+3, 28=1+2+4+7+14, 496=1+2+4+8+16+31+62+124+248, а Эйлер впоследствии доказал, что все чётные совершенные числа имеют указанный вид (вопрос о существовании нечётного совершенного числа открыт до сих пор).
Остаётся открытым вопрос о бесконечности количества простых чисел Мерсенна и об их асимптотике. Найденные простые числа Мерсенна могут служить отправной точкой для выдвижения и проверки гипотез о поведении простых чисел Мерсенна.
На практике простые числа Мерсенна применяются для построения генераторов псевдо-случайных чисел с большими периодами (см. Вихрь Мерсенна).
Денежные призы
GIMPS выиграла[3] денежный приз в 100 000 долларов США за нахождение простого числа из более чем 10 миллионов десятичных цифр и намеревается выиграть аналогичные призы в 150 000 и 250 000 долларов США, обещанные[4] Electronic Frontier Foundation за нахождение простых чисел соответственно из более чем 100 миллионов и 1 миллиарда десятичных цифр. Из суммы этого приза планируется сделать выплаты всем «открывателям» предыдущих простых чисел Мерсенна, авторам программного обеспечения и авторам новых, более эффективных алгоритмов поиска (если такие алгоритмы будут найдены).
Найденное в августе 2008 года число <math>M_{43112609} = 2^{43112609} - 1</math> содержит 12 978 189 десятичных цифр и является первым известным простым числом, состоящим более чем из 10 миллионов цифр, что позволило GIMPS получить премию в 100 000 долларов США. Однако, чтобы получить следующую премию в 150 000 долларов США, придётся проверять на простоту числа из более чем 100 миллионов десятичных цифр, каждое из которых при текущем развитии вычислительной и алгоритмической техники потребует более трёх лет.
Кроме денежного вознаграждения, имя открывателя навсегда будет записано в анналы математики.
Вероятность успеха
Эвристические оценки показывают, что существуют ещё четыре неизвестных простых числа Мерсенна, состоящие менее чем из 100 миллионов десятичных цифр, а ближайшее из них может состоять примерно из 26 миллионов цифр[5]. Подробную информацию об их возможном распределении, а также об ожидаемых трудозатратах на их нахождение можно получить на странице статистики проекта.[6]
Тестирование аппаратного обеспечения
Клиентская программа GIMPS проводит интенсивные вычисления, постоянно следя за их точностью. Поэтому многие рассматривают её как прекрасный инструмент для тестирования стабильности работы аппаратной части компьютера. Пиковые нагрузки и жёсткий контроль позволяют легко выявлять проблемы с памятью, кэшем, шиной данных, разгоном и перегревом процессора и т. п. Для облегчения процедуры тестирования клиент GIMPS предоставляет возможность работы в режиме «stress testing», когда вычисления проводятся для известных простых чисел Мерсенна и результаты вычислений сверяются с ожидаемыми.
Поддерживаемые операционные системы
Клиентская часть ПО проекта GIMPS доступна[7] для следующих операционных систем:
- Microsoft Windows 7/Vista/XP/2008/2003/2000/NT/Me/98/95. Также есть версия для 64-битных вариантов Windows 7/Vista/XP/2008.
- Mac OS X
- GNU/Linux (64-битная и 32-битная версии)
- FreeBSD (64-битная и 32-битная версии)
Напишите отзыв о статье "GIMPS"
Примечания
- ↑ [www.utm.edu/research/primes/largest.html The Largest Known Primes] (англ.)
- ↑ [primes.utm.edu/mersenne/index.html#known Table of Known Mersenne Primes] (англ.)
- ↑ [www.eff.org/press/archives/2009/10/14-0 Record 12-Million-Digit Prime Number Nets $100,000 Prize] (англ.)
- ↑ [www.eff.org/awards/coop EFF Cooperative Computing Awards] (англ.)
- ↑ [primes.utm.edu/notes/faq/NextMersenne.html Where is the next Mersenne prime?] (англ.)
- ↑ [www.mersenne.org/primenet/ PrimeNet Activity Summary] (англ.)
- ↑ [www.mersenne.org/freesoft/ Download GIMPS client] (англ.)
Ссылки
- [www.mersenne.org Официальный сайт проекта GIMPS] (англ.)
- [www.mersenne.ca Инструменты и расширенная статистика GIMPS] (англ.)
- [mersenne.ru/ Сайт команды GIMPS.Russia]
- [gimps.in.ua/ Сайт команды, представляющей на проекте Украину]
- [lenta.ru/articles/2013/02/12/mersenne/ Найдено 48-е число Мерсенна ]
- [naukatehnika.com/samoe-bolshoe-prostoe-chislo-soderzhit-svyishe-22-mln-znakov.html Найдено 49-е число Мерсенна]
- [mersennewiki.org Mersenne Wiki] (англ.)
- [mersenneforum.org/ Официальный форум GIMPS] (англ.)
Отрывок, характеризующий GIMPS
– Оттого, что не всё делается, как предполагается, и не так регулярно, как на параде. Мы полагали, как я вам говорил, зайти в тыл к семи часам утра, а не пришли и к пяти вечера.– Отчего же вы не пришли к семи часам утра? Вам надо было притти в семь часов утра, – улыбаясь сказал Билибин, – надо было притти в семь часов утра.
– Отчего вы не внушили Бонапарту дипломатическим путем, что ему лучше оставить Геную? – тем же тоном сказал князь Андрей.
– Я знаю, – перебил Билибин, – вы думаете, что очень легко брать маршалов, сидя на диване перед камином. Это правда, а всё таки, зачем вы его не взяли? И не удивляйтесь, что не только военный министр, но и августейший император и король Франц не будут очень осчастливлены вашей победой; да и я, несчастный секретарь русского посольства, не чувствую никакой потребности в знак радости дать моему Францу талер и отпустить его с своей Liebchen [милой] на Пратер… Правда, здесь нет Пратера.
Он посмотрел прямо на князя Андрея и вдруг спустил собранную кожу со лба.
– Теперь мой черед спросить вас «отчего», мой милый, – сказал Болконский. – Я вам признаюсь, что не понимаю, может быть, тут есть дипломатические тонкости выше моего слабого ума, но я не понимаю: Мак теряет целую армию, эрцгерцог Фердинанд и эрцгерцог Карл не дают никаких признаков жизни и делают ошибки за ошибками, наконец, один Кутузов одерживает действительную победу, уничтожает charme [очарование] французов, и военный министр не интересуется даже знать подробности.
– Именно от этого, мой милый. Voyez vous, mon cher: [Видите ли, мой милый:] ура! за царя, за Русь, за веру! Tout ca est bel et bon, [все это прекрасно и хорошо,] но что нам, я говорю – австрийскому двору, за дело до ваших побед? Привезите вы нам свое хорошенькое известие о победе эрцгерцога Карла или Фердинанда – un archiduc vaut l'autre, [один эрцгерцог стоит другого,] как вам известно – хоть над ротой пожарной команды Бонапарте, это другое дело, мы прогремим в пушки. А то это, как нарочно, может только дразнить нас. Эрцгерцог Карл ничего не делает, эрцгерцог Фердинанд покрывается позором. Вену вы бросаете, не защищаете больше, comme si vous nous disiez: [как если бы вы нам сказали:] с нами Бог, а Бог с вами, с вашей столицей. Один генерал, которого мы все любили, Шмит: вы его подводите под пулю и поздравляете нас с победой!… Согласитесь, что раздразнительнее того известия, которое вы привозите, нельзя придумать. C'est comme un fait expres, comme un fait expres. [Это как нарочно, как нарочно.] Кроме того, ну, одержи вы точно блестящую победу, одержи победу даже эрцгерцог Карл, что ж бы это переменило в общем ходе дел? Теперь уж поздно, когда Вена занята французскими войсками.
– Как занята? Вена занята?
– Не только занята, но Бонапарте в Шенбрунне, а граф, наш милый граф Врбна отправляется к нему за приказаниями.
Болконский после усталости и впечатлений путешествия, приема и в особенности после обеда чувствовал, что он не понимает всего значения слов, которые он слышал.
– Нынче утром был здесь граф Лихтенфельс, – продолжал Билибин, – и показывал мне письмо, в котором подробно описан парад французов в Вене. Le prince Murat et tout le tremblement… [Принц Мюрат и все такое…] Вы видите, что ваша победа не очень то радостна, и что вы не можете быть приняты как спаситель…
– Право, для меня всё равно, совершенно всё равно! – сказал князь Андрей, начиная понимать,что известие его о сражении под Кремсом действительно имело мало важности ввиду таких событий, как занятие столицы Австрии. – Как же Вена взята? А мост и знаменитый tete de pont, [мостовое укрепление,] и князь Ауэрсперг? У нас были слухи, что князь Ауэрсперг защищает Вену, – сказал он.
– Князь Ауэрсперг стоит на этой, на нашей, стороне и защищает нас; я думаю, очень плохо защищает, но всё таки защищает. А Вена на той стороне. Нет, мост еще не взят и, надеюсь, не будет взят, потому что он минирован, и его велено взорвать. В противном случае мы были бы давно в горах Богемии, и вы с вашею армией провели бы дурную четверть часа между двух огней.
– Но это всё таки не значит, чтобы кампания была кончена, – сказал князь Андрей.
– А я думаю, что кончена. И так думают большие колпаки здесь, но не смеют сказать этого. Будет то, что я говорил в начале кампании, что не ваша echauffouree de Durenstein, [дюренштейнская стычка,] вообще не порох решит дело, а те, кто его выдумали, – сказал Билибин, повторяя одно из своих mots [словечек], распуская кожу на лбу и приостанавливаясь. – Вопрос только в том, что скажет берлинское свидание императора Александра с прусским королем. Ежели Пруссия вступит в союз, on forcera la main a l'Autriche, [принудят Австрию,] и будет война. Ежели же нет, то дело только в том, чтоб условиться, где составлять первоначальные статьи нового Саmро Formio. [Кампо Формио.]
– Но что за необычайная гениальность! – вдруг вскрикнул князь Андрей, сжимая свою маленькую руку и ударяя ею по столу. – И что за счастие этому человеку!
– Buonaparte? [Буонапарте?] – вопросительно сказал Билибин, морща лоб и этим давая чувствовать, что сейчас будет un mot [словечко]. – Bu onaparte? – сказал он, ударяя особенно на u . – Я думаю, однако, что теперь, когда он предписывает законы Австрии из Шенбрунна, il faut lui faire grace de l'u . [надо его избавить от и.] Я решительно делаю нововведение и называю его Bonaparte tout court [просто Бонапарт].
– Нет, без шуток, – сказал князь Андрей, – неужели вы думаете,что кампания кончена?
– Я вот что думаю. Австрия осталась в дурах, а она к этому не привыкла. И она отплатит. А в дурах она осталась оттого, что, во первых, провинции разорены (on dit, le православное est terrible pour le pillage), [говорят, что православное ужасно по части грабежей,] армия разбита, столица взята, и всё это pour les beaux yeux du [ради прекрасных глаз,] Сардинское величество. И потому – entre nous, mon cher [между нами, мой милый] – я чутьем слышу, что нас обманывают, я чутьем слышу сношения с Францией и проекты мира, тайного мира, отдельно заключенного.
– Это не может быть! – сказал князь Андрей, – это было бы слишком гадко.
– Qui vivra verra, [Поживем, увидим,] – сказал Билибин, распуская опять кожу в знак окончания разговора.
Когда князь Андрей пришел в приготовленную для него комнату и в чистом белье лег на пуховики и душистые гретые подушки, – он почувствовал, что то сражение, о котором он привез известие, было далеко, далеко от него. Прусский союз, измена Австрии, новое торжество Бонапарта, выход и парад, и прием императора Франца на завтра занимали его.
Он закрыл глаза, но в то же мгновение в ушах его затрещала канонада, пальба, стук колес экипажа, и вот опять спускаются с горы растянутые ниткой мушкатеры, и французы стреляют, и он чувствует, как содрогается его сердце, и он выезжает вперед рядом с Шмитом, и пули весело свистят вокруг него, и он испытывает то чувство удесятеренной радости жизни, какого он не испытывал с самого детства.
Он пробудился…
«Да, всё это было!…» сказал он, счастливо, детски улыбаясь сам себе, и заснул крепким, молодым сном.
На другой день он проснулся поздно. Возобновляя впечатления прошедшего, он вспомнил прежде всего то, что нынче надо представляться императору Францу, вспомнил военного министра, учтивого австрийского флигель адъютанта, Билибина и разговор вчерашнего вечера. Одевшись в полную парадную форму, которой он уже давно не надевал, для поездки во дворец, он, свежий, оживленный и красивый, с подвязанною рукой, вошел в кабинет Билибина. В кабинете находились четыре господина дипломатического корпуса. С князем Ипполитом Курагиным, который был секретарем посольства, Болконский был знаком; с другими его познакомил Билибин.
