Иллюстрированный самоучитель по Mathematica 5

Критерии простоты чисел специального вида. Простые числа Мерсенна, тест Люка-Лемера.

Впрочем, возможно, программу придется модифицировать так, чтобы она время от времени подавала признаки жизни", даже если не успевает найти простое число Мерсенна. Это можно сделать, например, так.

Так что если не поленитесь потратить ночку-другую на вычисления, то найдете и другие простые числа р, при которых р-е число Мерсенна Mf = 2'-l является простым. В частности, вы сможете найти 6533-значное простое число Мерсенна Л/,,70, (найдено калифорнийскими школьниками Никкелом и Ноллом в 1978 году), 6987-значное простое число Мерсенна М23209 (найдено Ноллом), 13395-значное простое число Мерсенна Мш" (это 27-е простое число Мерсенна найдено Д. Словинским в 1979 году), 25962-значное простое число Мерсенна М86243 (это число Мерсенна найдено Дэвидом Словинским в январе 1983 года).

Если хотите, проверьте, не пропустил ли я чего-нибудь и сможете ли вы продвинуться дальше. У меня проверка простоты М,1701 заняла 53.547 секунды, М2Ш) – 64.25 секунды, Мшу, – 350.562 секунды (ого, почти 6 минут!), Мим – 1845.34 секунды (это чуть больше получаса). Думаю, что дальнейшее продвижение по данной программе весьма затруднительно. В данном случае либо нужен компьютер со значительно более высоким быстродействием, либо нужно изменить программу так, чтобы большинство составных чисел отсеивалось еще до применения критерия Люка.

Казалось бы, перед применением критерия Люка можно проверить, что число Мр не удовлетворяет сравнению ам' = a(modMp) при некоторых а. В качестве а удобно взять, например, число 3. Можно было бы также попытаться проверить другое свойство простых чисел. Однако при этом нужно тщательно следить за тем, чтобы все эти дополнительные проверки не снижали быстродействие программы. Время проверки сравнения aⁿ s=a(modMp) может оказаться, например, примерно равным времени проверки по критерию Люка-Лемера. Тогда, понятно, такая дополнительная проверка только замедляет выполнение программы. Так что дальнейшее продвижение требует изобретательности.

Дальше идет степень 110503. В 1983 году была найдена степень 132049, а в 1984-216 091. Поиском степеней на суперкомпьютерах прославился в 90-х годах XX столетия Дэвид Словинский. Вместе с Полем Гейджем он получил следующие индексы простых чисел Мерсенна: 756 839, 859 433, 1 257 787. Но степени 1 398 269 и 2 976 221 были найдены Жоэлем Арменгодом (Joel Armengaud) и Гордоном Спенсом (Gordon Spence) на персональных компьютерах по программе, разработанной Георгом Вольтманом (George Woltman) в 1996 году. Предварительная проверка Л/2.76,,, на компьютере с процессором Pentium с тактовой частотой 100 МГц заняла 15 суток в августе 1998 года! 27 января 1998 года Роланд Кларксон (Roland Clarkson) обнаружил простоту Л/3021377, а 1 июня 1999 года Найян Хьяратвала (Nayan Hayratwala) – простоту Af6972593. Впрочем, люди стремятся к рекордам, и после 1983 года числа проверялись не подряд, так что могли что-то и пропустить! Правда, добровольцы тщательно потом все просмотрели до миллиона!

Как из этого видно, критерий Люка-Лемера применяется только после некоторого предварительного отбора, которому уделяется огромное внимание. Давайте попробуем найти хотя бы какой-нибудь очень простой (а, значит, и довольно грубый) метод отсева показателей р, для которых числа Мерсенна Мр не являются простыми. Пусть s – показатель 2 по некоторому простому модулю q: Т =1 (mod q). (Такое 5 можно найти с помощью функции MultiplicativeOrder [2, q].) Поскольку Мp = 1ⁿ -1 оно делится на простое число q, если р является показателем 2 по простому модулю q. Так что такие индексы р чисел Мерсенна можно отсеять сразу, если Мр # q. Поэтому для предварительного отсева нам понадобится таблица показателей 2 по простым модулям q. Причем, чтобы уменьшить таблицу, из нее можно вычеркнуть все составные показатели. Чтобы построить таблицу, нам понадобится следующая функция.

Эта функция по заданному номеру n находит простое число q = рn, а затем – 5 (показатель 2 по найденному простому модулю q, если он существует). Если оказывается, что показатель 2 по простому модулю q существует, проверяется, является ли он простым числом. Если оказывается, что найденный показатель 2 по простому модулю q является простым числом, он возвращается в качестве значения функции. (В противном случае функция возвращает Null.) С помощью этой функции легко строится нужная нам таблица простых показателей 2 по простым модулям q.