Теперь покажем, что при заданном $t$ из наблюдаемых значений $\left|c, t^{k} \bmod M\right\rangle$ в $O(\log \log M)$ прогонах мы можем найти правильное значение $r$ с вероятностью, близкой к 1 .
Назовем наблюдаемое значение $c$ хорошим, если
\[
\exists l \in\left[-\frac{r}{2}, \frac{r}{2}\right], r c \equiv l \bmod N .
\]

В этом случае существует такое $d$, что
\[
-\frac{r}{2} \leqslant r c-d N=l \leqslant \frac{r}{2}
\]

так, что
\[
\left|\frac{c}{N}-\frac{d}{r}\right|<\frac{1}{2 N} .
\]

Следовательно, если $c$ — хорошее, то $r^{\prime}$, найденное из (22), действительно делит $r$.
Теперь назовем с очень хороиим, если $r^{\prime}=r$.
Оценивая экспоненциальную сумму (21), мы можем легко проверить, что вероятность наблюдения хорошего $c$ не меньше, чем $\frac{1}{3 r^{2}}$. С другой стороны, существует $r \varphi(r)$ состояний $\left|c, t^{k} \bmod M\right\rangle$ с очень хорошими $c$. Таким образом, чтобы найти очень хорошее $c$ с высокой вероятностью, достаточно будет $O\left(r^{2} \log r\right)$ прогонов.