Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
§ 1. ПСЕВДОПРОСТЫЕ ЧИСЛА
145
Сильно псевдопростые. Рассмотрим теперь еще один вид критериев простоты, который в определенном смысле даже лучше теста Соловея-ГПтрассена, основанного на определении псевдопростоты по Эйлеру. Это — тест Миллера-Рабина, основанный на вводимом ниже понятии «сильной псевдопростоты». Предположим, что п — большое нечетное натуральное число и b Є (Z/nZ)*. Пусть, далее, п — псевдопростое по основанию Ь, т.е. b = 1 (mod п). Идея критерия сильной псевдопростоты такова. Пусть п — 1 = 2"t, t — нечет-
t7 ,(71-1)/2 ,(71-1)/4 ,(71-1)/25
но. Если последовательно вычислять О , О , • • ¦, о ,
то при простом п первым элементом, отличным от 1, должен быть элемент — 1, так как при простом п единственными решениями сравнения А" -1 = 0 (mod п) являются 4-1 и -1. Практически действия выполняются «в обратном направлении». Полагаем п — 1 = 2st, t — нечетно. Вычисляем Ь1 по модулю п. Если Ьг ф 1 (mod п), то возводим
t It
Ь в квадрат по модулю п, получая b (mod п), затем вновь возводим в
2г t
квадрат и т. д. до тех пор, пока не получим 1:6 =1 (mod п). Тогда, если п — простое, предыдущим числом должно быть —1, в противном случае мы получаем доказательство того, что п составное.
Определение. Пусть п — нечетное составное число и п — 1 = 2si, I - - нечетно. Пусть Ь Є (Z/nZ) . Если nub удовлетворяют одному из условий:
1) bl = 1 (mod п);
2) существует такое г, 0 ^ г < s, что
ЬГі = -1 (mod n), (3)
то п называется сильно псевдопросгпым по основанию Ь.
Предложение V. 1. 5. Если п ~ 3 (mod 4), mo п — сильно псевдопростое число по основанию b тогда и только тогда, когда оно — эйлерово псевдопростое по основанию Ь.
Доказательство. Так как в этом случае s=lnt = (n — 1)/2, мы видим, что п — сильно псевдопростое по основанию b тогда и только тогда, когда b^n 1^2 = ±1 (mod п). Если п —эйлерово псевдопростое, то это условие выполнено по определению. Обратно, пусть ^n-1^/2 = ±i (mod п). Мы должны показать, что ±1 справа — это (-). Но если п = 3 (mod 4), то ±1 = (~). Таким образом,
что и требовалось.
Следующие два важных предложения несколько труднее для доказательства.
146
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
Предложение V. 1. 6. Если п — сильно псевдопростое по основанию Ь, то оно также эйлерово псевдопростое по основанию Ь.
Предложение V. 1.7. Если п — нечетное составное целое число, то п — сильно псевдопростое по основанию Ь не более чем для 2Ъ% чисел Ь, 0 < b < п.
Замечание. Как мы увидим в упражнениях, в общем случае обратное утверждение к предложению V. 1.6 неверно.
Перед доказательством этих двух предложений мы опишем тест Миллера—Рабина на простоту. Предположим, что мы хотим определить, является большое натуральное число п простым или составным. Представим п — 1 в виде 2st,t нечетно, и выберем случайное целое число b, 0 < Ь < п. Сначала вычисляем Ь1 по модулю п. Если получается ±1, то заключаем, что п прошло тест (3) при данном Ь, и производим новый случайный выбор b. В противном случае возводим 6* в квадрат по модулю п, результат вновь возводим в квадрат по модулю п и продолжаем так до тех пор, пока не получим -1. Если это происходит, то мы считаем, что п прошло тест. Если же этого не происходит, т. е.
если мы получаем b =1 (mod п), в то время как b ф — 1 (mod п), то п не проходит тест, и это доказывает, что п — составное число. Если мы к раз случайно выбирали разные основания b и п каждый раз проходило соответствующий тест, то, согласно предложению V.l. 7, число п имеет не более одного шанса из 4 быть составным. Это следует из того факта, что если п — составное, то не более 1/4 всех возможных оснований b, 0 < Ь < п, удовлетворяет (3). Заметим, что это несколько лучше, чем в тесте Соловея-Штрассена, где аналогичная оценка шансов — 1 из 2к (мы увидим в одном из упражнений, что существуют составные числа п, являющиеся псевдопростыми эйлеровыми относительно половины всех возможных оснований).
Переходим к доказательствам предложений V. 1.6 и V. 1. 7.
Доказательство предложения V. 1.6. Пусть п и Ь удовлетворяют (3). Докажем, что они удовлетворяют (2). Полагаем п — 1 = 2st, t нечетное.
Случай 1. Пусть 6* = 1 (mod п). Тогда левая часть (2) есть, очевидно, 1. Нам нужно показать, что (^) = 1. Но 1 = (¦^) = (~) = (~У- Так как t нечетно, то (?) = 1.
Случай 2. Теперь предположим, что ь^п~1^2 = —1 (mod п). Мы должны показать, что (?) = -1. Пусть р — любой простой
делитель п. Представим р — 1 в виде 2 t , t нечетно.
§ 1. ПСЕВДОПРОСТЫЕ ЧИСЛА
147
Утверждение. Справедливы соотношения s' ^ s и b » _ / — 1, если s = s,
PJ { 1, если s > s.
Доказательство утверждения. Іаккако =
Ь = — 1 (mod п), то, возведя обе части в степень t , получаем (6 ) ее — 1 (mod п). Так как р\п, это сравнение справедливо и по
модулю р. В случае s' < s мы имели бы Ьр 1 = Ь2 1 ее 1 (mod р), что противоречит малой теореме Ферма. Поэтому s' ^ s. Если s = s,
то (62''"1'')' ее -1 (mod р). Поэтому (J) ее Ь{р~г)/2 = b2'''4' ее
