Числа Мерсена вызывают интерес у математиков, так как позволяют найти новые, почитаемые еще с античности совершенные числа, т. е. такие, которые равны сумме собственных делителей, кроме себя самого.
Сложность задачи заключается в том, что числа Мерсена найти очень трудно. При всей простоте правил их нахождения приходится перебирать множество вариантов, пока наконец не найдешь хотя бы одно. Причем гарантий, что перебор какого–то массива обязательно приведет к успеху, нет, поскольку неизвестно, бесконечно ли количество чисел Мерсена.
Распределенный поиск таких чисел ведется уже с середины 90–х годов и конца–края ему пока не видно. Хотя в проекте участвуют тысячи математиков–энтузиастов, до сих пор им удалось обнаружить всего 38 таких чисел.
Причем за последние три года было найдено всего лишь два новых...
При всей, казалось бы, практической бесполезности решение громоздких задач из области теории чисел позволило усовершенствовать и отладить схему распределенных вычислений. Заодно это лишний раз доказало тезис Леонарда Эйлера о полезности изучения простых чисел.
«Из всех проблем, рассматриваемых в математике, нет таких, которые бы считались в настоящее время более бесплодными и лишенными приложения, чем проблемы, касающиеся природы чисел и их делителей, – писал ученый в XVIII веке. – В этом отношении нынешние математики отличаются от древних, придававших гораздо большее значение исследованиям такого рода. Кроме того, что отыскание истины само по себе казалось им похвальным и достойным человеческого познания, древние хорошо чувствовали, что при этом замечательным образом развивается изобретательность и перед человеческим разумом открываются новые возможности решать сложные задачи».
«Мастер и работяги»
Основная схема параллельных метакомпьютерных вычислений ныне обычно выглядит так. Разнородные компьютеры связываются между собой по линиям связи. Для всех участников проекта пишется общая программа обеспечения. При этом учитывается, что связь между вычислительными узлами имеет весьма небольшую скорость, неизбежны длительные задержки. Кроме того, компьютеры участников проекта имеют разную скорость, объем памяти, а сами участники проекта имеют неодинаковую квалификацию. Приходится учитывать и тот факт, что какая–то часть участников проекта в какой–то момент может разочароваться в своей деятельности и вообще отключиться от сети.
Кроме того, программное обеспечение для метакомпьютерных вычислений должно быть независимым от операционной системы, выполняться любой из них. Таким образом, приходится готовить различные версии рабочих программ для каждого участника проекта.
Поэтому даже не всякая задача перебора и поиска пригодна для метакомьютинга. Тем не менее такие задачи все же находятся и не только в области теории чисел. Математик Сергей Абрамов как–то заметил, что метакомпьютинг применим для задач, формулируемых моделью "мастер–работяги".
«Мастер» – программа, работающая на корневом сервере. «Работяги» – программы, запускаемые на других машинах через Интернет. «Мастер» делит всю работу на части. По запросу «работяг» он выделяет каждому его часть работы. Те ее выполняют и, отчитавшись перед «мастером», берут следующий кусок. Время от времени кто–то из «работяг» увольняется, уходит в отпуск или заболевает, и тогда взамен ему приходится брать другого работника, обучать его и потом уж давать задание...
Если навалиться сообща...
Переломным для метакомпьютерных вычислений стал 1997 год. В январе одна из компаний, разрабатывающих криптосистемы для рекламы своего нового алгоритма шифрования, предложила всем желающим взломать его, назначив приз в 10 тыс. долларов. Математики знали, что для взлома надо перебрать практически все варианты ключа, а на это требовалось, по расчетам сотрудников фирмы, около 10 тыс. лет при работе на компьютере средней мощности.
Однако поскольку такая задача легко делится на части, то вскоре объявились энтузиасты, которые объединили своих единомышленников в метакомпьютер, поделили между ними работу и в том же году добились успеха. 56–битный ключ удалось найти всего за 250 дней.
Ныне та же команда, объединяющая уже около 200 тыс. участников, трудится над отысканием 64–битного ключа. Общими усилиями уже достигнута скорость перебора 127 млрд ключей в секунду. С такой производительностью полный перебор вариантов можно осуществить за 4 года.