Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Покажем, что п не есть псевдопростое число по основанию Ь. Действительно, заметим, что если (1) выполняется, то автоматически Ьп 1 = 1 (mod р ), так как р \п. Но в этом случае р(р — l)|(n - 1), так как р(р - 1) — порядок b по модулю р . Однако п — 1 = -1 (mod р), так как р\п, а это означает, что п — 1 не делится на р(р — 1).- Это противоречие доказывает, что Ь — такое основание, по которому п не
§ 1. ПСЕВДОПРОСТЫЕ ЧИСЛА
143
является псевдопростым.
Ь) Предположим сначала, что (р — 1)|(п — 1) для каждого простого делителя р числа п. Пусть Ь — любое такое основание, что НОД (6, п) = 1. Тогда для всякого простого р|п мы имеем: Ьп~Х есть степень Ьр 1 и, значит, 6™ 1 = 1 (mod р). Таким образом, bn~l — 1 делится на каждый из простых делителей числа п, следовательно, делится и на их произведение, которое равно п. Поэтому (1) выполняется для всех оснований Ъ. Обратно, предположим, что существует такое простое число р|п, что п - 1 не делится на р - 1. Пусть д — целое число, порождающее (Z/pZ) . Как в доказательстве части а), найдем такое целое число 6, что b = д (mod р), Ь = 1 (mod п/р). Тогда НОД (6, n) = 1 и 6n_1 = gn~l (mod р). Однако дп~1 ф 1 (mod р), так как п - 1 не делится на порядок р — 1 числа д по модулю р. Стало быть, bn (mod р) и (1) не может выполняться. Доказательство
предложения завершено.
Пример 2. Число п = 561 = 3 • 11 • 17 есть число Кармайкла, так как п - 1 = 560 делится на 3 - 1 = 2, 11 - 1 = 10, 17 - 1 = 16. В упражнениях мы увидим, что 561 — наименьшее число Кармайкла.
Предложение V. 1. 3. Число Кармайкла должно быть произведением не менее 3 различных простых чисел.
Доказательство. Согласно предложению V. 1.2 число Кармайкла должно быть произведением различных простых чисел. Следовательно, остается лишь исключить возможность того, что n = pq есть произведение двух различных простых.
Пусть р < q. Тогда, если бы п было числом Кармайкла, мы имели бы п — 1 = 0 (mod q — 1) по части Ь) предложения V. 1.2. Однако п — 1 = p(q - 1 + I)-I = P- I (mod q — 1), и так как 0<р-1<<т-1,то правая часть не сравнима с нулем по модулю q — 1. Полученное противоречие с частью Ь) предложения V. 1.2 завершает доказательство.
Замечание. Лишь недавно Альфорд, Грэнвиль и Померанц доказали, что существует бесконечно много чисел Кармайкла. См. отчет Грэнвиля в Notices of the Amer. Math. Soc, 1992, т. 39, с. 696-700.
Эйлеровы псевдопростые. Пусть п — нечетное целое число и обозначает символ Якоби (см. §11.2). Если п — простое число, то по предложению П. 2. 2
6(„-l)/2 s (mod п) (2)
для любого целого Ь. С другой стороны, если п — составное, то согласно упражнению 21 к §11.2 не менее 50% всех Ь Є (Z/nZ)* не удо-
144
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
влетворяют (2). Эти два факта позволяют построить эффективный вероятностный тест для проверки простоты большого числа п. Начнем со следующего определения.
Определение. Если п — нечетное составное число, а Ь — такое целое число, что НОД (b,n) = 1 и выполняется (2), то п называется эйлеровым псевдопростым числом по основанию Ь.
Предложение V. 1.4. Если п — эйлерово псевдопростое число по основанию Ь, то оно — псевдопростое по основанию Ь.
Доказательство. Мы должны доказать, что если выполнено (2), то выполнено и (1). Но это очевидно: достаточно возвести обе части (2) в квадрат.
Пример 3. Предложение, обратное к V. 1.4, неверно. Так, в примере 1 мы видели, что 91 — псевдопростое по основанию 3. Однако 3 =27 (mod 91), так что (2) не выполняется для n = 91, 6 = 3. (Заметим, что знание порядка Ь в (Z/91Z)* упрощает возведение Ь в высокую степень по модулю 91: так как 3=1 (mod 91), то 3 = 3 (mod 91).) Число 10 дает пример основания, по которому 91 — эйлерово псевдопростое число: 1045 = 103 = -1 (mod 91) и (|у) = -1.
Пример 4. Легко убедиться, что любое нечетное составное п является псевдопростым по основаниям ±1; в дальнейшем мы будем исключать эти «тривиальные» основания Ь.
Опишем теперь тест Соловея-Штрассена. Пусть дано нечетное натуральное число и мы хотим знать, простое оно или составное. Выбираем случайно к натуральных чисел Ь, меньших п. Для каждого из них вычисляем значения обеих частей (2). Вычисление ^71-1'/2 проводится за О (log п) двоичных операций при использовании метода повторного возведения в квадрат (предложение L 3.6); вычисление символа Якоби в правой части также проводится за 0(log п) двоичных операций (см. упражнение 17 к §11.2). Если эти два значения не сравнимы по модулю п, то мы убедились, что п — составное число, и прекращаем тест. В противном случае переходим к следующему Ь. Вероятность того, что при составном п сравнение (2) выполняется
к
для всех к случайно выбранных Ь, не превышает 1/2 . Таким образом, тест Соловея-Штрассена — вероятностный алгоритм, который приводит либо к выводу о том, что п — составное число, либо к выводу о том, что п — «вероятно» простое.
Отметим, что не существует эйлеровых псевдопростых чисел, аналогичных псевдопростым числам Кармайкла: для любого составного п критерий (2) не выполняется, по меньшей мере, для половины всех возможных Ь.
