12.02.2013

Проще некуда

В начале февраля 2013 года математик Кертис Купер, участник проекта распределенных вычислений GIMPS (Great Internet Mersenne Prime Search), обнаружил 48-е простое число Мерсенна. Десятичная запись такого числа состоит из более чем 17 миллионов знаков. Для сравнения, в «Войне и мире» Толстого всего примерно 3,1 миллиона символов. За свое открытие профессор Университета Центрального Миссури вполне может получить три тысячи долларов. Впрочем, он, как и другие участники GIMPS, занимается поиском простых чисел Мерсенна вовсе не ради денег.

Преданья старины глубокой

Числа Мерсенна — это числа вида 2^p—1, где p — произвольное целое число, называемое показателем. Эти числа влекли математиков с древнейших времен, ориентировочно с Евклида (примерно 300 год до нашей эры), правда, до XVI века ученые полагали, что все эти числа простые, то есть делятся только на себя и единицу. Это, конечно же, неверно — достаточно взглянуть на четвертое число Мерсенна: оно равно 15 и представляется в виде произведения 3 и 5.

По-видимому, первым, кто заметил, что не все числа Мерсенна с простыми показателями (известно, что для составных показателей число Мерсенна не может быть простым) являются простыми, был Худальрикус Региус в 1536 году. Он показал, что при p=11 получившееся число — это 2047 — оказывается составным, поскольку представляется в виде произведения 23 и 89.

В XVII веке поиск простых чисел Мерсенна стал довольно популярным среди математиков развлечением. В 1640 году к изучению этих чисел подключился знаменитый Пьер Ферма. Он показал, что работы его предшественников, в которых утверждалась простота чисел для p=23 и p=37, были ошибочны. Но вообще Ферма не был уникален в своем интересе к этому предмету, в истории этих чисел отметились многие известные ученые: Эйлер, Паскаль, Галилео, Гюйгенс.

Имя же свое числа Мерсенна получили в честь французского монаха Марена Мерсенна, философа, теолога и математика. Он наткнулся на эти числа в поисках универсальной формулы, которая позволяла бы перечислять все простые числа. В 1648 году он выпустил труд Cogitata Physica-Mathematica, в котором высказал предположение, что числа вида 2^p — 1 должны быть простыми для показателей 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 и составными для всех остальных целых чисел, не превосходящих 257. Откуда взялась такая гипотеза, доподлинно неизвестно: современники сомневались, что Мерсенн мог разобрать все эти случаи вручную, да и он сам, говорят, это признавал.

Впрочем, эта гипотеза стала популярной уже после смерти автора. Так часто бывает с некоторыми математическими утверждениями — по совершенно непонятной причине они оказываются в центре внимания множества математиков. Возможно, на руку ей сыграла, как и в случае с легендарной теоремой Ферма, простота формулировки. Как бы то ни было, но с рядом Мерсенна ученые разобрались только в середине XX века — тогда они установили, что список показателей, дающих простые числа Мерсенна и не превосходящих 257, выглядит следующим образом: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 и 127. Это и есть первые 12 простых чисел Мерсенна. Кстати, простоту числа Мерсенна для показателя 61 (оно равно 2 305 843 009 213 693 951) доказал российский математик Иван Первушин в 1878 году.

Наше время

Надо сказать, что победе над гипотезой Мерсенна способствовало появление так называемого теста Люка-Лемера. Суть его заключается в следующем: для фиксированного числа Мерсенна вычисляется некоторая рекуррентная последовательность. Рекуррентная формула для членов этой последовательности, во-первых, относительно проста, а во-вторых, для проверки требуется взять p — 2 члена последовательности, где p — нечетный простой показатель числа Мерсенна. Сложность работы алгоритма составляет порядка третьей степени log n, где n — само число Мерсенна. Использование разного рода методов быстрого умножения, как, например, метода Шёнхаге — Штрассена, позволяет немного ускорить работу, однако кардинально сложности не меняет.

Нужно понимать, что это крайне низкая вычислительная сложность, то есть алгоритм работает довольно быстро. Для сравнения, самый быстрый детерминистский алгоритм проверки простоты из существующих — тест Агравала-Каяла-Саксены c улучшениями Померанса-Ленстры — имеет сложность порядка (log n)⁶. Относительную простоту программирования и низкую вычислительную сложность теста Люка-Лемера ученые оценили только с появлением компьютеров.

В 60-е годы прошлого века интерес к числам Мерсенна стал спадать. Связано это было с тем, что перспективы вычислительной техники на тот момент виделись довольно туманными, а использование суперкомпьютеров для поиска больших простых чисел казалось довольно расточительным. В 1968 году в Университете Иллинойса было открыто 23-е простое число Мерсенна с показателем 11213. На тот момент это было настолько великим достижением, что Пол Бейтман, который руководил кафедрой теории чисел в этом университете, заказал специальную печать для корреспонденции, на которой, помимо даты, красовалась надпись «2¹¹²¹³ — 1 — простое число».

