Тест простоты Рабина
Страница 3. Теорема (законность теста Рабина)


 

Теорема (законность теста Рабина)

1. Если тест Рабина выдает ответ 'm -- составное число', то m действительно является составным.

2. Вероятность ответа 'не знаю' для составного числа m не превосходит 1/4.

Доказательство. Докажем только первое утверждение. Если xt =/= 1 (mod m), то m не удовлетворяет малой теореме Ферма и, следовательно, не является простым. Если же последовательность (1) содержит фрагмент ..., a, 1, ..., где a =/= +-1 (mod m), то имеем

a2 == 1 (mod m), a =/= 1, a =/= -1 (mod m)

Если бы m было простым, то кольцо Zm являлось бы полем.

Но в любом поле есть только два квадратных корня из единицы: это единица и минус единица. (По теореме Безу, число корней многочлена не превосходит его степени, квадратные корни из единицы -- это корни многочлена x2 - 1.) Следовательно, число m не является простым.

 
« Предыдущая статья   Следующая статья »