Сорок мегабайт простоты

Привет, Хабр!

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

Без лишних предисловий - спустя шесть лет после предыдущего, найдено 52-ое известное простое число Мерсенна!

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

Было доказано, что такие числа иногда, весьма редко, бывают простые - и в этом случае экспонента (та самая степень двойки) непременно тоже представляет собой простое число. До середины прошлого века поиск таких чисел был довольно вялым, но с появлением ЭВМ, понятное дело, рванул вперёд - в первую очередь, конечно же, благодаря наличию алгоритма поиска с полиномиальной сложностью.

С тех пор простые числа Мерсенна (ПЧМ) удерживают практически весь пьедестал почёта самых больших известных простых чисел.

Чтобы вы понимали, о каких размерах идёт речь. Современная криптография оперирует простыми или псевдопростыми числами длиной в сотни и тысячи бит, текущий же фронт работ по поиску простых чисел Мерсенна располагается в окрестностях вот такого:

Каждый кандидат на простоту, на текущий момент - это число длиной более 40 000 000 (сорока миллионов) десятичных цифр, для проверки которого требуется около суток работы мощной видеокарты или несколько дней на "обычном" серверном CPU.

Проверка первого найденного совместными усилиями проекта GIMPS простого числа Мерсенна, M(1 398 269), занимала 0.05 гигагерце-дней (внутренняя условная единица GIMPS, примерно равная работе одного 1GHz ядра Pentium 4 за сутки). Это было в 1996 году. Последнее найденное ПЧМ, M(136 279 841) "весит" уже 759 ГГц*дней. Можете посмотреть на первые цифры или скачать архив с полной версией вот тут.

Получается, что за 28 лет сложность вычислений выросла на четыре порядка, неслабо так обогнав закон Мура.

Однако, GIMPS не только не унывает, но и наоборот - наращивает обороты. За последние 10 лет, помимо естественного появления всё более производительных CPU и GPU, были совершены и качественные скачки. Совместными усилиями математиков и программистов, при моральной поддержке обычных участников проекта вроде меня, реализованы новые алгоритмы:

• Вероятностный тест Миллера-Рабина, также известный как PRP.

• Метод коррекции ошибок Роберта Гербикса, снизивший практически до нуля вероятность аппаратной ошибки при вычислениях.

• Использование VDF, "Verifiable Delay Function", благодаря которой стало возможным отказаться от "тяжёлых" проверочных тестов и, фактически, удвоить общую производительность проекта.

Шесть лет ожиданий снова вознаграждены (поскольку это уже третье ПЧМ, которое я застал с момента присоединения к проекту), можно выдохнуть, продуть вентиляторы от пыли... и устремиться дальше по этой бесконечной (не доказано!) дороге к следующему огроменному и практически бесполезному в повседневной жизни числу.

Само собой, приглашаю присоединиться к нашей вакханалии, благо — это совсем не сложно. Будем греть атмосферу вместе.