Обновите ArcaOS до уровня NeoWPS Установите набор PNG иконок, нарисованных дизайнером, специализирующемся на оформлении OS/2 Установите eSchemes 2018, чтобы менять цвета и кнопки на рабочем столе

TITLE: Распределённые вычисления и проект GIMPS

DATE: 2003-01-13 09:55:31

AUTHOR: Max Alekseyev

В последнее время появилось много проектов распределённых вычислений (см. обзоры здесь, тут или там), зазывающих всех желающих занять время простоя компьютера полезными и не очень вычислениями. Наиболее известным подобным проектом является взлом RC5, проводимый distributed.net, который в то же время относится к наиболее бессмысленным.

Общая схема участия в том или ином проекте выглядит так: вы скачиваете клиента под свою платформу/операционную систему, настраиваете и запускаете его в фоне. Клиент периодически общается с сервером - запрашивает у него данные на обработку и отсылает результаты. При этом клиент выполняется в idle приоритете и не мешает основной работе. Таким образом, компьютер работает как и прежде, но уже никогда не простаивает.

Если вы хотите принять участие в одном из проектов, немедленно возникает вопрос какой из них предпочесть. Кажется разумным сравнивать проекты распределённых вычислений по следующим критериям:

1. Цели и методы проекта
2. Практическая значимость
3. Личная выгода от участия
4. Вероятность успеха
5. Наличие клиента под используемую OS (в нашем случае OS/2)

Я не ставлю перед собой цель дать исчерпывающую сравнительную характеристику различных проектов, а всего лишь хочу представить своего фаворита - проект GIMPS, в котором принимаю участие уже несколько лет. Ниже идёт подробное описание проекта по указанным критериям. Желающие смогут легко сравнить его с другими проектами.

Итак, знакомьтесь: Great Internet Mersenne Prime Search (GIMPS) - широкомасштабный интернет-проект по поиску простых чисел Мерсенна.

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

В школе нас учат, что все натуральные числа большие единицы разделяются на простые и составные. По определению число называется простым, если оно имеет ровно два натуральных делителя: единицу и само себя. Последовательность простых чисел начинается так:
2,3,5,7,11,13,17,19,23,29,31,...
Ещё Евклид доказал, что простых чисел бесконечно много.

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

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

Как следует из названия, целью проекта GIMPS является поиск новых простых чисел Мерсенна. Самое большое известное на данный момент простое число M_13466917 = 2^13466917-1 было найдено в рамках проекта GIMPS в конце 2001 года. Более того, четыре (!) предыдущих рекорда также были получены участниками GIMPS.

Числа Мерсенна выгодно отличаются от остальных простых чисел наличием эффективного (детерминированного!) критерия их простоты, носящего имя Люка-Лемера:
Число M_p является простым тогда и только тогда, когда оно делит число L_p-1, где числа L_k определяются рекуррентным соотношением:

Для поиска простых чисел Мерсенна сервер GIMPS раздаёт клиентам простые "экспоненты" p для проверки числа M_p на простоту. Клиент вычисляет последовательность чисел L₁, L₂, ..., L_p-1 по модулю числа M_p (т.е. вычисляются не сами числа L_k, длина которых растёт экспоненциально; а остатки от деления L_k на M_p, длина которых ограничена p битами). Если последнее число в этой последовательности получается нулевым, то по критерию Люка-Лемера число M_p является простым.

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

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+6+16+31+62+124+248), а Эйлер в последствии доказал, что все чётные совершенные числа имеют указанный вид (вопрос о существовании нечётного совершенного числа открыт до сих пор).

Простые числа Мерсенна также применяются для построения генераторов псевдо-случайных чисел с большими периодами. Примером является Mersenne Twister.

3. Личная выгода от участия

Плох тот солдат, который не мечтает стать генералом. Есть, конечно, альтруисты, которым интересен счёт ради счёта. Но многие люди питают надежду на успех и денежное вознаграждение. И не зря.

Многие проекты распределённых вычислений так или иначе финансируются. И участник, нашедший на своём компьютере заветное значение/объект поиска, как правило, награждается кругленькой суммой. В этом смысле, такие проекты можно рассматривать как лотерею, в которой вы платите за участие своим компьютерным временем, считаете что-то полезное (или бесполезное), и имеете шанс выиграть приз. Причём, шанс на успех прямо пропорционален вложенным мощностям - как и в лотерее: чем больше билетов вы покупаете, тем больше вероятность выигрыша.

GIMPS планирует выиграть награду в $100000, обещанную Electronic Frontier Foundation за нахождение простого числа из более чем 10⁷ десятичных цифр. Из суммы этого приза планируется сделать выплаты всем "открывателям" простых чисел Мерсенна (до $5000 на каждое), авторам программного обеспечения, и авторам новых эффективных алгоритмов поиска (если таковые будут найдены).

Заметим, что текущий рекордсмен M_13466917 содержит чуть более 4000000 десятичных цифр. Таким образом, для достижения планки в 10⁷ цифр, GIMPS надо увеличить "экспоненту" (и соответственно длину числа) в 2.5 раза.

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

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

