Если можно эффективно вычислить $r$ как функцию $t$, то можно найти собственный делитель $M$ за время, ограниченное полиномом от $\log _{2} M$ с вероятностью $\geqslant 1-M^{-m}$ для любого фиксированного $\mathrm{m}$.
Предположим, что для данного $t$ период $r$ удовлетворяет
\[
r \equiv 0 \bmod 2, t^{r / 2}
eq-1 \bmod M .
\]

Тогда $\operatorname{gcd}\left(t^{r / 2}+1, M\right)$ — собственный делитель $M$. Заметим, что функция gcd вычислима за полиномиальное время.

Вероятность того, что это условие выполняется $\geqslant 1-\frac{1}{2^{k-1}}$, где $k-$ число различных нечетных простых делителей $M$, следовательно, $\geqslant \frac{1}{2}$ в нашем случае. Поэтому мы найдем хорошее значение $t$ с вероятностью $\geqslant 1-M^{-m}$ за $O(\log M)$ попыток. Самое длинное вычисление в одной попытке — вычисление $t^{r / 2}$. Обычный метод возведения в квадрат также дает полиномиальное время.