Глава 13.

ТЕСТ ФЕРМА ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ

Основное в этой главе…

Тест на основе малой теоремы Ферма……………………………..….166

Основные свойства псевдопростых чисел…………………………..…..…166

Понятие о последовательностях Люка. (n+1) – критерий Люка..…..171

(P+1) – метод факторизации Вильямса…………………….…..….172

164 Глава 13. ТЕСТ ФЕРМА ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ

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

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

В основе тестов лежат т.н. критерии простоты [15,16]. Существует два типа критериев простоты: детерминированные и вероятностные. Детерминированные тесты позволяют доказать, что тестируемое число – простое. Практически применимые детерминированные тесты способны дать положительный ответ не для каждого простого числа, поскольку используют лишь достаточные условия простоты.

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

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

13.1. Решето Эратосфена и критерий Вильсона

Широко известен метод последовательного построения списка всех простых чисел, не превосходящих заданного числа N . Этот метод называется решетом Эратосфена.

В списке L всех чисел от 2 до N вычеркиваем числа кратные 2, большие двойки. Из оставшихся чисел выбираем наименьшее (оно равно 3), а из L вычеркиваем числа, кратные 3, большие тройки и так далее. Если очередное,

Тест на основе малой теоремы Ферма 165

выбираемое из L , наименьшее число a > N , то работу прекращаем.

Оставшиеся в L числа составляют искомый список простых чисел.

Данный метод основан на том, что все кратные указанного (простого) числа a и кратные превосходящих его чисел к моменту выбора a уже

вычеркнуты. Действительно, если ab ≤ N , то b ≤ N , следовательно, все кратные числа b были вычеркнуты ранее, как кратные некоторого его простого делителя.

Уместно задать вопрос, существуют ли критерии простоты, являющиеся необходимыми и достаточными?

Примером такого критерия является т.н. критерий Вильсона: число n -

простое тогда и только тогда, если (n −1)!= −1(n).

Для n = 2,3 утверждение очевидно. Если n = p > 3 - простое, то для каждого взаимно простого с p натурального числа a существует обратный по модулю p , причем, если a ≠ ±1(p), то a−1 ≠ a(p). В число (p −1)! входят сомножителями все ненулевые вычеты по модулю p . Поэтому произведение всех вычетов a ≠ ±1(p) дает единицу, а пара вычетов a = ±1(p) дает в произведении –1.

Обратно, если n = ab , 1< a < n, то a делит (n −1)!, поэтому вычета,

обратного к (n −1)!modn , не существует. Значит, (n −1)! не может быть сравнимо с (−1) по модулю n, что противоречит условию.