[Перевод] Простые числа Мерсенна и тест Люка-Лемера25.04.2017 20:48

Перевод поста Джона Макги (John McGee) «Mersenne Primes and the Lucas–Lehmer Test».
Код, приведенный в статье, можно скачать здесь.
Выражаю огромную благодарность Полине Сологуб за помощь в переводе и подготовке публикации

Содержание

— Введение.
— Теорема множителей Эйлера и Мерсенна
— Люка и Лемер
— От ${M_{13}}$ до ${M_{20}}$
— Совершенные числа
— 21-е, 22-е и 23-е числа Мерсенна
— 24-е, 25-е и 26-е числа Мерсенна.
— 27-е и 28-е числа Мерсенна
— 29-е число Мерсенна
— 30-е и 31-е числа Мерсенна
— Великий интернет-поиск чисел Мерсенна
— Факторизация чисел Мерсенна

Введение.

Простое число Мерсенна — простое число вида ${M_p} = {2^p} - 1$ (значение степени р также должно быть простым). Эти простые числа получили свое название от имени французского математика и религиозного ученого Мерсенна, который и составил данный список простых чисел этой формы в первой половине семнадцатого века. Первые четыре из них были известны уже давно: ${M_2} = 3$ , ${M_3} = 7$ , ${M_5} = 31$ и ${M_7} = 127$ .

Мерсенн утверждал, что значение ${2^p} - 1$ будет простым для простых чисел $p \leqslant 257$ , принадлежащих множеству $p \in \left\{ {{\text{2}}{\text{,3}}{\text{,5}}{\text{,7}}{\text{,13}}{\text{,17}}{\text{,19}}{\text{,31}}{\text{,67}}{\text{,127}}{\text{,257}}} \right\}$ . Во всем ли он был прав, можно проверить с помощью функции Wolfram Language — PrimeQ, в которой используются современные методы тестирования чисел на простоту, для которых не требуется поиска конкретного множителя, чтобы доказать, что число составное.

Вполне возможно, что его утверждение о том, что ${M_{67}}$ — простое число, просто опечатка, и на самом деле он имел в виду ${M_{61}}$ . Несложно понять, что проверка на простоту была при жизни Мерсенна делом затруднительным, поскольку проверка делением была одним из немногих доступных инструментов. Например, для ${M_{257}}$ наименьшим множителем оказывается 15-значное число, так что даже с современными методами факторизации его не так-то легко найти. В функции FactorInteger используются наиболее совершенные методы, которые позволяют применять метод факторизации в отношении больших целых чисел.

Теорема множителей Эйлера и Мерсенна

Первые важные достижения в области проверки на простоту принадлежат великому математику Леонарду Эйлеру, который незадолго до 1772 года уточнил, что ${M_{31}}$ является простым. Он сделал это, продемонстрировав, что любой простой делитель ${M_{31}}$ должен быть равен 1 или 62 (mod 248).

Такой относительно короткий список даже во времена Эйлера мог быть проверен с помощью пробного деления (вручную). Ему принадлежит применение теоремы Мерсенна, в которой говорится, что если $q$ является делителем ${M_p}$ , то $q \equiv 1 \vee - 1\left( {\bmod 8} \right)$ , $q \equiv 1\left( {\bmod p} \right)$ и $q \equiv 2kp + 1$ для некоторого целого положительного числа $k$ . Эти факты значительно ограничивают количество возможных делителей ${M_p}$ . С помощью функций, представленных ниже, демонстрируется использование этой теоремы с целью предоставления списка возможных делителей ${M_p}$ , меньших, чем $\sqrt {{2^p} - 1}$ .

Мы используем эти функции, чтобы быстро найти делитель ${2^{41}} - 1$ . Обратите внимание, что $q$ является делителем ${2^{p}} - 1$ тогда и только тогда, когда ${2^p} \equiv 1\left( {\bmod q} \right)$ . Это дает возможность использовать функцию PowerMod, что обеспечивает эффективное возведение в степень по модулю.

Ниже приводится число Мерсенна с 161649 знаками:.

Люка и Лемер

Следующим важным шагом стало открытие Эдуардом Люка метода для проверки простоты чисел данной формы. Он использовал свой метод в 1876 году для проверки, является ли ${M_{127}}$ (самое большое число Мерсенна «докомпьютерной» эпохи) простым. В начале двадцатого века, когда основы двоичной арифметики и алгебры стали широко известны, Дерек Генри Лемер усовершенствовал метод Люка. Полученный в результате тест простоты чисел Люка-Лемера обеспечивал эффективную проверку, если число данной формы являлось простым. Проверка проводилась с помощью сравнения по модулю:

Это означает, что $k$ идентично числу, представленному его $p$ битами низшего порядка, плюс — числами, представленными остальными битами. Это соотношение может применяться рекурсивно до тех пор, пока $k < {2^p} - 1$ .

Рассмотрим следующий пример. Здесь мы покажем, что для $k = {\text{1234567891}}$ . Обратите внимание, что (23 бита низшего порядка) и — означает, что остальные биты сдвинуты в крайнее нижнее положение.

