|
Страница 2 из 4
Тест Рабина является вероятностным. Это означает, что он использует датчик случайных чисел и, таким образом, работает не детерминированно. Для входного целого числа m тест Рабина может выдать один из следующих двух ответов. 1. Число m является составным. 2. Не знаю. В случае первого ответа число m действительно является составным, тест Рабина предъявляет доказательство этого факта. Второй ответ может быть выдан как для простого, так и для составного числа m. Однако для любого составного числа m вероятность второго ответа не превышает 1/4. Ценность теста Рабина состоит именно в неравенстве, ограничевающем сверху вероятность второго ответа для произвольного составного числа m. Таким образом, если мы применим 100 раз тест Рабина к числу m и получим 100 ответов "не знаю", то можно с большой вероятностью утверждать, что число m простое. Более точно, вероятность получения ста ответов "не знаю" для составного числа m не превышает (1/4)100, т.е. практически равна нулю. Тем не менее тест Рабина не предъявляет доказательства того, что число m простое. Перейдем непосредственно к изложению теста Рабина. Мы проверяем простоту входного числа m. Допустим сразу, что число m нечетное. (Существует только одно четное простое число -- 2.) Тогда число m - 1 четное. Представим его в виде m - 1 = 2t * s где s -- нечетное число. Выберем случайное число b такое, что b =/= 0, b =/= 1 (mod m), 1 < b < m При выборе b используется датчик случайных чисел. Используя алгоритм быстрого возведения в степень по модулю m, вычислим следующую последовательность элементов кольца Zm: 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) xt =/= 1 (mod m), или 2) в последовательности x0, x1, x2, ..., xt имеется фрагмент вида ..., *, 1, ... где звездочкой обозначено число, отличное от единицы или минус единицы по модулю m. В противном случае тест Рабина выдает ответ "не знаю". Последовательность x0, x1, ..., xt в этом "плохом" случае либо начинается с единицы, либо содержит (-1) где-нибудь не в конце. Cуществует алгоритм, доказывающий простоту, со сложностью O(ln3n), согласно которому необходимо провести тест Рабина со всеми числами
2 <= b < 70ln2m, а затем проверить, не является ли m степенью простого числа. Однако его правильность зависит от недоказанной в настоящее время гипотезы Римана. Этот алгоритм, опираясь на недоказанный факт, в принципе может 'соврать' в отношении доказательства простоты, хотя если тест Рабина говорит, что число составное, значит так оно и есть. На практике он работает очень даже неплохо. |