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

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

Рассмотренные числовые функции могут успешно применяться для проверки простоты чисел специального вида. С помощью числовых функций для чисел специального вида удается построить критерии, эффективность которых часто на несколько порядков выше, чем эффективность критериев для чисел произвольного вида. Данная тема необъятна, и ниже рассмотрены только самые простые примеры применения таких критериев.

Наибольшее простое число поймано решетом Эратосфена.

Конечно, решето Эратосфена годится для поиска простых чисел Мерсенна не более чем консервная банка для плавания через Атлантический океан. Гораздо более пригодна для этой цели функция PrimeQ. С ее помощью мы нашли все те индексы простых чисел Мерсенна, которые не превышают 5000. Дальнейшее продвижение оказалось практически невозможным.

Однако есть другой метод проверки простоты чисел этого вида. Его опубликовал Э. Люка (Lukas2) в 1878 году, а в 1930 году усовершенствовал Д. X. Лемер. Он основан на следующей теореме.

Если р>2 – простое число, то число Мерсенна Мр = 2^p -1 является простым тогда и только тогда, когда bр_r = 0, где последовательность L; определяется так:

L0 =4, Lⁱ⁺¹ =(L_i² -2)mod(2ⁱ -l).

Совершенно элементарное доказательство этой теоремы имеется во многих книгах; в частности, его можно найти во втором томе трехтомника Кнута. Чтобы сократить доказательство, можно также заметить, что критерий Люка основан на малой теореме Ферма для чисел из полей Q(√5) или Q(v3).

Тест Люка позволил проверить вручную все простые числа до МР7. Когда для проверки простоты стали применяться ЭВМ, началась настоящая гонка. Очередные новые простые числа Мерсенна рассматривались как свидетельство быстрого роста возможностей ЭВМ. Чтобы убедиться, что Л/819] является составным, Д. Дж. Уилер потратил около 100 часов машинного времени ILLIAC I – самой быстрой ЭВМ выпуска пятидесятых годов. Гурвицу на IBM 7090 для этой же цели потребовалось лишь 5 часов в 1962 году. В 1964 году Гиллис сделал это на ILLIAC II за 49 минут. А в 1971 году Такерман потратил на это только 3 минуты на IBM 360/91. (Но то были суперЭВМ, а я на своем весьма слабеньком ПК на это потратил 4.125 секунды.) Проверка простоты М1тз на ILLIAC II заняла 2 часа 15 минут, и всего лишь 8 минут на IBM 360/91. (Но это столько нужно суперЭВМ, а моему старенькому ПК нужно всего лишь 9.672 секунды.)

Найденное очередное простое число Мерсенна становилось визиткой фирмы. Например, доказательству простоты числа М112, Иллинойский университет посвятил выпуск фирменного конверта. IBM в долгу не осталась: она выпустила конверт, посвященный доказательству простоты М19937 (это 6002-значное число, найденное Б. Такерманом 4 марта 1971 года, довольно долго было рекордсменом). Проверка простоты этого числа и у меня заняла изрядное время – 42 094 секунды. с помощью функций Mod и powerMod несложно запрограммировать тест Люка-Лемера. Сначала дадим нужные определения.

Поскольку единственным простым числом Мерсенна Мр с четным индексом р является Я,, можем ограничиться поиском только нечетных индексов р. (Конечно, программа при этом пропустит число Мг = 3, но разве мы можем о нем забыть?) Вот нужная нам программа поиска нечетных индексов р простых чисел Мерсенна М ".

Даже на весьма слабеньком компьютере всего за несколько часов вы можете найти все нечетные индексы р первых 24 простых чисел Мерсенна известных до 1980 года: 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937. Здесь, конечно, только 23 числа, поскольку индекс первого простого числа Мерсенна М2 = 3 четный: р = 2.

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