В 1970-х годах интерес к числам Мерсенна снова активизировался. Причиной тому стала история двух тогда еще американских школьников — Лауры Никел и Лэндона Нолла. Не особо разбираясь в математических тонкостях вопроса, они написали программу для проверки чисел Мерсенна на простоту с помощью теста Люка-Лемера и прогнали ее на суперкомпьютере в местном университете. В результате они смогли найти 25-е и 26-е простые числа Мерсенна с показателями 21 701 и 23 209 соответственно. Это были самые большие простые числа из известных на тот момент. Нолл после этого стал обладателем еще одного рекорда — в 1989 году он принял участие в открытии самого большого простого числа, которое не является числом Мерсенна (это так называемое простое число Амдала 6, названное так в честь рабочей группы, открывшей его, и равное 391581*2²¹⁶¹⁹³-1).

История с открытием школьников попала на телеэкраны, и поиск простых чисел Мерсенна снова вернулся в моду. Следующие успехи в этой деятельности были связаны с суперкомпьютерами Крэй: один из сотрудников компании-производителя Дэвид Словински написал программу для поиска простых чисел Мерсенна, работавшую на этих машинах, пока они не использовались. Наконец, современный облик этот процесс приобрел при помощи программиста Джорджа Уолтмана, в 1995 году создавшего проект распределенных вычислений GIMPS (Great Internet Mersenne Prime Search).

Проект, предназначенный для работы на i386, к концу первого года существования насчитывал уже более тысячи участников. Это был первый исследовательский проект распределенных вычислений в истории. Первое простое число Мерсенна (в настоящее время в рамках проекта открыто уже 14 штук) стало известно в 1996 году. Сейчас программу, работающую под всеми основными операционными системами, может установить себе любой желающий. Суммарная вычислительная мощность проекта к концу 2012 года составляла уже 95 терафлопс.

48-е по счету и небольшая премия

Самым последним открытием в проекте GIMPS стало обнаружение 48-го простого числа Мерсенна. Это открытие было сделано математиком из Университета Центрального Миссури Кертисом Купером. На прогонку теста Люка-Лемера на одной из машин в университете у Купера ушло 39 дней. Его результат был перепроверен тремя независимыми пользователями, один из которых использовал 32-ядерный сервер, предоставленный компанией Новартис.

Размеры нового числа потрясают — его запись в десятичной системе счисления состоит из 17 425 170 знаков. Для самого же Кертиса это открытие стало уже третьим — ранее самые большие простые числа ему удавалось обнаруживать в 2005 и 2006 годах.

В 2008-м рекорд Кертиса был побит группой исследователей из Калифорнийского университета в Лос-Анджелесе. Они обнаружили простое число Мерсенна, в десятичной записи которого было 12 978 189 знаков. На момент открытия это число было 45-м простым числом Мерсенна, однако спустя некоторое время было открыто еще два простых числа, меньших этого (числа не всегда открываются в порядке возрастания), поэтому его номер в настоящее время — 47. Именно оно до открытия Купера было рекордсменом по размеру.

За открытие GIMPS получил премию в 100 тысяч долларов от фонда EFF, обещанную за открытие первого простого числа, записываемого более чем 10 миллионами знаков. Полученные деньги проект разделил на небольшие премии для поощрения следующих открытий — так, Купер с 48-м числом Мерсенна претендует на три тысячи долларов.

Примечательно, что с числами Мерсенна связано большое количество до сих пор нерешенных задач. К примеру, пока неизвестно, бесконечно ли множество простых чисел Мерсенна. В заключение хочется упомянуть еще про одно замечательное свойство чисел Мерсенна. Число называется совершенным, если оно равно сумме всех своих собственных (то есть положительных и отличных от самого числа) делителей, включая 1. Например, 6 — совершенное, поскольку 6=3+2+1. Еще Евклид обнаружил, что число вида 2ⁿ—1 (2ⁿ—1) совершенно, если в скобках стоит простое число, то есть простое число Мерсенна с показателем n. Позже Леонард Эйлер доказал, что все четные совершенные числа имеют такой вид, где в скобках стоит простое число Мерсенна. На настоящий момент неизвестно ни одного нечетного совершенного числа, однако существуют предположения, что искать такие числа также следует с помощью чисел Мерсенна.

Вместо заключения

У пытливого читателя, разумеется, может возникнуть вопрос, зачем вообще нужен поиск простых чисел Мерсенна. Во-первых, вычислительные нагрузки, стоящие за тем же проектом GIMPS, уже не единожды использовались для тестирования вычислительных мощностей — хорошо известно, что Intel апробировала Pentium II и Pentium Pro именно на GIMPS.

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

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

Андрей Коняев

Источники:

1. Lenta.Ru