Упрощенное обоснование вероятностного теста Миллера–Рабина для проверки простоты чисел

Пусть $m$ — положительное целое число, $\mathbb Z^{*}_{m}$ — множество всех положительных целых чисел, взаимно простых с $m$, не превосходящих $m$. Число $s\in\mathbb Z^*_{m}$ называется свидетелем простоты числа $m$, если последовательность степеней
$$ s^{(m-1)2^{-i}}\pmod m,\quad i=0,1,\ldots,r,\quad m-1=2^{r}t, $$
где $t$ нечетно, состоит только из единиц, либо с них начинается, после чего продолжается минус единицей, и может быть, другими числами. В статье приводится простое доказательство следующего известного утверждения, лежащего в основе вероятностного алгоритма Миллера–Рабина распознавания простоты чисел. Множество всех свидетелей простоты составного числа $m$ имеет мощность, не большую $\varphi(m)/4$, где $\varphi(m)$ — функция Эйлера.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 96–01–068.