Здравствуйте!
V>II) Очень распространенный тест Рабина-Миллера
V> Вычислим b — число делений p-1 на 2 (т.е. 2^b — это наибольшая степень числа 2, на которое делится p-1). Затем вычислим m, такое что p=1+(2^b)*m (т.е. m — остаток от деления p-1 на 2^b).
V> 1) Выберем случайное число a, меньшее p. V> 2) j=0; z=(a*m) mod p V> 3) Если z==1 или если z==p-1, то p проходит проверку и может быть простым числом. V> 4) Если j>0 и z==1, то p не является простым числом. V> 5) j=j+1. Если j<b и z<p-1, устанавливаем z=(z*z) mod p и возвращаемся на шаг 4). Еслм z==p-1, то p проходит проверку и может быть простым числом. V> 6) Если j==b и z!=p-1, то, p не является простым числом.
А кто-нибудь пробовал реализовать этот алгоритм? У меня получается, что ни одно число не проходит проверку. Возможно, я неправильно понял этот алгоритм, но другого (понятного для меня) описания теста Р-М я не встречал...
