Новый рекорд: найдено самое большое простое число Мерсенна
Можете ли вы себе представить число, запись которого в 10 раз длиннее всей «Войны и мира» Льва Толстого? А ведь именно такой размер имеет недавно найденное 50-е по счету простое число Мерсенна. Это математическое открытие потрясло умы ученых и заставило мир в очередной раз удивиться таинственной природе чисел.
Что такое числа Мерсенна
Числа Мерсенна — это особый класс чисел, определяемый по следующей формуле: Mp = 2p - 1, где p — натуральное число. Например, если взять p = 3, то получится число Мерсенна M3 = 23 - 1 = 7. А при p = 5 имеем M5 = 25 - 1 = 31.
Среди всех чисел Мерсенна особое значение имеют простые числа Мерсенна. Простым называется число, которое делится только на 1 и на само себя, не имея других делителей. Например, 7 — простое число, а 6 — составное, так как 6 = 2 × 3.
Простые числа Мерсенна обладают уникальными свойствами и широко используются в криптографии для генерации случайных чисел, а также при тестировании быстродействия компьютеров.
Почему важно искать простые числа Мерсенна
Хотя на первый взгляд поиск все больших простых чисел Мерсенна может показаться бесполезным занятием, на самом деле это не так. Вот несколько причин, почему ученые уделяют этому так много внимания:
- Помогает развитию теории чисел, открывая новые неизвестные закономерности
- Используется для тестирования производительности компьютеров и оптимизации алгоритмов
- Применяется в криптографии для генерации случайных чисел и шифрования данных
Кроме того, подобные математические «головоломки» стимулируют интерес общества к науке и привлекают молодежь в эту сферу. Участие в поиске рекордных простых чисел Мерсенна – это возможность внести посильный вклад в прогресс математики и информатики.
История открытия чисел Мерсенна
Впервые о числах такого вида упомянул в 1644 году французский монах Марен Мерсенн. Отсюда и пошло название – числа Мерсенна.
Изначально Мерсенн выдвинул гипотезу, что числа вида 2p - 1 должны быть простыми при определенных значениях p. Однако в дальнейшем выяснилось, что эта гипотеза верна не для всех p.
Поиском простых чисел Мерсенна в разное время занимались такие известные математики, как Леонард Эйлер, Пьер Ферма, Бернхард Риман и другие. Немало было сделано и для развития теории этих чисел российскими учеными Николаем Ивановичем Лобачевским и Пафнутием Львовичем Чебышевым.
Этапы открытия простых чисел Мерсенна
Вот основные вехи в истории поиска все более высоких простых чисел Мерсенна:
- 1644 г. - Мерсенн выдвигает гипотезу о простых числах такого вида
- 1876 г. - найдено простое Мерсенна при p = 61 (Иван Первушин)
- 1952 г. - с помощью ЭВМ найдено простое число Мерсенна при p = 127
- 1996 г. - запуск проекта GIMPS по распределенным вычислениям для поиска таких чисел
- 2016 г. - найден рекордный на то время Мерсенн при p = 74207281
- 2017 г. - новый рекорд при p = 77232917, длина записи 23 млн цифр
Как видно, благодаря распределенным вычислениям и мощности современных компьютеров темп открытия новых простых Мерсенна резко возрос в последние десятилетия.
Проект GIMPS и поиск рекордного Мерсенна
В 1995 году был запущен проект GIMPS (Great Internet Mersenne Prime Search) - это первый в истории исследовательский проект распределенных вычислений. Любой желающий может помочь в поиске новых простых чисел Мерсенна, установив программу Prime95 и таким образом находить числа Мерсенна исследовательская работа.
Суть этой программы в том, что она использует процессор вашего компьютера (или смартфона), когда он простаивает, для перебора вариантов и проверки чисел Мерсенна на простоту при помощи теста Люка-Лемера.
Как работает тест Люка-Лемера
Для проверки чисел Мерсенна на простоту используется эффективный алгоритм, предложенный в 1970-х годах Джоном Люком и Эдсгером Дейкстрой. Суть его работы заключается в следующем:
- Для данного числа Мерсенна вычисляется рекуррентная последовательность по специальной формуле
- Берутся первые p-2 члена этой последовательности и проверяется последний из них
- Если последний член равен нулю, то число Мерсенна является простым
Преимущество этого метода в том, что он имеет относительно невысокую вычислительную сложность - порядка O(p3). Это позволяет тестировать очень большие числа Мерсенна.
Роль суперкомпьютеров в поиске
С момента изобретения электронно-вычислительных машин (ЭВМ) они активно стали применяться и для поиска простых чисел Мерсенна. Первые рекорды были установлены именно на суперкомпьютерах.
Однако со временем выяснилось, что даже самые мощные суперкомпьютеры не могут конкурировать с объединенной вычислительной мощностью миллионов персональных компьютеров обычных людей. Поэтому сейчас большинство рекордов устанавливается в рамках проекта GIMPS.
Почему числа Мерсенна так велики
Возникает вопрос - почему при поиске простых чисел Мерсенна возникает «гонка за размером» и каждый новый рекорд на порядки больше предыдущего?
Ответ кроется в особенностях распределения простых чисел среди натурального ряда. Чем больше число, тем реже встречаются простые числа. А для чисел Мерсенна эта закономерность проявляется еще сильнее.
Поэтому для нахождения очередного простого Мерсенна приходится перебирать все более высокие степени числа 2, что и приводит к таким гигантским значениям.
Использование чисел Мерсенна на практике
Несмотря на кажущуюся абстрактность, простые числа Мерсенна находят вполне конкретное применение в различных областях:
- Криптография и защита информации
- Генераторы псевдослучайных чисел
- Тестирование и бенчмарк производительности компьютеров
Например, простые Мерсенна лежат в основе одного из самых быстрых алгоритмов генерации случайных чисел - генератора Мерсенна Twister. А их поиск часто используется для тестирования новых поколений процессоров.
Перспективы дальнейшего поиска
Несмотря на последние рекорды, пока не найден ответ на вопрос - существует ли вообще бесконечно много простых чисел Мерсенна или их количество ограниченно.
Также неизвестно, как именно распределены эти числа среди степеней числа 2. Возможно, есть какие-то неочевидные закономерности, которые помогут значительно ускорить их поиск в будущем.