Sancta simplicitas

Очередное большое открытие сделано участниками одного из Интернет-проектов распределенных вычислений. Участниками проекта GIMPS найдено простое число длиною в шесть миллионов цифр.

В мире математики - очередное большое (а лучше - шумное) открытие, сделать которое помогли машины: найдено новое гигантское простое число, записываемое последовательностью из 6.320.430 цифр. Чтобы хоть как-то представить себе эту величину, можно вспомнить, что общее количество атомов во вселенной записывается всего девятью десятками цифр. Героями дня стали 26-летний американский аспирант Майкл Шафер (Michael Shafer, Michigan State University), компьютер которого наткнулся на числовую жемчужину, и проект распределённых вычислений Great Internet Mersenne Prime Search (GIMPS), что примерно переводится как Большой Интернет-поиск чисел Мерсенна.

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

Несмотря на то, что установить общую зависимость распределения простых чисел наука пока не смогла, есть несколько частных случаев, приближённо (с большой долей вероятности) их определяющих. Именно таким частным случаем и является зависимость Мерсенна. Саму идею две тысячи лет назад подсказал Эвклид, а много позже, в 17-м веке, чётко сформулировал французский монах Марен Мерсенн. Суть её сводится к предположению, что число, описываемое формулой 2^P-1, где P - простое, также будет простым. Правило это выполняется не всегда, но всё же позволяет сэкономить время на поиски гигантских простых чисел (именно поиску чисел Мерсенна посвящён проект GIMPS). Всего до настоящего момента чисел Мерсенна было известно только 39. И легко понять тот восторг, с которым было встречено сообщение руководителей GIMPS об открытии очередного представителя этой последовательности. Число, простоту которого подтвердил компьютер Майкла Шафера, стало 40-м по счёту из известных чисел Мерсенна и может быть записано следующим образом: 2^20996011-1.

Конечно, несмотря на сравнительную "простоту", поиск чисел Мерсенна требует фантастических вычислительных затрат. Проект GIMPS - самый крупный пример организации работ такого рода: в нём принимают участие свыше 60 тысяч человек, а программа-клиент, перебирающая варианты, работает на 210 тысячах машин по всему миру. Интенсивность вычислений столь высока, что начинают проявляться мельчайшие дефекты компьютерной техники и, согласно официальной статистике проекта, около 2% его первичных результатов оказываются ошибочными. Это, кстати, объясняет, почему сообщение об открытии 40-го числа было сделано только вчера, хоть Шафер увидел его на экране своей машины ещё 17 ноября: две недели были потрачены на проверку результата. Предыдущее число Мерсенна было найдено два года назад также участником GIMPS.

Что даст открытие нового числа Мерсенна нам? Увы, ничего значительного: как и в случае c SETI@Home, какой-то большой практической отдачи от такого открытия не предвидится. К пониманию принципа распределения простых чисел нынешнее открытие науку также не приближает. Для участников поиска ведущаяся работа - шанс получить награду, назначенную за нахождение простого числа длиною в 10 миллионов цифр или больше: 100 тысяч долларов от Electronic Frontier Foundation ждут своего хозяина. Впрочем, следует трезво оценивать свои силы. 39-е число Мерсенна состояло из 4 миллионов цифр, 40-е (два года на поиск) из 6-ти, так что вручение приза вряд ли состоится раньше чем через пару-тройку лет. Но нельзя сбрасывать со счетов и возможность вписать своё имя в историю. Присоединяйтесь, чисел хватит на всех!