§ 7.3. Тест Миллера

В § 7.1 мы видели, что теорема Ферма предлагает способ проверки разложимости данного числа, не требуя поиска его делителей. Однако этот подход не всегда работает и, если очень не повезет, может потерпеть неудачу. Далее (§ 7.2) мы пытались объяснить, что означает «невезение» в данном контексте. Было обнаружено, что числа Кармайкла ведут себя как простые, в том смысле, что мы не можем установить

их разложимость методом, развитым в конце параграфа. Но этот тест можно так усовершенствовать, что его не смогут обмануть даже числа Кармайкла. Новый тест ввел Миллер (G. L. Milller) в 1976 году.

Пусть нечетное целое. Выберем целое число удовлетворяющее неравенству и назовем его, как и раньше, основанием. Поскольку нечетное, должно быть четным числом. Первый шаг теста Миллера состоит в определении такого показателя к 1, для которого где не делится на 2. Иначе говоря, мы должны найти наибольшую степень двойки, делящую и соответствующее частное

Далее тест вычисляет вычеты по модулю у следующей последовательности степеней:

Разберемся, какими свойствами обладает эта последовательность в случае простого Итак, пока не будет оговорено особо, простое число. Теорема Ферма говорит нам, что

Значит, если простое, то последний вычет в последовательности всегда равен 1. Конечно, единица среди вычетов может встретиться и раньше. Пусть наименьший показатель, для которого Если то

По предположению, число простое и (так как оно делит разность квадратов делит либо либо С другой стороны, в силу выбора показателя число не может делить Остается только одна возможность: делитель числа т.е.

Эти рассуждения показывают, что в случае простого среди последовательности степеней:

найдется по крайней мере одна, сравнимая с —1 по модулю Хорошо, но не слишком. Дело в том, что наше рассуждение основывалось на предположении: Если то А у нас нет простого способа разложения числа на множители, поскольку нечетно. Значит, если простое, то с последовательностью вычетов по модулю о которой мы говорили, должно произойти одно из двух: либо первый же вычет равен 1, либо среди них появится В противном случае (не будет ни того, ни другого) число должно быть составным.

Последовательность вычетов, используемая в тесте Миллера, довольно легко вычисляется, потому что каждый вычет (за исключением первого) — квадрат предыдущего. В самом деле, при Отсюда вытекает, что как только в последовательности вычетов по модулю встретится все остальные вычеты будут равны 1.

У нас появился еще один тест, который позволяет нам показать разложимость данного числа, но работающий только при удачном стечении обстоятельств. Тем не менее, тест Миллера более эффективен, нежели предложенный в § 7.1. Чтобы понять почему, заметим, что последовательность степеней, выписанная для псевдопростого по основанию должна иметь член, сравнимый с 1 по модулю А так как не простое, то существует хороший шанс, что этой степени не будет предшествовать другая, сравнимая с этом случае тест Миллера обнаружит разложимость числа. Приведем алгоритм, реализующий тест Миллера.

Тест Миллера

Ввод: нечетное натуральное и основание где

Вывод: одно из двух сообщений: составное» или «ничего определенного сказать нельзя».

Шаг 1. Последовательно делим на 2 пока не получим нечетного частного. В результате найдем положительное целое к и нечетное для которых

Шаг 2. Присвоим нулевое значение, а значение вычета по модулю

Шаг 3. Если или то вывести сообщение: «ничего определенного сказать нельзя»; в противном случае переходим к шагу 4.

Шаг 4. Увеличиваем на 1 и заменяем на по модулю переходим к шагу 5.

Шаг 5. Если то возвращаемся к шагу 3; в противном случае выдаем сообщение: составное».

В случае неопределенного сообщения возможны две ситуации: либо простое, либо составное. К сожалению, второй случай реально встречается. Рассмотрим несколько примеров, причем начнем с хороших новостей. Мы видели в § 7.1, что 341 — псевдопростое по основанию 2, так что это хороший объект для теста Миллера. Прежде всего, Теперь нам нужно найти вычеты по модулю 341 у степеней 2 с показателями 85 и 170:

Это позволяет тесту дать заключение: число составное.

Более наглядный пример дает нам число Кармайкла 561. Подвергнем его тесту Миллера по основанию 2. Простые вычисления показывают, что Выпишем последовательность вычетов степеней 2 по модулю 561:

(см. скан)

И в этом случае тест сообщит нам о разложимости числа.

Хотя 561 — число Кармайкла, мы обнаружили, что оно составное, применив наименьшее из возможных оснований.

Теперь плохие новости. Применим тест Миллера по основанию 7 к 25. Поскольку последовательность степеней и их остатков имеет вид:

(см. скан)

Так что тест здесь не может сказать ничего определенного, несмотря на то, что разложимость числа 25 видна невооруженным взглядом. Конечно, основание 7 мы выбрали не случайно, если бы основанием было 2, то тест бы узнал в двадцати пяти составное число.

Пусть нечетное целое число и Если составное, а тест Миллера его не распознал, то оно называется строго псевдопростым по основанию Вышеприведенный пример показывает, что 25 — строго псевдопростое по основанию 7. Легко увидеть, что строго псевдопростое число по основанию является псевдопростым по этому же основанию (см. упражнение 7).

Как мы уже отметили, число 25 не является строго псевдопростым по основанию 2. Наименьшее строго псевдопростое число по основанию 2 — это 2047. Более того, существует только 1282 строго псевдопростых чисел по основанию 2, лежащих между 1 и , что дает хорошее представление об эффективности данного теста. Конечно, можно применять тест Миллера по нескольким основаниям, что существенно увеличит его эффективность. Например, наименьшее строго псевдопростое одновременно по основаниям 2, 3 и 5 — это 25 326001.

Более того, не существует «строго Кармайкловских чисел». Это следует из результата М. О. Рабина (Rabin).

Теорема Рабина. Пусть нечетное натуральное число. Если тест Миллера, примененный к для более, чем

оснований, лежащих между не распознает в составного числа, то простое.

За подробностями можно обратиться к [39], или к [28]. Не стоит и говорить, что в случае больших применение теста Миллера по основаниям займет очень много времени. Вопреки этому замечанию, наиболее практичные тесты на простоту, как мы увидим в следующем параграфе, основываются на теореме Рабина.