Функция ниже задает этот метод для вычисления $k\bmod \left( {{2^p} - 1} \right)$ с использованием только битовых операций (без деления). Обратите внимание на то, что ${2^n} - 1$ имеет двоичную форму ${111...111_2}$ , при этом нет ни одного 0, и поэтому она также служит в качестве маски для $p$ битов низшего порядка числа $k$ .

Следующая функция реализует тест простоты Люка-Лемера (LLT). Определим последовательность ${s_0} = 4$ , $${s_i} = s_{i - 1}^2 - 2;i > 0$» />. Тогда <img src=$ является простым тогда и только тогда, когда ${s_{p - 1}} \equiv 0\left( {\bmod {M_p}} \right)$ .

Опыт показывает, что основное время выполнения этих функций тратится на целочисленную арифметику.

Чтобы проверить, является ли ${2^p} - 1$ простым, лучше сначала проверять простоту на небольших простых делителях и выполнять другие проверки простоты. Сначала мы используем теорему делителей простых чисел Мерсенна, закодированную в checkMPDivisors, а затем функцию PrimeQ. Если это не сработает, применим тест Люка-Лемера.

Здесь мы представляем расширенную версию функции PrimeQ, которая применяет тест Люка-Лемера для больших чисел вида ${2^p} - 1$ .

От ${M_{13}}$ до ${M_{20}}$

Первым простым числом Мерсенна, обнаруженным на компьютере с помощью теста Люка-Лемера, стало ${M_{521}}$ , найденное Рафаэлем Робинсоном 30 января 1952 года на базе лампового компьютера SWAC (Standards Western Automatic Computer). Ниже вы видите блок памяти этого компьютера, содержащий 256 слов по 37 бит каждое.

20-е простое число Мерсенна было обнаружено Александром Гурвицем в ноябре 1961 года в результате проведения 50-минутного теста Люка-Лемера на IBM 7090. Ниже мы воспроизводим эти результаты (на это потребовалось около 151 секунд машинного времени на современном одноядерном ноутбуке).

Одной из особенностей Wolfram Language, делающей его пригодным для такого рода работы, является его быстрая целочисленная арифметика. Поиск простых чисел Мерсенна стал настоящим вызовом на рассвете эпохи компьютеризированного поиска. Исследователи адаптировали методы быстрого преобразования Фурье для преобразования задачи умножения двух больших целых чисел в простое поэлементное произведение трансформированных цифр. Быстрое умножение целых чисел необходимо для шага возведения в квадрат в тесте Люка-Лемера. В Wolfram Language используются новейшие алгоритмы, оптимизированые для работы с точными целыми числами с миллиардами символов. Например, убедимся, что последнее из них, — ${M_{4423}}$ , — на самом деле простое число Мерсенна, и продемонстрируем все его цифры.

Совершенные числа

Существует интересная связь между простыми числами Мерсенна и совершенными числами. Совершенное число — это число, равное сумме всех своих делителей (отличных от самого числа). Евклид предполагал, а Эйлер доказал, что все четные совершенные числа, имеют вид $P = {2^{p - 1}}\left( {{2^p} - 1} \right) = {2^{p - 1}}{M_p}$ . Функция Wolfram Language PerfectNumberQ проверяет, является ли число совершенным. Продемонстрируем это свойство на ${M_{31}}$ .

21-е, 22-е и 23-е числа Мерсенна

