GIMPS

GIMPS
GIMPS
Платформа своя
Объём загружаемого ПО 1,1 МБ
Объём загружаемых данных задания <1 КБ
Объём отправляемых данных задания <1 КБ
Объём места на диске 20 МБ
Используемый объём памяти 25 МБ (TF),
45 МБ (PM1-1),
350 МБ (PM1-2),
25 МБ (LL)
Графический интерфейс нет
Среднее время расчёта задания 20 мин. — 1 день (TF),
5 дней (PM1),
>2 мес. (LL)
Deadline нет
Возможность использования GPU нет
Логотип GIMPS

GIMPS (Great Internet Mersenne Prime Search) — широкомасштабный проект добровольных вычислений по поиску простых чисел Мерсенна.

Содержание

Цели и методы проекта

Определение того, является ли данное число простым, в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, предложенный (и строго обоснованный теоретически) детерминированный алгоритм практически непригоден, в виду его большой, хотя и полиномиальной, сложности. Поэтому в криптографии с открытым ключом, где используются простые числа порядка 10^{300}, простоту по-прежнему определяют с помощью эффективных вероятностных тестов, таких как тест Миллера-Рабина. Важно отметить, что если практика довольствуется числами, являющимися простыми с вероятностью близкой к 1, то теория такие числа не приемлет: если про число утверждается, что оно простое, это должно быть строго доказано. Эта разница подчёркивается в разделение алгоритмов на вероятностные и детерминированные.

Если задаться вопросом, какое же наибольшее простое число[1] известно человечеству — то ответом будет какое-то простое число Мерсенна. Числа Мерсенна имеют вид M_p = 2^p - 1. Заметим, что простота числа 2^p - 1 влечёт простоту p; в противном случае p=xy для x,y>1 и число 2^p - 1 = 2^{xy} - 1 не будет простым в виду делимости на 2^x - 1 (как, впрочем, и на 2^y - 1).

Как следует из названия, целью проекта GIMPS является поиск новых простых чисел Мерсенна. Самое большое известное на данный момент простое число M_{43112609} = 2^{43112609} - 1 было найдено в рамках проекта GIMPS в августе 2008 года. Более того, одиннадцать предыдущих рекордов также были установлены участниками GIMPS. Причина кроется в наличии эффективного (детерминированного) критерия их простоты, носящего имя Люка-Лемера. Для поиска простых чисел Мерсенна сервер GIMPS раздаёт клиентам простые «экспоненты» p для проверки числа M_p на простоту тестом Люка-Лемера.

На сегодняшний день достоверно известны только первые 40 простых чисел Мерсенна. Также найдено семь больших простых числа Мерсенна, порядковые номера которых пока не установлены.[2]

Практическая значимость

Простые числа Мерсенна интересны уже тем, что они стабильно удерживают рекорд как самые большие известные простые числа.

Кроме того, простые числа Мерсенна играют важную роль в некоторых проблемах теории чисел. Например, Евклид обнаружил, что если число M_p = 2^p - 1 простое, то число M_p (M_p + 1)/2 = 2^{p-1}(2^p - 1) совершенно, т. е. равно сумме своих собственных делителей (примеры таких чисел: 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 и 1000 миллионов десятичных цифр. Из суммы этого приза планируется сделать выплаты всем «открывателям» предыдущих простых чисел Мерсенна, авторам программного обеспечения и авторам новых, более эффективных алгоритмов поиска (если такие алгоритмы будут найдены).

Найденный в августе 2008 года рекордсмен M_{43112609} = 2^{43112609} - 1 содержит 12 978 189 десятичных цифр, что позволило GIMPS получить премию в 100 000 долларов США. Однако, чтобы получить следующую премию в 150 000 долларов США, придётся проверять на простоту числа из более чем 100 миллионов десятичных цифр, каждое из которых при текущем развитии вычислительной и алгоритмической техники потребует более трёх лет.

Кроме денежного вознаграждения, имя открывателя навсегда будет записано в анналы математики.

Вероятность успеха

Эвристические оценки показывают, что в интервале для p от 10 000 000 до 80 000 000 ждут своего открытия ещё два неизвестных простых числа Мерсенна. Подробную информацию об их возможном распределении, а также об ожидаемых трудозатратах на их нахождение можно получить на странице статистики проекта.[5]

Тестирование аппаратного обеспечения

Клиентская программа GIMPS проводит интенсивные вычисления, постоянно следя за их точностью. Поэтому многие рассматривают её как прекрасный инструмент для тестирования стабильности работы аппаратной части компьютера. Пиковые нагрузки и жёсткий контроль позволяют легко выявлять проблемы с памятью, кэшем, шиной данных, разгоном и перегревом процессора и т. п. Для облегчения процедуры тестирования клиент GIMPS предоставляет возможность работы в режиме «stress testing», когда вычисления проводятся для известных простых чисел Мерсенна и результаты вычислений сверяются с ожидаемыми.

Поддерживаемые операционные системы

Клиентская часть ПО проекта GIMPS доступна[6] для следующих операционных систем:

  • Microsoft Windows 3.1/9x/NT/2000/XP; Vista поддерживается, но с оговорками. Также есть версия для 64-битных вариантов XP/Vista.
  • Mac OS X 64-х и 32-х битные версии
  • GNU/Linux (Существуют 32-битная и 64-битная версии.)
  • FreeBSD
  • OS/2

Примечания

Ссылки


Wikimedia Foundation. 2010.

Нужно решить контрольную?

Полезное


Смотреть что такое "GIMPS" в других словарях:

  • GIMPS — GIMPS,   Grid Computing …   Universal-Lexikon

  • GIMPS — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • GIMPS — Great Internet Mersenne Prime Search Le Great Internet Mersenne Prime Search, ou GIMPS, est un projet de calcul partagé où les volontaires utilisent un logiciel client pour chercher les nombres premiers de Mersenne. Le projet a été fondé par… …   Wikipédia en Français

  • GIMPS — noun The Great Internet Mersenne Prime Search, a collaborative project using home computers to find large prime numbers …   Wiktionary

  • gimps — gɪmp n. narrow cord made of silk or other material; vigor, courage, spirit; person with a limp, lame person; limp (Slang) …   English contemporary dictionary

  • GIMPS — abbr. Great Internet Mersenne Prime Search (Internet) comp. abbr. Great Internet Mersenne Prime Search …   United dictionary of abbreviations and acronyms

  • Mersenne prime — Named after Marin Mersenne Publication year 1536[1] Author of publication Regius, H. Number of known terms 47 Conjectured number of terms Infinite …   Wikipedia

  • Great Internet Mersenne Prime Search — Die Great Internet Mersenne Prime Search (GIMPS) ist ein gemeinschaftliches Projekt zur computergestützten Suche nach Mersenne Primzahlen. Das Projekt wurde von George Woltman gegründet, der auch die Software Prime95 und MPrime für das Projekt… …   Deutsch Wikipedia

  • Mersenne-Primzahl — Poststempel mit der 23. Mersenne Primzahl, gefunden 1963 an der UIUC von Donald B. Gillies. Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die ersten acht Mersenne Zahlen Mn… …   Deutsch Wikipedia

  • Lucas-Lehmer Test — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»