50-ое простое число Мерсенна

07.01.2018

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

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

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

3 января 2018 года стало известно, что компьютер американского инженера Джонатана Пейса (Jonathan Pace) нашел 50-е простое число Мерсенна. Это самое большое из известных на данный момент простых чисел, его длина превышает 23 миллиона символов, сообщается на сайте проекта распределенных вычислений GIMPS.

Широкомасштабный интернет-проект по поиску простых чисел Мерсенна (GIMPS — Great Internet Mersenne Prime Search) начался по инициативе Джорджа Вольтмана и использует сеть соединенных через интернет персональных компьютеров добровольцев (любой желающий может зарегистрироваться). Эти компьютеры работают параллельно и в совокупности представляют собой вычислительные мощности, превосходящие возможности любого суперкомпьютера. Каждый доброволец устанавливает соответствующее программное обеспечение, и его компьютер выполняет вычисления в периоды простоя. Проект был запущен в 1997 г., а к августу 2009 г. было найдено в общей сложности 12 новых простых чисел Мерсенна. Суммарная вычислительная мощность проекта составляла уже 324 терафлопс. Для того, чтобы присоединится к проекту, нужно установить программу Prime95 (доступна для разных операционных систем).

Числами Мерсенна называются числа вида 2^P-1 (здесь ^ - возведение в степень). Среди них встречаются как простые так и составные числа. Показатель p в найденном 50-м простом числе Мерсенна составляет 77232917, а десятичная запись числа 2^77232917-1 содержит 23 249 425 цифр. Это на 910 тысяч знаков длиннее, чем 49-е простое число Мерсенна, и длиннее, чем девять романов «Война и мир» без пробелов.

На подтверждение того, что 2^77232917-1 является простым, у компьютера с процессором Intel i5-6600 ушло шесть дней вычислений. Открытие нового самого большого простого числа уже подтвердили четыре других участника проекта на четырех различных платформах с разным программным обеспечением.