Математические основы защиты информации. Ишмухаметов Ш.Т - 36 стр.

                                                                           37

      Рабин доказал теорему о том, что если нечетное число n > 2–
составное, то множество свидетелей его простоты имеет мощность не более
φ(n)/4 < n/4. Отсюда следует, что если при проверке k произвольно
выбранных чисел a < n все они окажутся свидетелями простоты n, то n–
простое с вероятностью ошибки, не превышающей 4−k . На этом наблюдении
строится следующий тест Миллера–Рабина.

Тест Миллера–Рабина

      Пусть число n > 2–нечетно и n−1 = 2s ·d, где d–нечетно. Для каждого
числа a от 2 до r + 1, где r – число проверок в тесте, выполним следующие
действия:

      1. Вычислим x0 = ad (mod n).
      2. Проверим условие     x0 ∈ {1, n − 1}. Если оно выполнится, тогда
a–свидетель простоты. Перейдем к следующему a.
      3. Иначе проверим, содержится ли число n − 1 в последовательность
{x1 , x2 , ..., xs−1 }, где каждый последующий x вычисляется по формуле
xi+1 = x2i (mod n).
      Если ответ положительный, то a–свидетель простоты. Перейдем к
следующему a ≤ r + 1.
      Иначе, найден свидетель непростоты n. Завершаем тест с сообщением
«число n–составное».
      Если после r проверок окажется r свидетелей простоты, то
заканчиваем тест с сообщением «n–вероятно простое».
      Пример. Пусть n = 1729. Разложим n − 1 = 26 · 33 . Выполним тест
Миллера–Рабина для a = 2:
       x0 = 227 mod 1729 = 645 ̸= 1, ̸= n − 1,
       x1 = x20 mod 1729 = 6452 mod 1729 = 1065.
       x2 = x21 mod 1729 = 10652 mod 1729 = 1.
      Последующие элементы        {xi }   для    i   =   3, 4, 5   равны 1, и
последовательность {x1 , x2 , ..., xs−1 }, не содержит n − 1. Значит, 2
является свидетелем непростоты n, и n = 1729 – составное число.