Здравствуйте, sergey222, Вы писали:

S>Здравствуйте!

V>>II) Очень распространенный тест Рабина-Миллера

S>А кто-нибудь пробовал реализовать этот алгоритм? У меня получается, что ни одно число не проходит проверку. Возможно, я неправильно понял этот алгоритм, но другого (понятного для меня) описания теста Р-М я не встречал...

S>Спасибо.

Если поможет, то могу дать несколько другое описание.
Пусть p — число, которое проверяем, a — некоторое фиксированное целое число, взаимнопростое с p.
Пусть p==(2^k)*q, где q — нечетное.
Находим t = a^q.
Если t==1 или t==-1, значит есть вероятность, что число простое, но больше ничего сказать не можем, выход.
Для всех i от 1 до k повторяем
{
t = t*t;
Если t==-1, то опять есть вероятность, что число простое, выход.
Если t==1, значит число составное, при желании даже можно указать делители.
(Действительно, имеем t*t-1==0, (t-1)(t+1)==0 — один из них делитель нуля).
}
Если в конце t!=1, то число составное.

Этот тест повторяется для нескольких a, вероятность того, что число составное, если оно прошло s тестов равна 1/(4^s).