Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Почти все известные эффективные тесты на простоту аналогичны в общих чертах следующему.
Если п — простое число, то согласно малой теореме Ферма для любого такого Ь, что НОД (b, п) — 1,
Ьп~Х = 1 (mod п). (1)
Если п — не простое число, то (1) тоже может выполняться (хотя это маловероятно).
Определение. Если п — нечетное составное число, Ь — целое число, НОД (n,b) = 1, и (1) выполняется, то п называется псевдопростым числом по основанию Ь.
Другими словами, «псевдопростое» число — это число п, которое «претендует» быть простым, проходя тест (1).
§ 1. ПСЕВДОПРОСТЫЕ ЧИСЛА
141
Пример 1. Число п = 91 — псевдопростое по основанию 6 = 3, так как З90 = 1 (mod 91). Однако, 91 не есть псевдопростое число по основанию 2, так как 290 = 64 (mod 91). Если бы мы еще не знали, что 91 составное число, то соотношение 290 ф 1 (mod 91) доказало бы нам это.
Предложение V. 1.1. Пусть п — нечетное составное число.
a) Число п тогда и только тогда является псевдопростым по основанию Ь, для которого НОД (b,n) = 1, когда порядок b в группе (Z/nZ)* (т. е. наименьшее натуральное d, при котором bd = 1 (mod п)) делит п - 1.
b) Если п является псевдопростым по основаниям и Ь2, для которых НОД (6і, п) = НОД (b2,n) = 1, то п — псевдопростое по основаниям b\b2 и &i&2 1 (b2 1 обозначает элемент, обратный к Ь2 по модулю п).
c) Если п не является псевдопростым хотя бы по одному основанию b Є (Z/nZ)*, то п не проходит тест (1), по крайней мере, для половины оснований b Є (Z/nZ)*.
Док азательство. Части а) и b) очевидны, и мы оставляем их проверку читателю.
с) Пусть {6i, b2,..., bs} — множество всех оснований, по которым п — псевдопростое число, т. е. множество всех таких натуральных чисел, меньших п, для которых выполняется соотношение (1). Пусть b — фиксированное основание, по которому п не является псевдопростым. Если п было бы псевдопростым хотя бы по одному основанию bbi, то, ввиду части Ь), оно было бы псевдопростым по основанию b = (ЬЬі)Ьг (mod п), что противоречит выбору Ь. Таким образом, для s различных оснований {bbi, bb2,..., bb3} число п не проходит тест (1). Поэтому в группе (Z/nZ)* число оснований, по которым п не есть псевдопростое, не меньше числа оснований, для которых выполняется (1). Доказательство завершено.
Таким образом, если п удовлетворяет условию (1) не для всех возможных b с НОД (6, n) = 1, то при случайно выбранном b с вероятностью, не меньшей 50%, условие (1) для п не выполняется. Допустим теперь, что мы хотим выяснить, является ли данное большое нечетное число п простым. Мы можем случайно выбрать Ь в интервале 0 < b < п. Вначале находим d = НОД (Ь,п), применяя алгоритм Евклида. Если d > 1, то п — не простое число, и мы фактически уже нашли его нетривиальный делитель d\n. Если d = 1, возводим b в степень п — 1 (используя метод повторного возведения в квадрат, см. §1.3). Если (1) не выполняется, то п —составное число. Если (1) выполняется, то мы получаем некоторое подтверждение того, что п —
142
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
простое число. Мы выбираем тогда другое Ь и повторяем весь процесс. Если (1) нарушается для какого-либо 6, то можно остановиться, убедившись в том, что п — составное число. Предположим, ЧТО мы сделали к попыток с различными b и нашли, что п — псевдопростое число по всем к основаниям. По предложению V. 1.1 вероятность того, что составное п пройдет к тестов, не превышает 1/2к (если только п не таково, что (1) выполняется для каждого Ь Є (Z/nZ)*). Если к велико, мы можем быть уверены «с большой вероятностью», что п — простое (если только п не является псевдопростым по всем основаниям). Этот метод нахождения простых чисел называется вероятностным методом. Он отличается от детерминистического метода: слово «детерминистический» значит, что метод со 100%-й вероятностью определяет, является число п составным или простым.
Существуют ли такие составные п, что (1) выполняется для каждого Ь, взаимно простого с n? В таком случае вероятностный метод не может обнаружить, что п — составное (если только нам не повезет выбрать такое Ь, что НОД (b,n) > 1). Ответ на вопрос известен: такие числа существуют и называются числами Кармайкла.
Определение. Числом Кармайкла называется составное число п, для которого (1) выполняется при любом b Є (Z/nZ)*.
Предложение V. 1.2. Пусть п — нечетное составное число.
a) Если п делится на квадрат целого числа, большего 1, то п не есть число Кармайкла.
b) Если п свободно от квадратов, то п — число Кармайкла в том и только том случае, когда (р— l)|(n— 1) для всякого простого делителя р числа п.
Доказательство, а) Предположим, что р \п. Пусть g —
2 р(р-1)
образующий по модулю р , т.е. такое целое число, что g есть
наименьшая степень д, сравнимая с 1 по модулю р . Согласно упражнению 2 к §11.1 такое д всегда существует. Пусть п обозначает произведение всех простых делителей числа п, отличных от р. По китайской теореме об остатках существует решение системы из двух сравнений: b = д (mod р ) и b = 1 (mod п). Тогда Ь, как и д, есть образующий по модулю р2, и, кроме того, НОД (b,n) = 1, так как b не делится ни на р, ни на простые делители числа п .
