|
Страница 3 из 4
Теорема (законность теста Рабина) 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 не является простым. |