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

в 13:17, , рубрики: wolfram language, wolfram mathematica, Алгоритмы, Блог компании Wolfram Research, Занимательные задачки, математика, Программирование, простые числа, совершенные числа, факторизация чисел, числа мерсенна
Простые числа Мерсенна и тест Люка-Лемера - 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Люка и Лемер

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 минут.

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

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

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

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

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

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

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

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

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

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

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

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 ядра).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 минут.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Автор: Wolfram Research

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js