GIMPS
Материал из Википедии — свободной энциклопедии
GIMPS (Great Internet Mersenne Prime Search) — широкомасштабный проект распределённых вычислений по поиску простых чисел Мерсенна.
- Общая схема участия в том или ином проекте распределенных вычислений выглядит так: вы скачиваете клиента под свою платформу/операционную систему, настраиваете и запускаете его в фоне. Клиент периодически общается с сервером — запрашивает у него данные на обработку и отсылает результаты. При этом клиент выполняется в idle приоритете и не мешает основной работе. Таким образом, компьютер работает как и прежде, но уже никогда не простаивает.
Содержание |
[править] Цели и методы проекта
В школе нас учат, что все натуральные числа, большие единицы, разделяются на простые и составные. По определению число называется простым, если оно имеет ровно два натуральных делителя: единицу и само себя. Последовательность простых чисел начинается так: 2,3,5,7,11,13,17,19,23,29,31,... Ещё Евклид доказал, что простых чисел бесконечно много.
Определение того, является ли данное число простым или составным, в общем случае не такая уж тривиальная задача. Только в 2002 году было доказано, что она полиномиально разрешима. Тем не менее, предложенный (и строго обоснованный теоретически) детерминированный алгоритм практически непригоден, в виду его большой (хотя и полиномиальной) сложности. Поэтому в криптографии с открытым ключом, где используются простые числа порядка 10300, простоту по-прежнему определяют с помощью эффективных вероятностных тестов (например, тест Миллера-Рабина). Важно отметить, что если практика довольствуется числами, являющимися простыми с вероятностью близкой к 1, то теория такие числа не приемлет: если про число утверждается, что оно простое, это должно быть строго доказано. Эта разница подчёркивается в разделение алгоритмов на вероятностные и детерминированные.
Если мы зададимся вопросом, какое же наибольшее простое число известно человечеству — то ответом будет какое-то простое число Мерсенна. Числа Мерсенна имеют вид Mp = 2p - 1. Заметим, что простота числа 2p - 1 влечёт простоту p; в противном случае p = xy для x,y > 1 и число 2p - 1 = 2xy - 1 не будет простым в виду делимости на 2x - 1 (как, впрочем, и на 2y - 1).
Как следует из названия, целью проекта GIMPS является поиск новых простых чисел Мерсенна. Самое большое известное на данный момент простое число M32582657 = 232582657 − 1 было найдено в рамках проекта GIMPS в сентябре 2006 года. Более того, девять (!) предыдущих рекордов также были установлены участниками GIMPS. Причина кроется в наличие эффективного (детерминированного!) критерия их простоты, носящего имя Люка-Лемера. Для поиска простых чисел Мерсенна сервер GIMPS раздаёт клиентам простые «экспоненты» p для проверки числа Mp на простоту тестом Люка-Лемера.
На сегодняшний день достоверно известны только первые 39 простых чисел Мерсенна. Также найдено пять больших простых числа Мерсенна, порядковые номера которых пока не установлены.
[править] Практическая значимость
Простые числа Мерсенна интересны уже тем, что они стабильно удерживают рекорд как самые большие известные простые числа.
Кроме того, простые числа Мерсенна играют важную роль в некоторых проблемах теории чисел. Например, тот же Евклид обнаружил, что если число Mp = 2p - 1 простое, то число Mp(Mp + 1) / 2 = 2p - 1(2p - 1) будет совершенным, т. е. равно сумме своих собственных делителей (примеры таких чисел: 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14, 496 = 1 + 2 + 4 + 6 + 16 + 31 + 62 + 124 + 248), а Эйлер впоследствии доказал, что все чётные совершенные числа имеют указанный вид (вопрос о существовании нечётного совершенного числа открыт до сих пор).
Остаётся открытым вопрос о бесконечности количества простых чисел Мерсенна и об их асимптотике. Найденные простые числа Мерсенна могут служить отправной точкой для выдвижения и проверки гипотез о поведении простых чисел Мерсенна.
На практике простые числа Мерсенна применяются для построения генераторов псевдо-случайных чисел с большими периодами. Примером является «Mersenne Twister».
[править] Личная выгода от участия
Плох тот солдат, который не мечтает стать генералом. Есть, конечно, альтруисты, которым интересен счёт ради счёта. Но многие люди питают надежду на успех и денежное вознаграждение. И не зря.
Многие проекты распределённых вычислений так или иначе финансируются. И участник, нашедший на своём компьютере заветное значение/объект поиска, как правило, награждается кругленькой суммой. В этом смысле, такие проекты можно рассматривать как лотерею, в которой вы платите за участие своим компьютерным временем, считаете что-то полезное (или бесполезное), и имеете шанс выиграть приз. Причём, шанс на успех прямо пропорционален вложенным мощностям — как и в лотерее: чем больше билетов вы покупаете, тем больше вероятность выигрыша.
GIMPS намеревается выиграть награду в $100000, обещанную Electronic Frontier Foundation за нахождение простого числа из более чем 107 десятичных цифр. Из суммы этого приза планируется сделать выплаты всем «открывателям» предыдущих простых чисел Мерсенна (до $5000 на каждое), авторам программного обеспечения и авторам новых, более эффективных алгоритмов поиска (если такие алгоритмы будут найдены). Счастливчику нашедшему «то самое» простое число из более чем 107 десятичных цифр будет выплачен остаток, который будет гарантированно не меньше $25000.
Заметим, что текущий рекордсмен M32582657 содержит 9808358 десятичных цифр. Таким образом, для достижения планки в 107 цифр, GIMPS надо увеличить показатель (и соответственно длину числа) в 1.02 раза.
Кроме денежного вознаграждения, имя открывателя навсегда будет записано в анналы математики.
Клиентская программа GIMPS проводит интенсивные вычисления, постоянно следя за их точностью. Поэтому многие рассматривают её как прекрасный инструмент для тестирования стабильности работы аппаратной части компьютера. Пиковые нагрузки и жёсткий контроль позволяют легко выявлять проблемы с памятью, кэшем, шиной данных, разгоном и перегревом процессора и т. п. Для облегчения процедуры тестирования клиент GIMPS предоставляет возможность работы в режиме «stress testing», когда вычисления проводятся для известных простых чисел Мерсенна и результаты вычислений сверяются с ожидаемыми.
[править] Вероятность успеха
Эвристические оценки показывают, что в интервале для p от 10000000 до 80000000 ждут своего открытия ещё два неизвестных простых числа Мерсенна. Подробную информацию о их возможном распределении, а также об ожидаемых трудозатратах на их нахождение, можно узнать на странице статистики проекта.
[править] Наличие клиента под используемую OS
Имеются версии клиента для
