Тест простоты Рабина - Тест Рабина является вероятностным

 

Тест Рабина является вероятностным. Это означает, что он использует датчик случайных чисел и, таким образом, работает не детерминированно. Для входного целого числа m тест Рабина может выдать один из следующих двух ответов.

1. Число m является составным.

2. Не знаю.

В случае первого ответа число m действительно является составным, тест Рабина предъявляет доказательство этого факта. Второй ответ может быть выдан как для простого, так и для составного числа m. Однако для любого составного числа m вероятность второго ответа не превышает 1/4. Ценность теста Рабина состоит именно в неравенстве, ограничевающем сверху вероятность второго ответа для произвольного составного числа m.

Таким образом, если мы применим 100 раз тест Рабина к числу m и получим 100 ответов "не знаю", то можно с большой вероятностью утверждать, что число m простое. Более точно, вероятность получения ста ответов "не знаю" для составного числа m не превышает (1/4)¹⁰⁰, т.е. практически равна нулю. Тем не менее тест Рабина не предъявляет доказательства того, что число m простое.

Перейдем непосредственно к изложению теста Рабина. Мы проверяем простоту входного числа m. Допустим сразу, что число m нечетное. (Существует только одно четное простое число -- 2.) Тогда число m - 1 четное. Представим его в виде

где s -- нечетное число. Выберем случайное число b такое, что

При выборе b используется датчик случайных чисел.

Используя алгоритм быстрого возведения в степень по модулю m, вычислим следующую последовательность элементов кольца Z_m:

     x0 == bs (mod m),                                 (1)
     x1 == x0 * x0 (mod m),
     x2 == x1 * x1 (mod m),
     ...
     xt == xt-1 * xt-1 == bm - 1 (mod m)

(На каждом шаге мы возводим в квадрат число, полученное на предыдущем шаге.)

Тест Рабина выдает ответ 'm -- составное число' в случае, если

1) x_t =/= 1 (mod m), или

2) в последовательности x₀, x₁, x₂, ..., x_t имеется фрагмент вида ..., *, 1, ... где звездочкой обозначено число, отличное от единицы или минус единицы по модулю m.

В противном случае тест Рабина выдает ответ "не знаю". Последовательность x₀, x₁, ..., x_t в этом "плохом" случае либо начинается с единицы, либо содержит (-1) где-нибудь не в конце.

Cуществует алгоритм, доказывающий простоту, со сложностью O(ln³n), согласно которому необходимо провести тест Рабина со всеми числами

а затем проверить, не является ли m степенью простого числа. Однако его правильность зависит от недоказанной в настоящее время гипотезы Римана.

Этот алгоритм, опираясь на недоказанный факт, в принципе может 'соврать' в отношении доказательства простоты, хотя если тест Рабина говорит, что число составное, значит так оно и есть. На практике он работает очень даже неплохо.