Эвристические оценки показывают, что в интервале для p от 5255000 до 79300000 ждут своего открытия ещё 4 неизвестных простых числа Мерсенна. Подробную информацию о их возможном распределении, а также об ожидаемых трудозатратах на их нахождение, можно узнать на странице статистики проекта.

5. Наличие клиента под OS/2

До недавнего времени участникам проекта, использующим OS/2, приходилось довольствоваться клиентом древней версии 18.1 датируемой 1999 годом, в то время как версии под другие OS ушли далеко вперёд. Меня это не устраивало. Поэтому, как только появилось достаточно свободного времени, я взялся за портирование последней версии клиента под OS/2. Теперь клиент версии 22.12 под OS/2 доступен для скачивания с официального сайта наряду с клиентами под другие OS.

Как maintainer последних версий SysBar/2 хочу сказать о планах на будущее: планируется добавить к клиенту GIMPS возможность вывода текущего состояния в pipe для удобного отображения в PipeMonitor.

Буду рад любым пожеланиям/багрепортам, касаемым OS/2 версии клиента GIMPS,
Max Alekseyev

Дополнительная информация:

• Дата публикации статьи: 2003-01-13 09:55:31 -- Max Alekseyev
• Материал этой статьи распространяется на условиях лицензии GFDL

Комментарии:

Vladimir Solovyov 2003-01-14 10:37:09	Забавно
Max 2003-01-14 21:22:09	Кстати, вот она же: [url]
Gennady Kudryashoff 2003-01-17 16:36:28	Лучше бы спортировали Globus Toolkit под OS/2. ;-) [url]
Ваpеный 2003-01-18 20:11:18	Полезная штука. Я думаю надо договоpиться с коpпоpацией Сеpенити Системс и встpоить GIMPS/2 клиент в eCS. Пpичем, чтобы он pаботал всегда и пpинудительно, а то вдpуг еще найдутся в миpе идиоты (!) котоpые не захотят искать такие полезные для науки данные. Еще pаз, спасибо автоpу поpта.
шагал 2003-01-18 20:15:04	нихpена ничего не понял! зачем все это?
Max 2003-01-19 00:26:50	"Зачем все это? Лучше бы водки выпили..." (c) из писем Белинского Гоголю
Max 2003-02-06 03:42:11	Новость от проекта GIMPS: завершена двойная проверка чисел меньших M(6972593), чем с большой долей вероятности доказано, что это число является 38-м простым числом Мерсенна. Оригинал тут: [url]'>[e-mail] Соответственно, просьба заменить в статье про GIMPS фразу "На сегодняшний день достоверно известны только первые 37 чисел Мерсенна. Также найдены два больших числа Мерсенна, порядковые номера которых пока не установлены." на фразу "На сегодняшний день достоверно известны только первые 38 чисел Мерсенна. Также найдено большое число Мерсенна, порядковый номер которого пока не установлен."
Max 2003-02-15 12:30:59	Завтра-послезавтра выйдет версия клиента 22.13: New features in Version 22.13 of primeos2 ----------------------------------------- + High Resolution Timer support + Smart detection of running "another copy" - 32-bit TCP/IP stack dependancy removed
bax 2003-02-17 09:17:40	А можно ли сделать такую же фичу, как в RC5-клиенте: отслеживать наличие ppp-соединения? А то ручками посылать результаты ломает как-то.
Max 2003-02-18 05:05:50	bax: вообще-то эта фича там есть - она просто ломиться в инет через определенные промежутки времени, пока не поймает момент наличия соединения. Посмотри внимательно настройки по primeos2 -m
Max 2003-05-28 22:40:32	Версия 23.4: [url]
Max 2006-03-21 23:57:48	Версия 24.14: [url]
Sendy 2006-04-06 16:07:23	Я тоже похожим занимаюсь, но больше привлекает физические и медицинские проекты. подробшей можно посмотреть на [url]
Alex_soldier 2016-06-14 04:34:02	Прошло 13,5 лет, и вот какие результаты появились в проекте GIMPS: В интервале для p от 5255000 до 79300000 оказалось не 4, а целых 10 простых чисел! Причем проверены еще не все претенденты! Номера счастливчиков: 40: 2^20,996,011 -1 41: 2^24,036,583 -1 42: 2^25,964,951 -1 43: 2^30,402,457 -1 44: 2^32,582,657 -1 45: 2^37,156,667 -1 46: 2^42,643,801 -1 47: 2^43,112,609 -1 48: 2^57,885,161 -1 49: 2^74,207,281 -1 Вероятно, проект не развивался бы так динамично, если бы не соперничество команд за места в рейтингах. Всего в проекте более 900 команд, борющихся за позиции в результирующих таблицах. Желающих поучаствовать приглашаю присоединиться к команде GIMPS.Russia - [url]

Прокомментируйте эту статью (напоминаем, автор работал над текстом несколько недель, уважайте мнение других).

Ваше имя: Ваш E-Mail: CODE:
Ваш комментарий:

Каждый пользователь eComStation/Rus может бесплатно зарегистрировать несколько полезных программ (общая стоимость которых > 6000 руб). Дисковые утилиты, программы для интернета, расширители рабочего стола. Нужны ли тебе эти программы?