2.3.3. Тесты простоты

В этом разделе рассматривается следующая задача: для заданного положительного целого числа определить, является ли оно простым. При этом мы не интересуемся делителями числа . Наиболее очевиден следующий способ решения.

Первый детерминистический тест.

Разделим число последовательно на числа . Если при каком-нибудь делении мы получим нулевой остаток, то число составное, а делитель и частное являются его сомножителями; в противном случае m простое. (Почему нужно проверять только до )

Каково время работы этого теста? Очевидно, необходимо выполнить делений, поэтому время проверки простоты числа m равно . Эта оценка, однако, не является полиномиальной, поскольку, если учитывать длину записи , она принимает вид таким образом, это экспоненциальный тест, т.е. очень медленный. Простая на первый взгляд задача оказывается достаточно сложной. Конечно, первый тест (известный также под названием «метод пробных делений») делает гораздо больше, чем требуется: он не только определяет, является ли число простым, но и находит сомножители составного числа.

Значительный прогресс был достигнут в последние годы. Существуют две группы алгоритмов проверки простоты: детерминистические и вероятностные. Литература по этому предмету весьма обширна (Adleman et al., 1983; Cohen et al., 1982; Dixon, 1984; Lucas, 1961; Pomerance, 1981; Pratt, 1975; Rabin, 1980; Solovay et

и пока не сделано попыток дать полный обзор всех алгоритмов. Вместо этого мы приведем несколько тестов простоты, представляющих обе эти группы; практически все тесты так или иначе связаны с малой теоремой Ферма.

Продолжим рассмотрение детерминистических тестов.

Второй детерминистический тест.

Число просто тогда и только тогда, когда

Тест основан на теореме 2.3.16 (Wilson). Как уже отмечалось, факториал уничтожает всякий интерес к этому тесту; крайне медленный метод решета оказывается очень быстрым по сравнению с проверкой делимости для больших . Если имеет 100 цифр, то состоит примерно из цифр — не путайте с числом

Для третьего теста, который будет приведен ниже, нам понадобится следующее утверждение: если то — простое число, то существует натуральное число порядок которого по модулю равен , т.е. и никакая меньшая степень числа b не равна . Следующая теорема является обратным утверждением.

Теорема 2.3.27. Пусть — целое число 2. Если существует такое, что порядок b по модулю то равен в точности тот — простое число.

Доказательство. Если не просто, то . Для числа b из условия теоремы либо и в этом случае его порядок должен делить либо и тогда никакая степень b не сравнима с

Таким образом, получаем следующий тест простоты.

Третий детерминистический тест.

Число просто тогда и только тогда, когда существует элемент b, порядок которого по модулю в точности равен Эквивалентная формулировка: просто тогда и только тогда, когда существует такое, что и не равно для каждого простого делителя числа

Этот тест известен под названием «тест Лукаса» (1961). Для того чтобы определить, является ли m простым, нужно действовать следующим образом. Если не равно для некоторого , то не является простым (негативный тест,

вытекающий из теоремы Ферма). С другой стороны, если для некоторого 6 порядок b равен то просто (позитивный тест, вытекающий из теоремы 2.3.27).

К сожалению, очень сложно проверить, равен ли порядок b по модулю числу потому что нужно для каждого простого делителя числа показать, что не равно

Приведем два небольших примера. Пусть сначала После проверки того, что 899 не делится на 2, 3, 5, 7 и 11, можно предположить, что 899 — простое число. того чтобы наверняка убедиться в этом, применим тест; взяв получим, что 2838 = 683 (mod 899). Поэтому 899 не является простым числом, и, в самом деле, оно равно . Мы воспользовались только негативным тестом. Рассмотрим теперь число 341, для которого мы знаем, что Для применения позитивного теста мы должны вычислить порядок числа 2 по модулю 341, а это требует разложения на множители числа 340. Можно убедиться, что Позитивный тест не проходит и 341 — составное число.

Если мы вместо 341 возьмем некоторое -значное число , то для того чтобы использовать позитивный тест, нам придется разложить на множители число и с достаточно большой вероятностью после выделения маленьких простых делителей останется число из 35 или более цифр, которое необходимо будет разложить на множители — задача почти такая же сложная, как и разложение самого т. Поэтому тест Лукаса применим только в тех случаях, когда разлагается на множители просто.

Четвертый детерминистический тест.

Этот тест был вначале разработан в 1980 г. Адлеманом, Померанцом и Рюмли (Adleman et al., 1983) и впоследствии улучшен Коэном и Ленстрой (Cohen, Lenstra, 1982). Его детали требуют знакомства с техникой алгебраической теории чисел, но по существу он близок к тесту Ферма.

Показано, что время работы для этого теста равно

Несмотря на то что мы имеем дело с экспоненциальным тестом, выражение в показателе стремится к бесконечности очень медленно; например, первое число, для которого равно . Поэтому все числа, меньшие , могут

быть проверены на простоту за полиномиальное время. Таким образом, время работы этого теста очень близко к полиномиальному, и это лучшее, что известно на сегодняшний день. Неизвестно, существует ли полиномиальный детерминистический алгоритм проверки простоты.

Все приведенные выше тесты были детерминистическими; это означает, что для заданного числа то мы всегда получаем ответ, является ли оно простым или составным. Бели заменить слово «всегда» на «с некоторой вероятностью», то оказывается возможным построить вероятностные тесты простоты, которые работают за полиномиальное время; такие тесты называют также тестами псевдопростоты. Ниже мы рассмотрим несколько таких тестов.

Более точно, под тестом псевдопростоты мы будем понимать тест, применяемый к паре целых чисел обладающий следующими свойствами:

1. Тест может выдавать следующие ответы: — составное число» или «не удалось определить».

2. Если тест выдал ответ — составное число», то — составное число.

3. Время выполнения теста полиномиально зависит от

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

Первый вероятностный тест.

Для заданного выберем случайным образом . Если , то тест выдает ответ «то — составное число», в противном случае — «не удалось определить».

Вероятность того, что выдается ответ — составное число», равна вероятности того, что . Если — число делителей случайно выбрано в пределах то вероятность этого равна . Ясно, что это очень слабый тест.

Второй вероятностный тест.

Для заданного выберем случайным образом . Если , то тест выдает

ответ — составное число», в противном случае — «не удалось определить».

Если составное, то количество чисел для которых тест выдает ответ — составное число», равно Это число велико, если то имеет маленькие простые делители. Если, однако, , где , q — большие простые числа, то доля хороших оснований очень мала, и потому этот тест не лучше предыдущего.

Третий вероятностный тест.

Если для заданных чисел степень не равна , то тест выдает ответ — составное число», в противном случае — «не удалось определить».

Этот тест гораздо лучше двух предыдущих, но и он несовершенен, поскольку для всех псевдопростых по основанию b чисел он выдает ответ «не удалось определить». Как уже отмечалось, число 341 является псевдопростым по основанию 2. Из следующей теоремы вытекает, что существует бесконечно много псевдопростых по основанию 2 чисел.

Теорема 2.3.28. Если — псевдопростое число по основанию 2, то то же самое верно для числа

Доказательство. Пусть число является псевдопростым по основанию 2, т.е. . Докажем, что также является псевдопростым по основанию 2, используя тождество

Более точно, для того чтобы доказать, что мы покажем, что делит Согласно этому тождеству, достаточно доказать, что . Поскольку псевдопросто по основанию 2, то ; кроме того, , откуда следует, что

Как мы уже отмечали, кроме псевдопростых существуют составные числа, которые называются абсолютными псевдопростыми или кармайкловыми числами, определяемые условиями для всех b, таких, что

Как может получиться, что сравнимо с 1 по модулю для всех ? Например, для числа имеется таких значений b. Ответ оказывается совсем простым. Все, что требуется, — это три или более нечетных простых

числа такие, что Для каждого простого числа проверьте это для Покажем достаточность. Зафиксируем некоторое По теореме Ферма Поскольку делится на , то то же самое верно и для сравнение справедливо для любого i. Отсюда и из утверждения о единственности в греко-китайской теореме об остатках вытекает, что сравнение справедливо по модулю произведения чисел . (Действительно, запишем сравнения в виде Они образуют систему, имеющую единственное решение по модулю ; конечно, это единственное решение есть т.е.

Таким образом, эти числа псевдопросты по любому основанию b, и для всех них третий вероятностный тест будет выдавать ответ «не удалось определить». Наименьшее такое число — это ; другие кармайкловы числа: и т.д. Следующий тест справляется с такими числами.

Четвертый вероятностный тест.

Это тест сильной псевдопростоты. Пусть заданы бит. Пусть где t — нечетное число, и рассмотрим числа для — наименьший по абсолютной величине остаток по модулю то). Если либо либо найдется индекс i, такой, что то m называется сильно псевдопростым по основанию и тест выдает ответ «не удалось определить», в противном случае ответ — — составное число».

Этот тест успешно применяется и к псевдопростым числам, таким, как Например, для имеем соответственно, тогда как для получаем , и, следовательно, 561 — составное число. Итак, справедлива следующая теорема.

Теорема 2.3.29. Если тест сильной псевдопростоты выдает ответ — составное число», тот — составное число.

Доказательство. Докажем это от противного. Предположим, что — нечетное простое число. Покажем по индукции, что для любого , что будет противоречить условию теоремы. Очевидно, это справедливо для по теореме Ферма. Предполагая справедливость утверждения для

i, нетрудно видеть, что оно справедливо и для потому что равенство влечет за собой, что возводимое в квадрат число рано ±1. Но —1 не подходит по условию (иначе бы тест выдал ответ «не удалось определить»),

Анализ времени работы алгоритма четвертого вероятностного теста.

Число вычисляется за время поскольку в алгоритме быстрого возведения в степень выполняется умножений, , и, так как длины умножаемых по модулю чисел каждое умножение выполняется за время После этого при вычислении последовательности производится возведений в квадрат, где также и каждое возведение в квадрат выполняется за время . Таким образом, тест выполняется за время

Доказано, что четвертый вероятностный тест обладает следующим свойством: если — составное число, то вероятность того, что тест выдаст ответ — составное число», не меньше 1/2. Основная идея доказательства состоит в том, что собственная подгруппа конечной группы не мажет содержать больше половины ее элементов; детали см. в (Wilf, 1986). Более того, Рабином было показано, что не существует нечетного составного числа , которое является сильно псевдопростым по более чем 1/4 части всех оснований, меньших т. На практике для заданного числа мы применяем тест 100 раз, используя 100 случайно и независимо выбранных оснований . Если составное, то тест определит это с вероятностью и каждая проверка выполняется за полиномиальное время.