Самое длинное простое число Мерсенна состоит из 22 миллионов цифр

Cамое большое известное простое число теперь состоит из 17 425 170 цифр.

Широкомасштабный проект добровольных вычислений по поиску простых чисел Мерсенна (GIMPS) отметил свою 20-ю годовщину открытием самого большого из известных на данный момент простых чисел 2^{74 207 281} — 1. Кертис Купер, один из многих тысяч добровольцев программы GIMPS, использовал для работы один из компьютеров своего Университета Сентрал Миссури, чтобы сделать данное открытие.

Простое число, получившее название M74207281, было высчитано путем умножения 74 207 281 двоек и вычитания единицы. Получившееся число содержит 22 338 618 цифр, что почти на 5 миллионов цифр больше, чем было у числа, державшего предыдущий рекорд самого длинного простого числа.

Несмотря на то, что использование простых чисел очень часто встречается, например в криптографии, полученное самое длинное простое число, вероятнее всего, слишком большое, чтобы иметь практическую значимость. Однако сам поиск числа принес ученым немало практической пользы. Исторически сложилось, что поиск простых чисел Мерсенна использовался в качестве проверки компьютерного оборудования. Ранее в этом месяце благодаря программному обеспечению GIMPS prime95 члены немецкого компьютерного сообщества обнаружили некоторый дефект у новейших процессоров Intel Skylake, на базе которых группа проводила данное исследование. Примечательно, что аналогичные аппаратные проблемы были обнаружены и во многих других частных персональных компьютерах, которые также принимали участие в вычислениях.

Чтобы доказать, что в основном вычислительном процессе никаких ошибок не было, простое число было проанализировано разными программами на разном компьютерном оборудовании. Андреас Хоглунд и Дэвид Стэнфилл провели анализ, используя программное обеспечение CUDALucas для графических процессоров NVIDIA Titan. Помимо этого, Дэвид Стэнфилл провел анализ числа с помощью ПО ClLucas для графических чипов AMD Fury. Последний тест проводил Сердж Баталов, на программном обеспечении MLucas, работающем на 18-ядерном сервере.

Для доктора Купера, профессора Университета Сентрал Миссури, найденное столь длинное простое число является четвертым. Первое было высчитано в 2005 году, после чего в 2006 году последовало открытие второго. Число Купера утратило рекордное значение в 2008 году, однако обнаруженное в 2013 году новое число вернуло ему пальму первенства. Что интересно, самое длинное на сегодняшний момент простое число было обнаружено еще 17 сентября 2015 года, однако потребовалось 127 дней только для того, чтобы доказать, что перед ученым находится действительно что-то стоящее. Анализ проводился с помощью персонального компьютера на базе процессора Intel I7-4790.

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

Новое простое число относится к натуральным числам Мерсенна, названным в честь французского математика Марена Мерсенна, исследовавшего их свойства в 17 веке. В настоящий момент известно лишь 49 чисел Мерсенна. С момента основания GIMPS в 1996 году было обнаружено только 15 таких чисел.

Простые числа Мерсенна

В течение нескольких столетий шла погоня за простыми числами. Многие математики боролись за честь стать открывателем самого большого из известных простых чисел. Разумеется, можно было бы выбрать несколько очень больших чисел, не имеющих таких очевидных делителей, как 2, 3, 5, 7, и проверить, являются ли они простыми числами. Этот способ, как мы вскоре убедимся, не очень эффективен. Теперь эта погоня утихла, она идет только в одном направлении, оказавшемся удачным.

Простые числа Мерсенна являются простыми числами специального вида

М_р = 2^p - 1, (2.2.1)

где р — другое простое число. Эти числа вошли в математику давно, они появляются еще в евклидовых размышлениях о совершенных числах, которые мы рассмотрим позже. Свое название они получили в честь французского монаха Мерена Мерсенна (1588–1648), который много занимался проблемой совершенных чисел.

Если начать вычислять числа (2.2.1) для различных простых чисел р, то видно, что не все они оказываются простыми. Например,

М₂ = 2² — 1 = 3 = простое,

