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

Простое число Мерсенна — это простое число, которое может быть представлено в виде \( M_p = 2^p - 1 \), где \( p \) — также простое число. Названы в честь французского математика, философа и монаха-минима Мари Мерсенна, который в XVII веке изучал числа такого вида. Простые числа Мерсенна являются подмножеством чисел Мерсенна — чисел вида \( 2^n - 1 \), где \( n \) — натуральное число. Они играют ключевую роль в теории чисел, криптографии и поиске самых больших известных простых чисел, так как существуют эффективные тесты простоты (в частности, тест Люка — Лемера), позволяющие проверять числа Мерсенна на простоту быстрее, чем произвольные числа сопоставимого размера.

История

Ранние исследования

Числа вида \( 2^n - 1 \) были известны ещё в античности. Древнегреческий математик Евклид в своих «Началах» (около 300 г. до н. э.) доказал, что если \( 2^n - 1 \) является простым, то число \( 2^{n-1} (2^n - 1) \) является совершенным (равным сумме своих собственных делителей). Это утверждение, известное как теорема Евклида — Эйлера, установило прямую связь между простыми числами Мерсенна и чётными совершенными числами.

В средние века числа Мерсенна изучались редко. В 1536 году итальянский математик Пьетро Катальди показал, что \( 2^{11} - 1 = 2047 \) не является простым (оно равно \( 23 \times 89 \)), опровергнув распространённое в то время мнение, что все числа вида \( 2^p - 1 \) при простом \( p \) просты.

Вклад Мари Мерсенна

В 1644 году Мари Мерсенн опубликовал труд «Cogitata Physica-Mathematica», в котором утверждал, что для \( p \le 257 \) числа \( 2^p - 1 \) являются простыми только при \( p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 \). Это утверждение оказалось ошибочным: впоследствии было обнаружено, что \( M_{67} \) и \( M_{257} \) составные, а \( M_{61} \), \( M_{89} \) и \( M_{107} \), не включённые в список, на самом деле просты. Тем не менее, работа Мерсенна стимулировала интерес к числам этого типа, и они получили его имя.

Поиск в XIX—XX веках

В XIX веке были найдены новые простые числа Мерсенна. В 1876 году французский математик Эдуард Люка разработал тест для проверки простоты чисел Мерсенна, который позже был усовершенствован Дерриком Лемером и стал известен как тест Люка — Лемера. С помощью этого теста Люка вручную доказал простоту \( M_{127} \), которое оставалось самым большим известным простым числом до 1952 года.

С появлением компьютеров в середине XX века поиск простых чисел Мерсенна резко ускорился. В 1952 году Рафаэль Робинсон с помощью компьютера SWAC нашёл \( M_{521} \), \( M_{607} \), \( M_{1279} \), \( M_{2203} \) и \( M_{2281} \). С тех пор все новые простые числа Мерсенна находятся исключительно с помощью вычислительной техники.

Современный этап: GIMPS

В 1996 году американский программист Джордж Вольтман основал проект Great Internet Mersenne Prime Search (GIMPS) — распределённый вычислительный проект, в котором добровольцы со всего мира предоставляют вычислительные ресурсы своих компьютеров для поиска простых чисел Мерсенна. GIMPS использует тест Люка — Лемера и его оптимизированные версии. На 2025 год проект обнаружил 18 новых простых чисел Мерсенна, включая самое большое из известных на сегодняшний день — \( M_{82589933} \), найденное 7 декабря 2018 года. Это число содержит 24 862 048 десятичных цифр.

Определение и свойства

Формальное определение

Числом Мерсенна называется число вида \( M_n = 2^n - 1 \), где \( n \) — натуральное число. Если \( n \) — составное, то \( M_n \) также составное, так как \( 2^{ab} - 1 \) делится на \( 2^a - 1 \) и \( 2^b - 1 \). Поэтому для того, чтобы \( M_n \) было простым, необходимо, чтобы \( n \) было простым. Однако обратное неверно: не все числа \( M_p \) при простом \( p \) просты. Например, \( M_{11} = 2047 = 23 \times 89 \).

Необходимое и достаточное условие

