Простые числа Мерсенна и тест Люка-Лемера

http://blog.wolfram.com/2016/09/30/mersenne-primes-and-the-lucas-lehmer-test/
  • Перевод

Перевод поста Джона Макги (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 LanguagePrimeQ, в которой используются современные методы тестирования чисел на простоту, для которых не требуется поиска конкретного множителя, чтобы доказать, что число составное.





Вполне возможно, что его утверждение о том, что ${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$. Тогда ${M_p} = {2^p} - 1$ является простым тогда и только тогда, когда ${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.













Если вас заинтересовала эта тема, вы можете найти более подробную информацию на следующих веб-сайтах:

Wolfram Research 46,05
Wolfram Language, Mathematica, Wolfram Alpha и др.
Поделиться публикацией
Комментарии 20
  • +2
    Спасибо за интересную статью! Получил истинное удовольствие, сходил на сайт GIMPS и установил Prime95:) Возник тут сразу вопрос. А есть какое-нибудь более-менее активное применение этим числам? В криптографии, например.
    • +1

      Насчет GIMPS — есть более продвинутый проект на базе распределенных вычислений, PrimeGrid www.primegrid.com. Они там ищут несколько разных форм простых чисел — числа Прота, например, m*2n+1.

    • +1
      Ниже вы видите памяти этого компьютера, содержащий 256 слов по 37 бит каждое.

      Спасибо за интересную статью но, это блок с элт и вряд-ли блок памяти. Скорее всего вывода или диагностики.

      • +1
        https://ru.m.wikipedia.org/wiki/%D0%97%D0%B0%D0%BF%D0%BE%D0%BC%D0%B8%D0%BD%D0%B0%D1%8E%D1%89%D0%B0%D1%8F_%D1%8D%D0%BB%D0%B5%D0%BA%D1%82%D1%80%D0%BE%D0%BD%D0%BD%D0%BE-%D0%BB%D1%83%D1%87%D0%B5%D0%B2%D0%B0%D1%8F_%D1%82%D1%80%D1%83%D0%B1%D0%BA%D0%B0
        • 0

          Спасибо!
          Не знал, застал уже на ферритовых кольцах.

          • 0
            Прошу прощения за вид ссылки, с мобильного через приложение отправлял, не обратил внимания.
            • 0
              В википедии есть функция «цитировать страницу». Ссылку надо брать оттуда.
        • +1
          20-е простое число Мерсенна было обнаружено Александром Гурвицем в ноябре 1961 года в результате проведения 50-минутного теста Люка-Лемера на IBM 7090. Ниже мы воспроизводим эти результаты (на это потребовалось около 151 секунд машинного времени на современном одноядерном ноутбуке)

          50минут vs 151 секунда — т.е. современный одноядерный ноутбук всего в 20 раз эффективнее компьютера 55 летней давности? Либо тут опечатка, либо с эффективностью что-то не то. Быстрый гуглинг показывает эффективность 7090 в 100KFlops, современный ноутбук по хорошему должен бы единицы гигафлопс выдавать
          • 0
            Я бы предположил, что Гурвиц писал сильно оптимизированный код под конкретную платформу, а тут вычисления в Mathematica (интерпретатор?) с открытым скайпом и другими оверхедами.
            • 0
              Либо тут опечатка, либо с эффективностью что-то не то.

              Я посмотрел статью, на которую в тексте приводили ссылку.


              Theorem.
              If S(1) = 4 and S(n+1) = S(n)^2-2 then Mp is prime if and only if S(p-i) = 0 (mod Mp).
              The test takes about 50 minutes of machine time for p = 4423

              Я так понимаю, 50 минут уходило на то, чтобы для одного фиксированного p, взять Mp=2^p-1 и потом вычислить по его модулю S(p-1).


              Что именно делают и меряют в wolfram alpha — мне не понятно.


              Я попробовал простое решение "в лоб" на Scala — оно перебирает все простые числа до p=5000 за 30 секунд.


              максимально простой код
                val start = System.currentTimeMillis()
                var count = 0
              
                for (p <- 2 to 5000 if BigInt(p).isProbablePrime(20)) {
                  val mp = BigInt(2).pow(p) - 1
                  if (mp.isProbablePrime(20)) {
                    count += 1
                    println(s"$count numbers found, time = ${System.currentTimeMillis() - start}ms")
                    println(s"2^$p - 1 = $mp")
                  }
                }

              Ещё попробовал алгоритм Люка-Лермера, для p = 4423 проверяет за 0.2 секунды. Получается, в 15000 раз быстрее, чем за 50 минут)
              Перебор для всех простых p от 2 до 5000, как ни странно, у меня работает за те же 30 секунд.


              тест Люка-Лермера на википедии


              код с алгоритмом
                def lucasLehmer(p: Int): Boolean = {
                  var S = BigInt(4)
                  val mp = BigInt(2).pow(p) - 1
                  for (k <- 1 until (p - 1)) {
                    S = (S * S - 2) mod mp
                  }
                  S == 0
                }
              
                val start = System.currentTimeMillis()
                lucasLehmer(4423)
                println(s"time = ${System.currentTimeMillis() - start}ms")
              • 0
                В Wolfram Language тест Люка-Лемера (на моем компьютере 7-летней давности) для p = 4423 выполняется за:



                Дело в том, что функция Джона lucasLehmerPrep работает так: если за время, равное

                (количество цифр в записи числа)*0.05 секунд

                встроенная навороченная функция PrimeQ не дает ответа, применяется тест Люка-Лемера. Именно поэтому применение её к диапазону от 1 до 1000-го простого числа занимает 150 секунд (у Джона).

                Также учтите, что p_1000 = 7919, так что вы должны были проводить тестирование не для простых чисел меньших 5000, а до 8000. Время существенно изменится.

                Я проделал теже вычисления у себя на компьютере, получилось 1926 секунд (для lucasLehmerPrep) и 54 секунды для чисто теста Люка-Лемера (так как, получается, мой компьютер медленнее компьютера Джона примерно в 12.84, то вычисление теста Люка-Лемера для p = 4423 заняло бы у него примерно 0.0049 с (т. е. в 183673 раза быстрее), что заметно быстрее, чем у вас):

            • 0
              *промахнулся*
              • 0
                я десять тысяч раз извиняюсь, возможно это все так и должно быть запутанно, но (сугубо мое лично имхо, уберите помидоры) числа мерсена легко заходят через двоичное представление. для 2^n-1 это просто число из n двоичных единиц. И делиться на что бы то ни было оно может только если n не простое (это очевидно если представить двоичное умножение) — причем разложение числа 2^n -1 для составного n тривиально — это 2^x-1, где x — поочередно множители n и соотв. результат деления 2^n-1 на 2^x-1

                Ну и с пониманием этого факта все остальные свойства этих чисел тоже становятся либо тривиальны либо более понятны.

                Подробнее думаю не стоит — тусовка програмерская, должны понять.
                • 0
                  не правильно объяснил, давно обкатывал в голове, подробности стали забываться. Не обращайте внимания.
                • 0
                  Ваши рассуждения уже в первом абзаце не верны.

                  Речь идет как раз о простых числах Мерсенна, у которых n — простое число и которые в свою очередь являются простыми числами.

                  • 0
                    если вы мне — то нет. Я говорю о признаках делимости чисел 2^n-1 — прочитайте внимательно. если n — не простое — то разложение очевидно и такое число не может быть простым. Для простых n там идет проверка по сложению. В общем не суть. Умножьте на бумаге два числа в двоичной системе — поймете о чем я. Например 3 на 5 .
                    • 0
                      Простой контрпример: показатель степени простой — 11, число 2^11-1 = 2047 имеет делители 23 и 89:

                      • –1
                        > если n — не простое — то разложение очевидно
                        Уважаемый, вы все таки не перечитали о чем я пишу. Если Вам это не нужно — зачем тратить свое время на бессмысленные посты?
                        • 0
                          Ок, перешли на хамоватый язык, я с вами тоже цацкаться не собираюсь.

                          Гражданин, вы бы свои мысли оформили для начала в каком-то законченном виде. Написали один комментарий некорректный, я вам на это указал, тут же его отредактировали. Написали еще пару туманных комментариев ни о чем.

                          А если вы не поняли смысла поста и суть простых чисел Мерсенна — перечитайте пост и сопутствующую литературу.

                          Если считаете, что есть более тривиальный метод поиска простых чисел Мерсенна, опубликуйте — все сообщество математиков и криптологов вам спасибо скажет. Граждан, умеющих доказывать теоремы уровня Ферма на салфетке простым сложением уже достаточно видел.
                          • 0
                            >Если считаете, что есть более тривиальный метод поиска простых чисел Мерсенна

                            нет, не считаю.

                            >Граждан, умеющих доказывать теоремы уровня Ферма на салфетке простым сложением уже достаточно видел.

                            До свидания.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое