Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
Теперь покажем, что при заданном $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)$ прогонов.