М₃ = 2³ — 1 = 7 = простое,

М₅ = 2⁵ — 1 = 31 = простое,

М₇ = 2⁷ — 1 = 127 = простое,

М₁₁ = 2¹¹ — 1 = 2047 = 23 89.

Общий способ нахождения больших простых чисел Мерсенна состоит в проверке всех чисел М_p для различных простых чисел р.

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

В исследовании чисел Мерсенна можно выделить раннюю стадию, достигшую своей кульминации в 1750 году, когда Леонард Эйлер[5] установил, что число М₃₁ является простым. К этому времени было найдено восемь простых чисел Мерсенна, соответствующих значениям

р = 2, р = 3, р = 5, р = 7, р = 13, р = 17, p = 19, р = 31.

Эйлерово число M₃₁ оставалось самым большим из известных простых чисел более ста лет. В 1876 году французский математик Лукас установил, что огромное число

М₁₂₇ = 170141183460469231731687303715884105727

является простым числом. Ну и число! С 39 цифрами. Простые числа Мерсенна, меньшие этого числа, задаются значениями р, указанными выше, а также значениями

р = 61, р = 89, р = 107.

Эти 12 простых чисел Мерсенна были вычислены с помощью только карандаша и бумаги, а для вычисления следующих уже использовались механические настольные счетные машины. Появление вычислительных машин с электрическим приводом позволило продолжить поиски, доведя их до р = 257. Однако результаты были неутешительными, среди них не оказалось новых простых чисел Мерсенна.

Затем задача была переложена на плечи ЭВМ. Создание все более высокопроизводительных ЭВМ дало возможность продолжить поиск новых простых чисел Мерсенна. Д. X. Лемер установил, что значения

р = 521, р = 607, р = 1279, р = 2203, р = 2281

дают простые числа Мерсенна. Дальнейшие поиски также увенчались успехом. Ризель (1958) показал, что

р = 3217,

дает простое число Мерсенна, а Гурвиц (1962) нашёл еще два таких значения:

р = 4253, р = 4423.

Огромного успеха добился Гиллельс (1964), который нашел простые числа Мерсенна, соответствующие значениям

р = 9689, р = 9941, р = 11213.

Итак, общий урожай составил 23 простых числа Мерсенна, и, так как мощности ЭВМ продолжают увеличиваться, мы надеемся на дальнейший успех. Простое число Лукаса М₁₂₇, как мы уже упоминали, имеет 39 цифр. Даже вычисление самого большого из известных простых чисел, числа M₁₁₂₁₃, является довольно сложной задачей и, по-видимому, нет смысла воспроизводить здесь это число. Если же мы захотим узнать, сколько цифр содержит это число, то мы можем сделать это, не вычисляя самого числа.

Вместо нахождения количества цифр числа М_р = 2^p — 1 рассмотрим эту задачу для числа М^р+ 1 = 2^р.

Эти два числа имеют одинаковое количество цифр, так как если бы число М^р + 1 имело на одну цифру больше, то оно должно было бы оканчиваться на 0. Но это невозможно ни для какой степени числа 2, что видно из ряда

2, 4, 8, 16, 32, 64, 128, 266….

в котором последняя цифра в каждом числе может быть только одним из чисел

2, 4, 8, 6.

Чтобы найти количество цифр числа 2^p, вспомним, что Ig 2^p = p lg 2. Из таблиц находим, что Ig 2 приближенно равняется 0,30103, откуда

lg 2^p = p lg 2 = р • 0,30103.

Для р = 11213 получаем

lg 2¹¹²¹³ = 3375,449…,

и так как характеристика этого числа равна 3375, то мы приходим к выводу, что число 2^pимеет 3376 цифр.

Итак, мы можем сказать следующее.

Самое большое известное в настоящее время простое число имеет 3376 цифр. (Здесь слова «в настоящее время» имеют существенное значение.) Это число было найдено на ЭВМ Иллинойского университета (США). Математический факультет этого университета был так горд своим достижением, что изобразил это число на своем почтовом штемпеле, таким образом воспроизводя его на каждом отсылаемом письме, для всеобщего восхищения.