Простые числа Мерсенна — это числа \( M_p = 2^p - 1 \), которые являются простыми. Для их проверки используется тест Люка — Лемера, который является необходимым и достаточным условием простоты для чисел Мерсенна.

Связь с совершенными числами

Как упоминалось выше, каждое простое число Мерсенна \( M_p \) порождает чётное совершенное число \( 2^{p-1} (2^p - 1) \). Обратно, любое чётное совершенное число имеет такой вид. Таким образом, поиск новых простых чисел Мерсенна эквивалентен поиску новых чётных совершенных чисел. На 2025 год известно 51 простое число Мерсенна и, соответственно, 51 чётное совершенное число. Вопрос о существовании нечётных совершенных чисел остаётся открытым.

Классификация и известные примеры

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

Первые несколько простых чисел Мерсенна (с указанием \( p \)):

Самые большие известные простые числа Мерсенна

На 2025 год самым большим известным простым числом Мерсенна является \( M_{82589933} \), открытое в 2018 году. Предыдущие рекорды:

• \( M_{57885161} \) (17 425 170 цифр) — открыто в 2013 году.
• \( M_{74207281} \) (22 338 618 цифр) — открыто в 2016 году.
• \( M_{77232917} \) (23 249 425 цифр) — открыто в 2017 году.

Все эти числа были найдены в рамках проекта GIMPS.

Тест Люка — Лемера

Тест Люка — Лемера является основным методом проверки простоты чисел Мерсенна. Он работает следующим образом:

1. Пусть \( p \) — нечётное простое число.
2. Определим последовательность \( S_k \) рекуррентно: \( S_0 = 4 \), \( S_{k+1} = S_k^2 - 2 \mod M_p \).
3. Число \( M_p \) является простым тогда и только тогда, когда \( S_{p-2} \equiv 0 \pmod{M_p} \).

Этот тест очень эффективен, так как требует \( O(p) \) операций, каждая из которых — умножение больших чисел. Благодаря использованию быстрого преобразования Фурье (FFT) для умножения, тест может быть выполнен за время \( O(p \log p \log \log p) \).

Применение

Криптография

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

Вычислительные проекты

Поиск простых чисел Мерсенна является популярной задачей для распределённых вычислений. Проект GIMPS привлёк тысячи добровольцев и способствовал развитию алгоритмов для работы с большими числами и тестированию аппаратного обеспечения.

Математические исследования

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

Гипотезы и открытые вопросы

• Бесконечность простых чисел Мерсенна: неизвестно, существует ли бесконечно много простых чисел Мерсенна. Большинство математиков склоняются к положительному ответу, но доказательства нет.
• Распределение: предполагается, что количество простых чисел Мерсенна с показателем \( p \le x \) асимптотически равно \( \frac{\log x}{\log 2} \), но это не доказано.
• Простые числа Мерсенна и совершенные числа: все известные чётные совершенные числа соответствуют простым числам Мерсенна. Вопрос о существовании нечётных совершенных чисел остаётся открытым.

Интересные факты

• Самое маленькое простое число Мерсенна, не являющееся очевидным (то есть большее 31), — \( M_{13} = 8191 \). Оно было известно ещё в XV веке.
• В 2018 году за открытие \( M_{82589933} \) проект GIMPS выплатил премию в размере 3000 долларов США (в рамках программы Electronic Frontier Foundation за нахождение простого числа с более чем 100 миллионами цифр, хотя эта премия была меньше заявленной из-за неполного соответствия условиям).
• Числа Мерсенна тесно связаны с так называемыми «простыми числами Ферма» (\( 2^{2^n} + 1 \)), но в отличие от них, для чисел Мерсенна известно много примеров, и они являются основным источником рекордно больших простых чисел.

Источники

• Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — 3-е изд. — М.: Вильямс, 2007.
• Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998.
• Caldwell C. K. «Mersenne Primes: History, Theorems and Lists» — сайт Prime Pages.
• Woltman G. «Great Internet Mersenne Prime Search» — официальная документация проекта GIMPS.
• Weisstein E. W. «Mersenne Prime» — MathWorld.