2001-12-17 11:21:18

20-летний житель Оуэн-Саунда (Канада), работая за своим домашним компьютером, нашел самое большое из известных простых чисел. Правда, работал он не один. Его система входила в раскинувшийся на весь мир квазисуперкомпьютер, объединяющий 210 тыс. машин.
Майкл Камерон (Michael Cameron) нашел новое простое число 14 ноября, пользуясь компьютером с 800-МГц процессором AMD, сообщает сайт Entropia. Эта компания из Сан-Диего продает ПО для «распределенных вычислений», которое концентрирует неиспользованные вычислительные ресурсы компьютеров, разбросанных по всему интернету.

Появление материального стимула изменило лицо распределенных вычислений, однако корнями они уходят в такие чисто академические проекты, как поиск оптимальных линеек Голомба или радиосигналов из других миров.

Хотя число обнаружил компьютер Камерона, честь открытия принадлежит троим: Джордж Уолтман (George Woltman) основал проект Great Internet Mersenne Prime Search (GIMPS) и написал ПО поиска, а учредитель Entropia Скотт Куровски (Scott Kurowski) создал сетевую систему PrimeNet, управляющую 210 тыс. компьютеров, которые принимали участие в решении задачи.

Простые числа (когда-то они рассматривались как математический курьез, а теперь составляют основу криптографии) — это числа больше единицы, которые делятся только на единицу и на самих себя. Камерон — участник проекта по поиску простого числа особого рода, называемого простым числом Мерсенна.

В числе, которое обнаружил Камерон (213 466 917-1), 4 053 946 цифр. Чтобы изобразить его на постере размером 74 х 102 см (такие постеры продает Perfectly Scientific), это число пришлось набрать мельчайшим шрифтом в 1,37 пункта, рассмотреть который можно только в лупу.

Простые числа Мерсенна названы так в честь французского монаха Марена Мерсенна, родившегося в 1588 году, который исследовал простые числа вида (2p-1), где p — обычное простое число. Такие числа встречаются гораздо реже обычных простых чисел. Проект GIMPS вплотную занимается их поиском с 1996 года, и среди его достижений пять последних примеров. Всего на сегодняшний день известно 39 примеров. Чтобы убедиться, что это простое число Мерсенна, компьютеру Камерона потребовалось 42 дня. Затем ученые подтвердили это на рабочей станции за три недели.

Простые числа используются в системах шифрования данных, таких как технология Secure Sockets Layer (SSL), используемая веб-браузером. Как правило, в них применяются числа, содержащие не более 300 цифр. «Практической пользы от больших простых чисел Мерсенна не много, но такая находка может принести человеку 15 минут славы», — говорит математик из Стэнфордского университета Дэн Боне (Dan Boneh). Математики-энтузиасты представили онлайновые версии числа Камерона, записанные десятичными цифрами и словами.

Поиск простых чисел Мерсенна требует огромных вычислительных ресурсов, но это так называемая «существенно параллельная» задача: ее легко разбить на независимые части, решаемые отдельными компьютерами. Многие задачи, напротив, требуют высокоскоростного обмена данными или пошагового решения — в этом случае возможность распределения вычислений между многими системами значительно затрудняется.

Методом параллельных вычислений решаются не только академические задачи. Sun Microsystems и Intel используют распределенное ПО для проектирования микропроцессоров, а в таких компаниях, как Entropia, Turbolinux, Platform Computing, Parabon Computation и United Devices, имеется ПО, которое можно использовать для исследований в области генетики, фармацевтики или финансовых услуг. Обычно такое ПО используется в пределах одной корпорации, а не на компьютерах случайных людей, разбросанных по всему интернету.

Концепция распределенных вычислений близка к концепции сетевых (grid) вычислений, когда компьютеры и системы хранения данных объединяются в единый пул ресурсов. Исследованиями в этой области занимается, например, Национальный фонд науки, который вложил в одну такую сеть 53 млн $. Entropia, IBM, Sun, Platform Computing и другие компании сотрудничают с проектом open-source Globus Project, работая над стандартами и ПО для создания управляемых сетей вычислительных ресурсов.

Ученые надеются, что когда-нибудь все компьютеры в мире будут объединены в один гигантский ресурс. Проект поиска простых чисел Мерсенна — шаг в этом направлении. Каждый день сеть выполняет работу, над которой ПК с процессором Pentium 90 МГц трудился бы 200 лет. В среднем эта сеть производит 2,4 трлн операций в секунду. Наиболее популярная модель компьютера-охотника за простыми числами — система Intel Pentium III; за ней с небольшим отрывом следует ПК на базе AMD Athlon.

Хотя проект добровольный, для участия в нем есть и материальный стимул. Организация Electronic Frontier Foundation выплатила участнику GIMPS Найану Хэйратвала (Nayan Hajratwala) из Плимута (штат Мичиган) 50 тыс. $ за открытие первого простого числа, содержащего более миллиона цифр. Организация, существующая на частные пожертвования, предлагает 100 тыс. $ за первое простое число с 10 млн цифр, 150 тыс. $ за первое простое число со 100 млн цифр и 250 тыс. $ за первое простое число с миллиардом цифр.

Сейчас ученые ищут 40-е число Мерсенна. ПО для решения этой задачи можно загрузить с веб-сайта Мерсенна.

ZDNet