Перейдем к переоткрытию 21-го, 22-го и 23-го чисел Мерсенна (будем обозначать их далее в форме вида $\# 21$ ): $\# 21 = {M_{9689}}$ , $\# 22 = {M_{9941}}$ , $\# 23 = {M_{11213}}$ . Все они были обнаружены Дональдом Гиллисом, который запускал LLT на ILLIAC II всю весну 1963 года (см. здесь). Для проверки всех чисел вида ${2^p} - 1$ для простых чисел в промежутке $7927 \leqslant p \leqslant 17389$ нам понадобилось около 6 минут.

24-е, 25-е и 26-е числа Мерсенна

Далее мы расширяем поиск, чтобы найти $\# 24 = {M_{19937}}$ , $\# 25 = {M_{21701}}$ , $\# 26 = {M_{23209}}$ . Последнее из них было обнаружено в феврале 1979 г. Лэндоном Куртом Ноллом и Лорой Никель. Они искали в диапазоне от ${M_{21001}}$ до ${M_{24499}}$ на суперкомпьютере CDC Cyber 174 (почитать об этом можно здесь). Наши расчеты становятся более долгими, так что мы начинаем использовать параллельную обработку. Поскольку тесты независимы, для ускорения работы мы можем использовать ParallelMap. Проверка диапазона $17393 \leqslant p \leqslant 27449$ занимает приблизительно три с половиной минуты (используются 4 ядра).

Обратите внимание на то, что специализированный тест Люка-Лемера значительно быстрее, чем более общая функция PrimeQ (для данных чисел Мерсенна).

27-е и 28-е числа Мерсенна

Далее мы проверили диапазон $27457 \leqslant p \leqslant 48611$ , чтобы найти число $\# 27 = {M_{44497}}$ . Оно было обнаружено в апреле 1979 года Гарри Нельсоном и его командой (они использовали суперкомпьютер Cray-1). Наш поиск завершился за 15 минут.

Следующее число Мерсенна, $\# 28 = {M_{86243}}$ . Оно был открыто в сентябре 1982 года Дэвидом Словински — также на Cray-1. Этот суперкомпьютер весил около 5 тонн и потреблял около 115 киловатт электроэнергии, а его вычислительная производительность достигала 160 мегафлопс. Он поставлялся с 1 миллионом 64-разрядных слов памяти (8 мегабайт), а стоил около 16000000$ в сегодняшних ценах. Ниже показана деталь его системы охлаждения. Для сравнения: Raspberry Pi весит несколько унций, работает на 4 Вт, обеспечивает около 410 мегафлопс и снабжен 1Гб оперативной памяти, и это все — за 40$. А еще он поставляется сразу с системой Mathematica.

Число $\# 28 = {M_{86243}}$ содержит 25962 цифры. Это значение мы нашли за 1 час и 14 минут (на моем ноутбуке, а не на Raspberry Pi), проводя испытания в диапазоне $48619 \leqslant p \leqslant 87533$ .

29-е число Мерсенна

Поскольку теперь нам требуется более серьезное компьютерное время, мы также производим отметку времени для каждого прогона. Теперь мы проверяем диапазон $87557 \leqslant p \leqslant 110597$ . Через 1 час и 44 минут компьютер показал: $\# 29 = {M_{110503}}$ . Это число впервые было обнаружено 29 января 1988 года Уокер Колкуиттом и Люком Уэлшем (суперкомпьютер NEC DX-2; статью можно найти здесь).

30-е и 31-е числа Мерсенна

Следующие два простых числа Мерсенна: ${M_{132049}}$ и ${M_{216091}}$ , — были на самом деле обнаружены еще до 29-го (той же командой, которая обнаружила и 28-е). Они использовали Cray X-MP, чтобы найти 30-е число Мерсенна в сентябре 1983 года и 31-е — в сентябре 1985 года. Проверим $\# 30$ с помощью функции поиска в диапазоне $110603 \leqslant p \leqslant 139901$ . Для проверки каждого ${M_p}$ в этом диапазоне понадобилось 4 часа и 8 минут.

Великий интернет-поиск чисел Мерсенна

С открытием 34-го простого числа Мерсенна — ${M_1257787}$ — в сентябре 1996 года закончилась эпоха суперкомпьютеров для поиска простых чисел Мерсенна. Следующие 15 были найдены добровольцами Великого интернет-поиска простых чисел Мерсенна (GIMPS), в рамках которого проводится вариант теста Люка-Лемера (в качестве фонового процесса) на персональных компьютерах. Этот масштабный проект распределенных вычислений в настоящее время достигает уровня производительности, эквивалентного приблизительно 300 терафлопс в секунду, причем задействуется время простоя более чем 1,3 миллиона компьютеров.

Проверим 34-е число Мерсенна с помощью теста Люка-Лемера. На этом этапе мы достигли предела возможностей личного компьютера. На тестирование тысячи чисел Мерсенна в этом диапазоне потребуется много дней. Интересно отметить, что тест Люка-Лемера часто используется в качестве стресс-теста надежности компьютерного оборудования и программного обеспечения, так как даже одна арифметическая ошибка среди миллиардов вычислений, необходимых для тестирования одного большого простого числа, повлечет за собой неправильный вывод, что будет означать потерю числа Мерсенна или ложный ответ. Тот факт, что мы проверили каждое ${M_p}$ для простых чисел в промежутке между 2 и 139901, убедительно доказывает надежность арифметики больших чисел и бинарных операций в системе Mathematica и языке Wolfram Language.

Факторизация чисел Мерсенна

Как мы уже видели, количество возможных множителей в разложении чисел вида ${2^p} - 1$ согласно теореме множителей Мерсенна ограниченно. Это позволило провести эффективный компьютеризированный поиск делителей больших чисел этой формы. На момент написания этой статьи все числа Мерсенна (до ${2^{1201}} - 1$ ) были полностью разложены на множители (иллюстрации можно найти здесь). Проект GIMPS также привел к открытию крупных множителей многих чисел Мерсенна в качестве побочного продукта проверки простоты чисел. Новую статью, которая представляет собой современный подход к решению этой проблемы (наряду с 17 новыми факторизациями), можно найти здесь. Наибольшее факторизованное число составило ${2^{1199}} - 1$ ; его наименьший из найденных делителей имеет 76 десятичных цифр. Его наименьший делитель равен 23. Общее время, необходимое для того, чтобы получить этот результат составляет 7500 лет (речь о компьютерном времени).

Мы можем быстро найти несколько первых множителей ${2^{1201}} - 1$ с помощью функции FactorInteger.

Все простые числа Мерсенна, обнаруженные на сегодняшний день, каталогизированы в Wolfram Language (до 44-го). Доступ к этой информации обеспечивается функциями MersennePrimeExponent и MersennePrimeExponentQ.