2d \gets 1

3for i \gets к downto О

4do х \gets d

5d \gets (d\cdot d) \bmod n

6if d=l и $x\ne 1$ и $x\ne n-l$

7then return true

8if b i=l

9then d \gets (d \cdot a) \bmod n

10if d\ne 1

11then return true

12return false

Вот как происходит эта проверка. В строке 1 число га - 1 переводится в двоичную систему. Это представление нужно, чтобы вычислять an~l mod п методом повторного возведения в квадрат (строки 3-9). Это делается тем же способом, что и в процедуре Modular-Exponentation, но заодно в строках 6-7 проверяется, не наткнулись ли мы на нетривиальный корень из 1. Если наткнулись, то продолжать дальше вычисление an~l mod п нет смысла, мы и так знаем, что число п составное; процедура Witness возвращает значение true. Если этого не произошло, возведение в степень заканчивается с результатом d и в строках 10-11 мы проверяем, равно ли d единице по модулю п. Если нет, то число п также составное (процедура возвращает значение true). Если нет, то возвращается значение false («число а не является свидетелем того, что п составное»).

В каком случае процедура Witness (а, га) возвращает значение true? В двух - либо имеется нетривиальный корень из 1 по модулю га, либо не выполнена малая теорема Ферма (число га не является пвсевдопростым по основанию а). В обоих случаях число га является составным.

Приведём теперь полностью вероятностный алгоритм Миллера - Рабина.

1for j \gets 1 to s

2do a \gets Random(1,n-1)

3if Witness(a,n)

4then return составноезаведомо

5return простоепочти наверняка

Процедура Miller-Rabin берёт s случайных чисел от 1 до га - 1 и проверяет, не является ли какое-то из них свидетелем того, что га - составное (в описанном выше смысле). Если является, то число га заведомо является составным, и об этом можно сообщить в строке 4. Если ни одно из выбранных чисел не является свидетелем, то выдаётся ответ «простое», хотя гарантии тут нет. (Мы оценим далее, насколько вероятен такой ответ при составном га.)

Для примера рассмотрим работу этого алгоритма для числа 561 (которое, как мы говорили, является числом Кармайкла 561). Для этого вернёмся к рис. 33.4, который соответствует вычислениям для а = 7. При последнем возведении в квадрат процедура обнаруживает нетривиальный корень из 1, поскольку 7280 = 67 (mod 561) и 7560 = 1 (mod 561). Тем самым значение а = 7 является свидетелем того, что число 561 составное: Witness(7, 561) = true. Если а = 7 встретится среди s случайных значений, выбранных в алгоритме Miller-Rabin, то алгоритм выдаст ответ «составное».

Если двоичная запись га содержит fi битов, то процедура Miller-Rabin(s, га) выполняет O(sfi) арифметических (и 0(s/33) битовых) операций (производится не более s операций возведения в степень).

Оценка вероятности ошибки для теста Миллера - Рабина.

Сообщая, что число га является простым, процедура Miller-Rabin (как и Pseudoprime) может ошибаться. Но тут есть важная разница. Процедура Pseudoprime давала неправильный ответ для некоторой (пусть небольшой) доли всех чисел - такие числа можно назвать «плохими» с точки зрения этой процедуры. Для теста Миллера - Рабина плохих чисел нет: для любого числа тест даёт правильный ответ с большой вероятностью. Плохим может быть лишь случайный выбор пробных свидетелей, и вероятность этого события мала.

Как мы сейчас докажем, для любого составного числа га не менее половины всех возможных значений а позволят установить, что га составное - так что вероятность однократного неудачного вы-борпа свидетеля не превышает 1/2, а при s-кратном повторении падает до 2~s.

Теорема 33.38

Пусть га - нечётное составное число. Тогда среди элементов Z+ не менее (га - 1)/2 являются свидетелями того, что га составное, то есть

\{а е Z+ : WiTNESs(a, га) = true) (га - 1)/2. Доказательство

Пусть фиксировано начётное составное число га. Будем называть элементы а £ Z+, для которых WlTNESs(a, п) = false, плохими. Мы хотим показать, что число плохих элементов не превосходит (п-1)/2.

Заметим, что все негодные элементы лежат в Z*. В самом деле, для плохого а выполнено равенство an~l = 1 (mod га), и потому

•п - 1

а и само а взаимно просты с га.

Теперь мы покажем, что все плохие элементы содержатся в некоторой собственной подгруппе В группы Z*. По следствию 33.16 число элементов в В не больше половины общего числа эдементов в Z*, откуда и следует доказываемое утверждение. Остаётся найти

собственную подгруппу В, содержащую все плохие элементы. Случай 1: Существует х £ Z*, для которого

хп~1 ф 1 (mod га).(33.43)

Тогда положим В равным {Ь £ Z* : Ьп~1 = 1 (mod га)}. Множество В замкнуто относительно операции -п, поэтому по теореме 33.14 оно является подгруппой группы Z*. Очевидно, все плохие элементы лежат вВипо предположению группа В является собственной подругоой - так что в этом случае всё доказано. Случай 2: Для всякого х £ Z*

xn~l = 1 (mod га)(33.44)

(га является числом Кармайкла).

Этот случай несколько более сложен. Покажем прежде всего, что га не может быть степенью простого числа. Пусть это не так и га = ре для нечётного простого р и для целого е > 1. Тогда по теореме

33.32группа Z* является циклической, то есть содержит элемент д, для которого ordn(g) = Z* = (р(п) = (р - 1)ре~1. По теореме

33.33из сравнения (33.44) следует, что га - 1 = 0 (mod ср(п)), но это невозможно, так как правая часть делится на р (и даже на pe 1, а левая на единицу меньше числа га, делящегося на р.

Итак, га является составным числом, которое не есть степень никакого простого числа, и потому содержит несколько разных простых множителей. Поэтому мы можем разложить га в произведение двух взаимно простых чисел п\,п2 > 1 (например, включив в щ один простой множитель, а в п2 - все остальные).

Число га - 1 четно. Выделим из него наибольшую степень двойки 2f, то есть запишем его в виде га - 1 = 2*и, где и нечётно. Для каждого а £ Z+ рассмотрим последовательность

а= (аи,а2и,а22и,... ,а2").(33.45)

состоящую из вычетов по модулю га; каждый следующий её элемент получается из предыдущего возведением в квадрат, а последний элемент есть ап~1. Заметим, что двоичная запись числа га - 1 оканчивается на га нулей, и потому все элементы этой последовательности встретятся в качестве промежуточных результатов при вычислениях в процедуре Witness (которые заканчиваются t возведениями в квадрат).

Какой вид может иметь последовательность а при различных а? Для каждого j = 0,1,... ,t посмотрим, какие члены могут появляться на j-ом месте в последовательности а (для удобства начинаем нумерацию с нуля, считая аи нулевым членом последовательности а). Последним членом (j = t) может быть только единица (иначе мы имели бы уже рассмотренный случай 1). С другой стороны, в начале последовательности а (то есть для j = 0) может