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

                                                                      28

      Для оценки эффективности теста Миллера–Рабина определим понятие
функции Эйлера.

Функция Эйлера ϕ(n)

      Леонард Эйлер ввел в обиход функцию ϕ, определенную на целых
положительных числах, значением которой на аргументе n является
количество положительных чисел, меньших n и взаимно-простых с n.
      Очевидно, что для всех n > 1 ϕ(n) < n. Для простого числа p
значение ϕ(n) равно p − 1, а для числа n, являющегося произведением двух
сомножителей n = n1 · n2 , ϕ(n) = ϕ(n1 ) · ϕ(n2 ).

      Рабин доказал теорему о том, что если нечетное число 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–составное».